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]等。

相关问题

欧拉筛法求素数 c++

以下是使用欧拉筛法求素数的C++代码：

#include <iostream>
using namespace std;

const int MAXN = 1000000; // 筛数范围
int prime[MAXN + 5]; // 存储素数
bool isPrime[MAXN + 5]; // 标记是否为素数

int EulerSieve(int n) {
    int cnt = 0; // 素数个数
    for (int i = 2; i <= n; i++) {
        if (!isPrime[i]) {
            prime[cnt++] = i; // 将素数存入prime数组
        }
        for (int j = 0; j < cnt && i * prime[j] <= n; j++) {
            isPrime[i * prime[j]] = true; // 标记合数
            if (i % prime[j] == 0) { // 保证每个合数只被标记一次
                break;
            }
        }
    }
    return cnt;
}

int main() {
    int n;
    cin >> n;
    int cnt = EulerSieve(n);
    for (int i = 0; i < cnt; i++) {
        cout << prime[i] << " ";
    }
    return 0;
}

c++欧拉筛求素数个数代码

欧拉筛法是一种用于查找一定范围内所有质数的高效算法。它通过维护一个数组，记录每个合数因子的倍数已经被标记为合数，然后递归地筛选出所有的质数。以下是C++实现欧拉筛求素数个数的一个简化版本：

#include <iostream>
#include <vector>

void sieveOfEuler(int n, std::vector<bool>& isPrime) {
    isPrime.resize(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            // 将i的倍数标记为非素数
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    int count = 0;
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) ++count;
    }
    std::cout << "Number of primes up to " << n << ": " << count << std::endl;
}

int main() {
    int limit;
    std::cout << "Enter a number: ";
    std::cin >> limit;
    std::vector<bool> isPrime(limit + 1);
    sieveOfEuler(limit, isPrime);
    return 0;
}

在这个代码中，`sieveOfEuler`函数接收一个整数n和一个布尔向量`isPrime`，其中`isPrime[i]`表示i是否为素数。首先初始化所有数字为素数，然后从2开始，逐个检查并标记其因子的倍数。最后，统计并输出小于或等于给定数值的素数个数。