C++编写求素数的代码 |21xrx.com

C++编写求素数的代码

2023-07-05 13:22:29 深夜i -- --

C++ 素数编写代码算法

C++是一种高级编程语言，常用于编写复杂的应用程序和算法。其中，求素数是一项常见的任务，也是C++编程的基本练习之一。那么，如何使用C++编写求素数的代码呢？

一、什么是素数

首先，我们需要了解什么是素数。素数是指只能被1和本身整除的正整数，例如2、3、5、7、11等。如果一个数可以被其他数整除，那么它就不是素数。

二、求素数的基本思路

在编写求素数的代码之前，我们需要先了解求素数的基本思路。首先，我们可以从2开始，依次判断每个数字是否为素数。具体地，我们可以使用一个循环，将每个数字与小于该数字的所有素数进行对比，如果该数字可以被其中任意一个数整除，那么它就不是素数。如果循环结束后仍然没有找到该数字的除1和本身之外的因子，那么它就是素数。

三、C++求素数的代码实现

下面，我们就可以使用C++编写求素数的代码了。具体地，我们可以定义一个函数，输入一个上限数字，输出在该数字范围内的所有素数。

以C++11为例，代码如下：


#include <iostream>
using namespace std;
bool isPrime(int n) {
  if (n <= 1)
    return false;
  
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0)
      return false;
    
  }
  return true;
}
void findPrimes(int n) {
  for (int i = 2; i <= n; i++) {
    if (isPrime(i))
      cout << i << endl;
    
  }
}
int main() {
  int n;
  cout << "请输入上限数字：";
  cin >> n;
  findPrimes(n);
  return 0;
}

上面的代码实现了一个isPrime函数和一个findPrimes函数。其中，isPrime函数用于判断一个数字是否是素数，它使用了循环+判断的方式。具体地，如果该数字小于等于1，那么它肯定不是素数；否则，我们从2开始，循环到该数字（i*i<=n），如果可以被其中任意一个数整除，那么它就不是素数；否则，它就是素数。

findPrimes函数用于找出在给定上限范围内的所有素数。具体地，它从2开始，逐个循环至上限数字n，如果该数字是素数，那么就输出它。

最后，在main函数中，我们可以输入一个上限数字n，并调用findPrimes函数，输出在该数字范围内的所有素数。

四、求素数的优化

不过，上面的实现方式并不是最优的，因为我们需要循环判断所有小于该数字的素数，这样会造成效率低下。因此，我们可以加入一些优化，提高求素数的速度。具体地，我们可以使用埃拉托斯特尼筛法（Erathostenes sieve），该算法可以通过逐步排除非素数，快速判断某个数字是否为素数。

以C++11为例，优化后的代码如下：


#include <iostream>
#include <vector>
using namespace std;
void findPrimes(int n) {
  vector<bool> is_prime(n + 1, true);
  is_prime[0] = false;
  is_prime[1] = false;
  for (int i = 2; i * i <= n; i++) {
    if (is_prime[i]) {
      for (int j = i * i; j <= n; j += i) {
        is_prime[j] = false;
      }
    }
  }
  for (int i = 2; i <= n; i++) {
    if (is_prime[i])
      cout << i << endl;
    
  }
}
int main() {
  int n;
  cout << "请输入上限数字：";
  cin >> n;
  findPrimes(n);
  return 0;
}

在优化后的代码中，我们使用了一个vector保存每个数字是否是素数。初始化所有的数字都是素数，因此初始化为true。接下来，我们循环遍历2至sqrt(n)，如果该数字是素数，我们就将从i*i开始，每隔i个数字的都标记为非素数（即false）。最后，我们再次循环遍历2至n，如果该数字是素数，就输出它。

通过这种优化方式，我们可以大大加快求素数的速度，提高程序效率。

五、总结

通过本文的学习，我们了解了C++编写求素数的基本思路，以及如何使用循环判断或埃拉托斯特尼筛法实现。无论是初学者还是有经验的开发者，都可以通过编写求素数的代码来提高自己的程序设计能力和算法水平。

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

下一篇: C++ 如何取整数部分

评论区

()

相似文章