Euler’s Sieve 欧拉线性筛选

Euler’s Sieve 欧拉线性筛选
求0-N之间额素数，线性筛法是我见过的最好的算法了，具有线性时间复杂度。
http://www.cnblogs.com/hailoong/archive/2011/01/31/1948261.html
原理:
1. 任何一个合数都可以表示成一个质数和一个数的乘积
2. 假设A是一个合数，且A = x * y，这里x也是一个合数，那么有:
       A = x * y; (假设y质数，x合数)
       x = a * b; (假设a是质数，且a < x)
 ->  A = a * b * y = a * Z (Z = b * y)
即一个合数(x)与一个质数(y)的乘积可以表示成一个更大的合数(Z)与一个更小的质数(a)的乘积
这也是理解代码中 if(i%primes[j] == 0)break;的关键
例如: 如果i = 8; 那么由于i%2 == 0; 因此对于i=8就只需要检查primes[1]即可，因为对于大于primes[1]的质数，像3，有:
        8*3 = 2*4*3 = 12*2
也就是说24(8*3=24)并不需要在8时检查，在12时才检查 

1. const int MAX=100;  
2. bool isPrime[MAX+1];  
3. int total;//计数  
4. int prime[MAX+1];  
5. //线性筛法寻找素数  
6. void makePrime()  
7. {  
8.     memset(isPrime,true,sizeof(isPrime));  
9.     memset(prime,0,sizeof(prime));  
10.     for(int i=2;i<=MAX;i++)  
11.     {  
12.         if(isPrime[i]) prime[total++]=i;  
13.         for(int j=0; j<total && i*prime[j]<=MAX; j++)  
14.         {  
15.             isPrime[i*prime[j]]=false;  
16.             //i此时不是素数,只是拓展用  
17.             if(i%prime[j]==0) break;  
18.         }  
19.     }  
20. }  
21. int main()  
22. {  
23.     makePrime();  
24.     for(int i=0;i<total;i++)  
25.     {  
26.         cout<<prime[i]<<" ";  
27.         if((i+1)%10==0) cout<<endl;  
28.     }  
29.     return 0;  
30. }  

线性筛法求质数(素数)表 及其原理

线性筛法,即是筛选掉所有合数,留下质数

我们知道合数可以由一个质数数与另一个数相乘得到

而同时假设合数a=质数b×质数c×一个数d

令e=c × d,假设b ≥ e,e为合数,令f=d × b

a=f × c ,其中c

即比一个合数数大的质数和该合数的乘积可用一个更大的合数和比其小的质数相乘得到

这也是if(!( i % prime[j]))break;的含义,这也是线性筛法算质数表的关键所在

这个算法的关键在于 if(i%pr[j] == 0) break;。它使得任何一个合数，只被它最小的质因数标记过一次。所以整个算法是线性的。但考虑到log(log(100000000))还不到3，故这个线性算法其实也只有理论上的价值罢了。

const long MAXP = 1000000;
long prime[MAXP] = {0},num_prime = 0;
int isNotPrime[MAXP] = {1, 1};
void GetPrime_Init()//初始化调用
{
    for(long i = 2 ; i <  MAXP ; i ++)
    {
        if(! isNotPrime[i])
            prime[num_prime ++]=i;
        for(long j = 0 ; j < num_prime && i * prime[j] <  MAXP ; j ++)
        {
            isNotPrime[i * prime[j]] = 1;
            if( !(i % prime[j]))
                break;
        }
    }
}

http://zhiqiang.org/blog/science/computer-science/complexity-of-prime-sieve.html

Time Complexity of Sieve of Eratosthenes: 此算法复杂度实际为 

O(∑p<nn/p)=O(nloglogn) 。

bool* prime(int n) {
  bool *p = new bool[n];
  memset(p, 0, sizeof p);
  for (int i = 2; i < n; i++)
    if (!p[i])
      for (int j = 2*i; j < n; j+=i)
        p[j] = true;
  return p;
}

Also check http://blog.sina.com.cn/s/blog_60263c1c0101dgwi.html
http://blog.csdn.net/dinosoft/article/details/5829550