C++ 欧拉筛法求素数

欧拉筛法是一种用于找出一定范围内所有质数的有效算法，它比简单的Sieve of Eratosthenes（埃拉托斯特尼筛法）更节省空间。在C++中，我们可以按以下步骤实现欧拉筛法：

1. **初始化数组**：创建一个大小为n+1的布尔数组isPrime，初始值都设为true。表示从2到n的所有数字都是潜在的质数。

2. **筛选过程**：从第一个质数2开始，遍历到√n，对每个质数p，将它的倍数标记为合数。但是，由于每次遇到质数，只需要更新那些大于或等于p^2的倍数，因为之前的倍数已经被较小的质数标记了。这一步可以利用位操作（如位移）提高效率。

   for (int p = 2; p * p <= n; ++p) {
       if (isPrime[p]) { // 如果p是质数
           for (int i = p * p; i <= n; i += p) {
               isPrime[i] = false;
           }
       }
   }

3. **生成素数序列**：最后，将isPrime数组中值为true的位置对应的索引即为素数。例如，isPrime[2]、isPrime[3]、isPrime[5]等。