C++程序：求解n以内的质数 |21xrx.com

C++程序：求解n以内的质数

2023-07-04 21:57:23 深夜i -- --

C++ 程序 n 质数

如果你想编写一个C++程序，来求解n以内的所有质数，那么这篇文章就是为你准备的。

质数是指只能被1和它本身整除的自然数，如2、3、5、7等等。在计算机编程中，求解质数的程序十分常见，因为质数的应用非常广泛，如密码学、公钥加密、哈希函数等领域都会用到质数。

对于一个大于1的整数n来说，求解n以内的质数可以分为两种方法：一是使用暴力枚举的方法，遍历1到n中的每个数，判断其是否是质数；二是使用筛法，通过排除法来筛选出所有的质数。

下面我们分别介绍这两种方法的实现过程。

1. 暴力枚举法

暴力枚举法是最简单、最直接的方法。对于n以内的每个数i，我们都遍历它以内的所有数j，判断i是否可以被j整除，若是则跳出循环，否则该数为质数。

下面是具体的代码实现：


#include <iostream>
using namespace std;
bool isPrime(int n) {
  if (n <= 1) return false;
  for (int i = 2; i <= n / 2; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
int main() {
  int n;
  cout << "请输入一个正整数n: ";
  cin >> n;
  cout << n << "以内的质数有：";
  for (int i = 2; i <= n; i++) {
    if (isPrime(i)) cout << i << " ";
  }
  cout << endl;
  return 0;
}

2. 筛法

筛法的思路是先生成从2到n的所有自然数，然后从2开始按顺序依次排除掉所有2的倍数、3的倍数、4的倍数......直到n的根号。经过这样的筛选，剩余的自然数就是质数了。

下面是具体的代码实现：


#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1000001;
bool prime[maxn];
void sieve(int n) {
  memset(prime, true, sizeof(prime)); // 初始化数组为true
  prime[0] = prime[1] = false; // 数字0和1不是质数
  for (int i = 2; i * i <= n; i++) {
    if (prime[i]) {
      for (int j = i * i; j <= n; j += i) {
        prime[j] = false; // 把i的所有倍数标记为false
      }
    }
  }
}
int main() {
  int n;
  cout << "请输入一个正整数n: ";
  cin >> n;
  cout << n << "以内的质数有：";
  sieve(n);
  for (int i = 2; i <= n; i++) {
    if (prime[i]) cout << i << " ";
  }
  cout << endl;
  return 0;
}

总结

以上就是两种求解n以内质数的方法，它们的时间复杂度分别为O(n * n)和O(n log log n)。由于暴力枚举法的时间复杂度太高，在n很大的时候已经不适用了，因此我们更多地使用筛法来求解质数。

参考文献

1. 算法竞赛入门经典训练指南. 李煜东, 2018.

2. 《算法竞赛入门经典（第2版）》, by 李煜东, 张兆翔.

上一篇: idea打包java可执行jar包

下一篇: C++的有参构造函数重载

评论区

()

相似文章