本篇博客是【数论专题】系列的第 \(1\) 篇，希望大家多多支持。
埃氏筛
埃氏筛，全称埃拉托斯特尼筛法。
埃氏筛的核心思想是：如果一个数 \(p\) 是质数，那么 \(p\) 的倍数的不是质数，即将所有质数的倍数都标记为合数，不需要标记合数的倍数。
埃氏筛时间复杂度 \(o(n \log \log n)\)，但常数较大。
bool is_prime[N];//is_prime[i] 用来标记 i 是不是质数
void sieve_primes(int n)
{for(int i = 1;i <= n;i ++) is_prime[i] = true;//初始化 is_prime[1] = false;//1 不是质数 for(int i = 2;i <= n;i ++){if(is_prime[i] == false) continue;//因为只标记质数的倍数，所以遇到合数要跳过 for(int j = i * 2;j <= n;j += i)is_prime[j] = false;//标记 }
}
欧拉筛
欧拉筛，也称线性筛，是一种比埃氏筛更优秀的筛法。
欧拉筛的核心思想是：对于每个合数，只会被它的最小质因数给筛掉，从而避免重复标记。
欧拉筛需要多维护一个数组 \(prime\)，\(prime_i\) 表示第 \(i\) 个质数。
欧拉筛需要用当前遍历到的 \(i\) 和当前筛出的质数 \(prime_j\) 标记合数，因为 \(i\times prime_j\) 一定是合数，先进行标记，然后，最重要的优化来了：如果 \(i\bmod\ prime_j = 0\)，说明 \(i\) 的最小质因数为 \(prime_j\)，此时应该停止标记。
欧拉筛的时间复杂度为 \(O(n)\)。
bool is_prime[N];//is_prime[i] 用来标记 i 是不是质数
int prime[N], tot;//tot 表示当前质数的个数，prime[i] 表示第 i 个质数
void sieve_primes(int n)
{for(int i = 1;i <= n;i ++) is_prime[i] = true;//初始化 is_prime[1] = false;//1 不是质数 for(int i = 2;i <= n;i ++){if(is_prime[i] == true) prime[++ tot] = i;//如果第 i 个数是质数，把它加入 prime 数组 for(int j = 1;j <= tot && prime[j] * i <= n;j ++){is_prime[prime[j] * i] = false;//标记 if(i % prime[j] == 0) break;//当 prime[j] 是 i 的最小质因数是，停止标记 }}
}