线性筛素数表

说明:

pcnt 记录素数的个数+1

prime[] 记录素数表 有效数据范围:1~pcnt-1

factor[i] 记录i的最小质数因子

Tips: 记得要Init_Prime()

typedef long long ll;
#define maxn 100
ll prime[maxn]={1};
int pcnt=0;//素数下标1~pcnt-1
int factor[maxn]={1,1}; //factor[i]表示i的最小质因子
void Init_Prime(){
    pcnt=1;
    for(ll i = 2 ; i < maxn ; i ++){
        if(!factor[i]) {
            prime[pcnt++]=i;
            factor[i]=i;
        }
        for(ll j = 1 ; j < pcnt && i * prime[j] <  maxn ; j ++)
        {
            factor[i * prime[j]] = prime[j];
            if( !(i % prime[j] ) )
                break;
        }
    }
    return;
}

results matching ""

    No results matching ""