质数筛选

·Ansel · 2022-09-07 20:56:06 · 个人记录

质数筛选

埃拉托色尼筛法

首先 定义两个数组一个数据清单numlist 一个质数prime
两层循环嵌套依次将将j = i 的倍数 < n 的数据标记为numlist[i * j] = 1
cpp
void calc(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!numlist[i] )
        {
            cnt++;
            prime[cnt] = i;
        }
        for (int j = i; i * j <= n; j++)
        {
            numlist[i*j] = 1;
        }
    }
    return;
}

欧拉筛

同为两层循环嵌套 为避免重复筛选标记，仅用最小质数的倍数依次标记，且若
i%prime[j] == 0,则表示已用该数的最小因子标记
cpp
void calc(int n)
{
    numlist[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!numlist[i] )
        {
            cnt++;
            prime[cnt] = i;
        }
        for (int j = 1; j <= cnt && prime[j] * i <= n; j++)
        {
            numlist[ i * prime[j] ] = 1;
            if(i % prime[j] == 0) break;
        }
    }
    return;
}