C++程序员必备：求素数代码 |21xrx.com

C++程序员必备：求素数代码

2023-06-30 06:19:47 深夜i -- --

C++ 程序员素数代码必备

在C++编程中，求素数是一个基本的算法问题。素数是指只能被1和它本身整除的整数，而不能被其他数整除。素数的应用范围广泛，比如密码学、数据加密等领域。因此，C++程序员必须掌握如何编写求素数的代码。

下面介绍一种基本的求素数算法，使用的是最简单的试除法。具体步骤如下：

1. 从2开始，循环到要求的最大范围内的整数。

2. 对于每个数n，判断它是否为素数。判断的方法是循环从2到n-1，依次判断n是否能被这些数整除。如果n能整除其中任何一个数，则n不是素数。

3. 如果n不能被任何数整除，则n为素数。将n加入素数列表中。

下面是C++代码实现：


#include <iostream>
#include <vector>
using namespace std;
int main() {
  int max_num; // 最大范围
  cin >> max_num; // 输入最大范围
  vector<int> primes; // 存放素数的列表
  for(int i = 2; i <= max_num; i++) { // 循环判断每个整数
    bool is_prime = true;
    for(int j = 2; j < i; j++) { // 试除法判断i是否为素数
      if(i % j == 0)
        is_prime = false;
        break;
      
    }
    if(is_prime) { // 如果i是素数，则加入列表中
      primes.push_back(i);
    }
  }
  cout << "素数列表如下：" << endl;
  for(int prime : primes) // 输出素数
    cout << prime << " ";
  
  return 0;
}

上述代码中，使用了C++标准库中的vector类来存放素数列表。在循环判断每个整数是否为素数时，使用了一个bool变量is_prime来记录是否为素数。如果i不是素数，则跳出内层循环，继续判断下一个整数。如果i是素数，则将它加入素数列表中。

运行上述代码，输入一个正整数作为最大范围，程序将输出在此范围内的所有素数。这样，C++程序员就能够快速编写求素数的代码了。

当然，在实际应用中，这种简单的试除法并不是最优的求素数算法，因为它的时间复杂度较高，效率较低。当要求的范围比较大时，需要使用更加高效的算法，比如Eratosthenes筛法、欧拉筛法等。在选择算法时，需要根据具体问题的要求和数据规模来进行评估，选择合适的算法。

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

下一篇: "Java语言实现的人工智能毕业设计"

评论区

()

相似文章