【方法一】
【代码一】
-
-
int IsPrime(int a){
-
-
if(a <= 1){
-
return 0;
-
}
-
-
int bound = (int)sqrt(a) + 1;
-
for(int i = 2;i < bound;i++){
-
-
if(a % i == 0){
-
return 0;
-
}
-
}
-
return 1;
-
}
【方法二】
【代码二】
-
#define MAXSIZE 10001
-
-
int Mark[MAXSIZE];
-
int prime[MAXSIZE];
-
-
-
int Prime(){
-
int index = 0;
-
memset(Mark,0,sizeof(Mark));
-
for(int i = 0;i < MAXSIZE;i++){
-
-
if(Mark[i] == 1){
-
continue;
-
}
-
else{
-
-
prime[index++] = i;
-
-
for(int j = i*i;j < MAXSIZE;j += i){
-
Mark[j] = 1;
-
}
-
}
-
}
-
return index;
-
}
【方法三】
这种方法比较好理解，初始时，假设全部都是素数，当找到一个素数时，显然这个素数乘上另外一个数之后都是合数
把这些合数都筛掉，即算法名字的由来。但仔细分析能发现，这种方法会造成重复筛除合数，影响效率。
比如10，在i=2的时候，k=2*15筛了一次；在i=5，k=5*6 的时候又筛了一次。所以，也就有了快速线性筛法。
【代码三】
-
int Mark[MAXSIZE];
-
int prime[MAXSIZE];
-
-
-
int Prime(){
-
int index = 0;
-
memset(Mark,0,sizeof(Mark));
-
for(int i = 2; i < MAXSIZE; i++)
-
{
-
-
if(Mark[i] == 0){
-
prime[index++] = i;
-
}
-
-
for(int j = 0; j < index && prime[j] * i < MAXSIZE; j++)
-
{
-
Mark[i * prime[j]] = 1;
-
if(i % prime[j] == 0){
-
break;
-
}
-
}
-
}
-
return index;
-
}
利用了每个合数必有一个最小素因子。每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。
代码中体现在：
if(i%prime[j]==0)break;
prime数组 中的素数是递增的,当 i 能整除 prime[j]，那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉。
因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。
在满足i%prme[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。
参考博文：点击打开链接
习题练习：点击打开链接
[算法]素数筛法
原文：http://blog.csdn.net/sunnyyoona/article/details/41846513
