素数筛法

Eratosthenes 筛法

基本思想

一个数可以质因数分解为几个素数的乘积，那么一个素数的倍数一定是合数，且素数不会为素数的倍数。

代码

使用 book 数组记录 i 是否为素数

for(int i=1;i<=n;i++)
    if(!book[i])
        for(int j=1;i*j<=n;j++)
            book[j]=1;

Euler 筛法

基本思想

已经筛过的数无需再筛，这是对上面筛法浪费的时间的优化。

代码

    for(int i=2;i<=n;i++)
    {
        if(!book[i])
            pri[++cnt]=i;
        for(int j=1;j<=cnt;j++)
        {
            if((long long)pri[j]*(long long)i>n)
                break;
            book[i*pri[j]]=1;
            if(!(i%pri[j]))
                break;
        }
    }