素数筛选法

1.埃拉托斯特尼筛法

埃拉托斯特尼筛法的基本思想是：要得到自然数 n 以内的全部素数，必须把不大于根号 n 的所有素数的倍数剔除，剩下的就是素数。

std::vector<int> sieve_of_eratosthenes(int n) {std::vector<bool> is_prime(n + 1, true);is_prime[0] = is_prime[1] = false;for (int i = 2; i * i <= n; ++i) {if (is_prime[i]) {for (int j = i * i; j <= n; j += i) {is_prime[j] = false;}}}std::vector<int> primes;for (int i = 0; i <= n; ++i) {if (is_prime[i]) {primes.push_back(i);}}return primes;
}

2.欧拉筛（线性筛法）

线性筛法的核心思想是每个合数只被它的最小质因数筛去。这样可以保证每个数只被筛一次，从而达到线性时间复杂度 O (n)。

std::vector<int> linear_sieve(int n) {std::vector<int> primes;std::vector<bool> is_prime(n + 1, true);is_prime[0] = is_prime[1] = false;for (int i = 2; i <= n; ++i) {if (is_prime[i]) {primes.push_back(i);}for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {is_prime[i * primes[j]] = false;if (i % primes[j] == 0) {break;}}}return primes;
}

对于if (i % primes[j] == 0)break;的解释

• 当i % primes[j] == 0时，意味着i可以写成i = k * primes[j]（k为整数）的形式。
• 此时如果继续让j增加，也就是用更大的素数primes[j + 1]去筛i * primes[j + 1]，会发现i * primes[j + 1]=(k * primes[j])* primes[j + 1]，而primes[j]小于primes[j + 1]，这就说明i * primes[j + 1]这个数的最小质因数应该是primes[j]，而不是primes[j + 1]。