素数筛法

2017-04-16更新:

void init_prime(int n) //欧拉素数筛法
{
    for(int i = 2; i <= n; i++)
    {
        if(!prime[i])
            prime[++prime[0]] = i;
        for(int j = 1; j <= prime[0] && prime[j] <= n / i; j++)
        {
            prime[prime[j] * i] = 1;
            if(i % prime[j] == 0)
                break;
        }
    }
}

以下是原文

埃氏筛法：

void init_prime()
{
    bool is_prime[maxn];
    memset(is_prime, 1, sizeof(is_prime));
    int cnt = 0;
    for(int i = 2; i <= maxn; i++)
    {
        if(is_prime[i])
            prime[cnt++] = i;
        for(int j = 0; j<cnt && i*prime[j]<=maxn; j++)
            is_prime[i*prime[j]] = 0;
    }
}

此法有冗余，例如对于数字12可以拆分为2 x 6或3 x 4，下面的快速筛法可以避免冗余。

欧拉筛法：

void init_prime()
{
    bool is_prime[maxn];
    memset(is_prime, 1, sizeof(is_prime));
    int cnt = 0;
    for(int i = 2; i <= maxn; i++)
    {
        if(is_prime[i])
            prime[cnt++] = i;
        for(int j = 0; j<cnt && i*prime[j]<=maxn; j++)
        {
            is_prime[i*prime[j]] = 0;
            if(!(i%prime[j]))
                break;
        }
    }
}

注意：

对于少量数据，应使用埃氏筛法减少 if 判断；而对于大量数据，应使用欧拉筛法减少冗余。