算法提高 找素数 Eratosthenes素数筛法

题目链接

问题描述

　　给定区间[L, R] ， 请计算区间中素数的个数。

【分析】
对于这样的限制，直接枚举判断会超时：需要判断10^6个整数，而每个整数还需要花费一定的时间判断是否为素数。用Eratosthenes筛法构造1～n的素数表。筛法的思想特别简单：对于不超过n的每个非负整数p，删除2p, 3p, 4p,…，当处理完所有数之后，还没有被删除的就是素数。如果用vis[i]表示i已经被删除，筛法的代码可以写成： 

memset(vis, 0, sizeof(vis));
for(int i = 2; i <= n; i++)
for(int j = i*2; j <= n; j+=i) vis[j] = 1;

       尽管可以继续改进，但这份代码已经相当高效了。为什么呢？给定外层循环变量i，内层循环的次数是。这样，循环的总次数小于。这个结论来源于欧拉在1734年得到的结果： ，其中欧拉常数γ≈0.577218。这样低的时间复杂度允许在很短的时间内得到10^6以内的所有素数。

       下面来改进这份代码。首先，在“对于不超过n的每个非负整数p”中，p可以限定为素数——只需在第二重循环前加一个判断if(!vis[i])即可。另外，内层循环也不必从i*2开始——它已经在i=2时被筛掉了。改进后的代码如下：

int m = sqrt(n+0.5);
memset(vis, 0, sizeof(vis));
for(int i = 2; i <= m; i++) if(!vis[i])
for(int j = i*i; j <= n; j+=i) vis[j] = 1;

这里有一个有意思的问题：给定的n，c的值是多少呢？换句话说，不超过n的正整数中，有多少个是素数呢？
素数定理： 。
其中，π(x)表示不超过x的素数的个数。上述定理的直观含义是：它和x/lnx比较接近——对于算法入门来说，这已足够。

#include <cstdio>
const int N = 1000000+5;
bool notPrime[N],smallPrime[N];
 
int main(int argc, char** argv) {	
	int L, R;
	scanf("%d%d",&L,&R);
	for(long long i = 2; i*i <= R; i++){
		if(!smallPrime[i]){
			for(long long j = i*i; j*j <= R; j += i) smallPrime[j] = true;
			for(long long j = max(i,((L-1)/i +1))*i; j <= R; j += i)
				notPrime[j-L] = true;
		}	
	}
	int cnt = R-L+1;
	for(int i = 0; i <= R-L; i++)  cnt -= notPrime[i];
	printf("%d\n",cnt);
	return 0;
}

输入格式

　　两个数L和R。

输出格式

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

样例输入

2 11

样例输出

5

数据规模和约定

　　2 <= L <= R <= 2147483647 R-L <= 1000000