欧拉筛法

· · 算法·理论

欧拉筛法

欧拉筛法是一种筛质数的方法，时间复杂度 O(n) ，快于埃式筛法。

代码

const int N = 100005, M = 15000;
int pri[M], tot;
bitset<N> ispri;
void get_prime(){
    for(int i = 2; i < N; i++){
        if(!ispri[i]) pri[tot++] = i;
        for(int j = 0; j < tot && (long long)i * pri[j] < N; j++){
            ispri[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}

代码解释

对于每一个数 $i$ ，如果 `ispri[i] == 0` 说明了 $i$ 还没有被标记过，那么 $i$ 就是质数，应该放进质数的数组， `pri[tot++] = i;` 接下来把 $i$ 看成一个倍数，用它乘上每一个已经筛出来的（小于 $i$ 的）质数，筛掉它们： `ispri[i * pri[j]] = 1;` 。 为了保证其 $O(n)$ 的时间复杂度，我们只希望每一个数被他的最小的质因子筛掉，这样可以保证每一个数只被筛掉一次。 如果 $pri[j]\mid i$ ，那么再 $pri[j + 1] \times i$ 这个数中，存在质因子 $pri[j]$ 。但是由于 $pri[j] < pri[j + 1]$ ，所以 $pri[j + 1]$ 并不是 $pri[j + 1] \times i$ 的最小质因数。那就可以 `break;` 掉它。