prime

题目描述

给定区间[L, R](L <= R <= 2147483647， R-L <= 1000000)，请计算区间中

素数的个数。

输入输出

输入

两个数 L 和 R。

输出

一行，区间中素数的个数。

样例

样例输入

2 11

样例输出

说明

时空限制

时间限制 1s/testcase

空间限制 32MB

思路

R-L<=1000000

L <= R <= 2147483647

时间上用质数筛能过

求出2~45000的所有质数（sqrt(2147483647)大约是4300+）

然后将所有是这些质数的倍数的数删掉，剩下的就是质数

空间上只有32mb，数组不能开太大，考虑到R-L<=1000000

完全可以只开到100005，之后对于大于100000的L和R，在存质数时

减去L即可。

代码

/*

b[i]==1  i不是质数

b[i]==0  i是质数

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int i,j,k,l,t,n,m,ans;

int zhi[100005];

bool b[100005],z[1000005];

inline int read() {

	int x=0,w=1;

	char ch=0;

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-') w=-1,ch=getchar();

	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();

	return x*w;

}

int main() {

	freopen("prime.in","r",stdin);

	freopen("prime.out","w",stdout);

	for(i=2; i<=sqrt(100000); i++) {

		if(!b[i]) {

			for(j=2; j<=100000/i; j++) {

				b[i*j]=1;

			}

		}

	}

	for(i=2; i<=100000; i++)if(!b[i])zhi[++zhi[0]]=i;

	n=read();

	m=read();

	for(i=1; i<=zhi[0]; i++) {

		for(j=max(n/zhi[i],1); j<=m/zhi[i]; j++) {

			if(j==1)continue;

			if(j*zhi[i]<n)continue;

			z[zhi[i]*j-n]=1;                   //平移数组，控制空间大小

		}

	}

	for(i=n-n; i<=m-n; i++) {

		if(!z[i])++ans;

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

【数论】8.30题解-prime素数密度洛谷p1835

prime

题目描述

输入输出

样例

说明

思路

代码

最新文章

热门文章

巴特西

【数论】8.30题解-prime素数密度 洛谷p1835

prime

题目描述

输入输出

样例

说明

思路

代码

最新文章

热门文章

【数论】8.30题解-prime素数密度洛谷p1835