看通常做法：首先假设要检查的数是N好了，则事实上只要检查至N的开根号就可以了，道理很简单，假设
A*B = N，如果A大于N的开根号，则事实上在小于A之前的检查就可以先检查到B这个数可以整除N。不过在程式中使用开根号会精确度的问题，所以可以使用i*i <= N进行检查，且执行更快
而筛法具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛法”，简称“筛法”。（另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。
在n(n为求素数的范围)以内的数中,把2的倍数都去掉,再把3的倍数都去掉,如此,依次把第一个没有去掉数的倍数去掉,注意这个数本身不去掉.最后没被去掉的为所有的素数
#include<stdio.h> #include<memory.h> bool * prime(int n) { bool *p=new bool[n];
memset(p,n,sizeof(bool)*n);
//可以不要p[0]=p[1]=false; for(int i=2;i<n;i++) //这里i《n可以换成i*i<n if(p[i]) for(int j=i*i;j<n;j+=i) //注意这里j=i*i,很多人写成j=2*i,效率不高 p[j]=false; return p; } int main() { int n; scanf("%d",&n); bool *a=prime(n); printf("n内不包括n的素数有\n"); for(int i=2;i<n;i++) if(a[i]) printf("%d ",i); }
这个筛法是近似线性。
检查的次数还可以再减少，事实上，只要检查6n+1与6n+5就可以了，也就是直接跳过2与3的倍
数，使得程式中的if的检查动作可以减少
参考这个：
下列是伪代码算法：
// arbitrary search limit
limit ← 1.000.000
// assume all numbers are prime at first
is_prime(i) ← true, i ∈ [2, limit]
for n in [2, √limit]:
if is_prime(n):
// eliminate multiples of each prime,
// starting with its square
is_prime(i) ← false, i ∈ {n², n²+n, n²+2n, ..., limit}
for n in [2, limit]:
if is_prime(n): print n
可再简化为：
limit = 1000000 sieve$ = string of the character "P" with length limit prime = 2 repeat while prime
2
< limit
set the character at the index of each multiple of prime (excluding index prime * 1) in sieve$ to "N"
prime = index of the next instance of "P" in sieve$ after index prime
end repeat
print the index of each instance of "P" in sieve$
上面这个代码很好理解，下面这个就有点难理解了。
#include<stdio.h> #include<memory.h> #define mr 10 bool notp[mr];//素数判定 int pr[10000],pn,ans;//pr存放素数,pn当前素数个数。 void getprime() { pn=0; memset(notp,0,sizeof(notp)); for(int i=2;i<mr;i++) { if(!notp[i]) pr[pn++]=i; //注意这里是后缀，pr[0]存放第一个元素,若改成前缀，则pr[1]存放第一个 for(int j=0;j<pn&&pr[j]*i<mr;j++) { notp[pr[j]*i]=1; if(i%pr[j]==0) break; } } } int main() { getprime(); for(int i=0;i<pn;i++) printf("%d ",pr[i]); }
利用了每个合数必有一个最小素因子。
每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。
代码中体现在：
if(i%pr[j]==0)break;
pr数组中的素数是递增的,当i能整除pr[j]，那么i*pr[j+1]这个合数肯定被pr[j]乘以某个数筛掉。
因为i中含有pr[j],pr[j]比pr[j+1]小。接下去的素数同理。所以不用筛下去了。
在满足i%pr[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。
三、结合线性筛素数算法的优化算法
基于这个线性筛素数算法,我们可以很容易地得到某个数的最小素因子。
因为当i%pr[j]!=0的时候,最小素因子pr[j]与i互质,满足积性函数的条件,可以直接得到f(i*pr[j])=f(i)*f(pr[j]).
不过当i%pr[j]==0时我们必须根据该积性函数本身的特性进行计算.或者在筛的同时保存并递推些附加信息.总之要O(1)求得f(i*pr[j])及完成递推附加信息.
下面的两个例子是欧拉函数phi和约数个数.这两个是最常用和最有优化价值的。
利用上面的性质都可以很容易地把前n个用O(n)时间推出来.
当然，利用这个性质还可以对其他积性函数进行优化，这里仅介绍两个常用和有优化价值的。
1)欧拉函数(phi)
传统的算法:
对于某素数p且p|n(n能整除p)
if( (n/p) % i == 0 ) phi(n)=phi(n/p)*i;
else phi(n)=phi(n/p)*(i-1);
这个传统算法的性质正好用在筛素数算法中.
p为n的最小素因子,当n/p包含该因子p,则phi(n)=phi(n/p)*i;否则phi(n)=phi(n/p)*(i-1);
p即pr[j], n/p即i, n即i*pr[j]了.
2)约数个数(divnum)
约数不能像phi那么自然,但还是有不错的方法.
约数个数有个性质
divnum(n)=(e1+1)*(e2+1)...(ei表示n的第i个质因数的个数.)
传统方法就是对每个数分解质因数,获得各因数个数再用上式.
开一个空间e[i]表示最小素因子的次数
这次说直接点:
筛到i 第j个素数
对于divnum
如果i|pr[j] 那么 divnum[i*pr[j]]=divsum[i]/(e[i]+1)*(e[i]+2) //最小素因子次数加1
否则 divnum[i*pr[j]]=divnum[i]*divnum[pr[j]] //满足积性函数条件
对于e
如果i|pr[j] e[i*pr[j]]=e[i]+1; //最小素因子次数加1
否则 e[i*pr[j]]=1; //pr[j]为1次