埃氏筛
入门埃氏筛是求质数表的经典算法，时间复杂度 O(n log log n)。
// 算法讲解
埃氏筛
演示埃拉托斯特尼筛法求质数的过程。
待机
速度 中
待机 ⌨1vector<int> sieve(int n) {
2 vector<bool> isPrime(n + 1, true);
3 isPrime[0] = isPrime[1] = false;
4 for (int i = 2; i * i <= n; i++)
5 if (isPrime[i])
6 for (int j = i * i; j <= n; j += i)
7 isPrime[j] = false;
8 vector<int> primes;
9 for (int i = 2; i <= n; i++)
10 if (isPrime[i]) primes.push_back(i);
11 return primes;
12}
复杂度分析
时间 O(n log log n)
空间 O(n)
最优 O(n log log n)
最坏 O(n log log n)
算法讲解
埃氏筛从 2 开始，将每个质数的倍数标记为合数。
当处理到 √n 时，所有合数都已被标记，剩余未标记的即为质数。
时间复杂度 O(n log log n)，空间复杂度 O(n)。
它是数论算法的基础，常用于预处理质数表。