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

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