C++编程：求解小于给定值的所有质数 |21xrx.com

C++编程：求解小于给定值的所有质数

2023-07-03 19:46:17 深夜i -- --

C++ 编程质数求解给定值

C++编程是一种优秀的编程语言，它可以轻松地实现各种不同的编程任务。其中一个常见的编程任务是求解小于给定值的所有质数。

质数是一种只能被1和它本身整除的自然数。因此，要找到小于给定值的所有质数，我们需要用到一个叫做“筛法”的算法。

这个算法的基本思想是，从2开始，将所有能被2整除的数都标记为非质数；然后，对于下一个未标记为非质数的数3，将所有能被3整除的数都标记为非质数；以此类推，一直到所有小于给定值的数都被标记完为质数或非质数为止。

下面是使用C++实现这个算法的示例代码：


#include<iostream>
#include<vector>
using namespace std;
void sieve(int n) {
  vector<bool> is_prime(n+1,true); //初始化所有数为质数
  is_prime[0] = false;
  is_prime[1] = false; //标记0和1不为质数
  for(int i=2; i*i<=n; i++) { //遍历2到n的平方根
    if(is_prime[i]) { //如果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 << " ";
    
  }
}
int main() {
  int n;
  cout << "请输入一个正整数：";
  cin >> n;
  cout << "小于" << n << "的所有质数为：" << endl;
  sieve(n);
  return 0;
}

在以上代码中，我们首先定义一个长度为n+1的bool型向量is_prime来表示小于等于n的所有数是否为质数。我们将所有数初始化为true，之后将0和1标记为false，因为它们不是质数。

接着，我们遍历2到n的平方根，标记所有质数的倍数为false。在执行这一步骤时，我们可以通过判断is_prime[i]的值是否为true来判断i是否为质数。

最后，我们遍历is_prime来输出小于n的所有质数。

当我们在终端界面上输入一个正整数n之后，程序就会输出所有小于n的质数。这个算法的时间复杂度为O(n log log n)，因此在实践中，它可以很快地计算出小于较大数的所有质数。

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

下一篇: C++代码库：汇集千万行开源C++代码

评论区

()

相似文章