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

/**
 * 线性筛法求素数表
 * 复杂度: O(n)
 */
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;
        }
    }
}

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

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

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

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

a=f × c ,其中c

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

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