[数论]线性筛素数表

注意

• 要Init_Prime()

说明

1. pcnt 记录素数的个数+1
2. prime[]记录素数表 有效数据范围:1~pcnt-1
3. factor[i]记录i的最小质数因子

模板

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;
}