欧拉筛

欧拉筛

代码

#include <iostream>
#include <cstdio>

int n;
int cnt, prime[1003];
bool is_prime[100005];

void Ols()
{
    for(int i = 2; i <= n; i ++) is_prime[i] = 1;
    
    for(int i = 2; i <= n; i ++)
    {
        if(is_prime[i]) prime[++ cnt] = i;
        
        for(int j = 1; j <= cnt; j ++)
        {
            is_prime[i * prime[j]] = 0;
            
            if(i % prime[j] == 0) break;
        }
    }
}

int main()
{
    scanf("%d", &n);
    
    Ols();
    
    for(int i = 1; i <= cnt; i ++) printf("%d%c", prime[i], " \n"[i == n]);
    
    return 0;
}

第20行为什么要break

欧拉筛保证为线性的关键就在于这个break， 在欧拉筛中， 每个合数只会被弃最小的质因子筛一次， 如果当前的i是prime[j]的倍数关系， 那么当j变为j加1时，$ i \times prime[j+1]$就相当于是用prime[$j + 1$]筛出， 但是显然这个数应该被prime[j]筛， 不满足了要求， 也就不再是线性。

举个例子

当前i=4， prime[j]为2，用$2 \times 4$更新8后， 如果不break， 那么就会用下一个质数3继续更新， 即用$3 \times 4$更新了12， 此时这个12是用3更新的， 但实际上12的最小质因子是2， 所以12应该被$2 \times 6$更新一次， 导致12被3更新的就是4是2的倍数， 所以一定要break。