21xrx.com
2025-04-07 11:38:48 Monday
文章检索 我的文章 写文章
C++ 实现统计素数个数的方法
2023-07-14 14:21:33 深夜i     19     0
C++ 统计素数 实现 方法 个数

随着计算机技术和算法的发展，计算素数个数的方法也不断得到改进。其中，C++ 作为一门高效的编程语言，可以很好地实现求解素数个数的功能。本文将介绍 C++ 中几种常见的统计素数个数的方法。

1. 埃拉托斯特尼筛法（Sieve of Eratosthenes）

埃拉托斯特尼筛法是一种简单而高效的算法，它的思路是：从小到大枚举每个数，把它的倍数全部标记为合数，直到最后只剩下素数。具体实现可以用一个布尔数组来表示每个数是否被筛掉，最后统计未被筛掉的素数个数即可。

以下是使用埃拉托斯特尼筛法实现统计素数个数的示例代码：

C++
int countPrimes(int n) {
  vector<bool> isPrime(n, true); // 初始化所有数为素数
  for (int i = 2; i * i < n; i++) {
    if (!isPrime[i]) continue; // 已经被筛掉了，跳过
    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++; // 统计未被筛掉的素数个数
  }
  return count;
}

2. 线性筛法（Linear Sieve）

线性筛法是对埃拉托斯特尼筛法的优化，它的核心思想是每个合数只被它的最小质因子筛掉一次。具体实现中，从小到大枚举每个数时，除去它的最小质因子后所得到的数为合数，但是由于它已经被它的最小质因子筛掉过了，所以不需要再重复标记。

以下是使用线性筛法实现统计素数个数的示例代码：

C++
int countPrimes(int n) {
  vector<int> primes; // 存储所有素数
  vector<int> isPrime(n, true); // 初始化所有数为素数
  for (int i = 2; i < n; i++) {
    if (isPrime[i]) {
      primes.push_back(i); // 添加素数到列表中
    }
    for (int j = 0; j < primes.size() && i * primes[j] < n; j++) {
      isPrime[i * primes[j]] = false; // 标记合数
      if (i % primes[j] == 0) break; // 跳出循环，保证每个合数只被它的最小质因子筛掉一次
    }
  }
  return primes.size();
}

3. 埃式筛法（Sieve of Atkin）

埃式筛法是一种比较新的素数筛法，它利用数学方法来筛选素数。其基本原理是找到一些模式，通过计算它们的生成公式、判别式、精度控制等方式，对素数和合数进行快速的判断和区分。

以下是使用埃式筛法实现统计素数个数的示例代码：

C++
int countPrimes(int n) {
  if (n <= 2) return 0;
  if (n <= 3) return 1;
  vector<bool> isPrime(n, false); // 初始化所有数为合数
  int sqrt_n = int(sqrt(n));
  for (int i = 1; i <= sqrt_n; i++) {
    for (int j = 1; j <= sqrt_n; j++) {
      int num = 4*i*i + j*j;
      if (num <= n && (num % 12 == 1 || num % 12 == 5)) {
        isPrime[num] = !isPrime[num];
      }
      num = 3*i*i + j*j;
      if (num <= n && num % 12 == 7) {
        isPrime[num] = !isPrime[num];
      }
      num = 3*i*i - j*j;
      if (i > j && num <= n && num % 12 == 11) {
        isPrime[num] = !isPrime[num];
      }
    }
  }
  int count = 0;
  for (int i = 5; i < n; i++) {
    if (isPrime[i]) count++; // 统计未被筛掉的素数个数
  }
  return count + 2; // 加上 2 和 3 两个素数
}

总结：

本文介绍了 C++ 中三种常用的统计素数个数的方法，分别是埃拉托斯特尼筛法、线性筛法和埃式筛法。不同方法之间的时间复杂度和实现难度存在一定的差异，选择合适的方法可以提高计算效率。

  
  

评论区

请求出错了