C++求解范围内的素数 |21xrx.com

C++求解范围内的素数

2023-07-05 12:50:39 深夜i -- --

C++ 求解范围素数算法

C++是一种功能强大的编程语言，常用于数值计算和程序开发等任务。在计算素数方面，C++提供了各种算法和工具，既能高效地计算出范围内的素数，又能够在程序中方便地使用和操作这些数字。

要使用C++求解范围内的素数，我们可以采用筛法。筛法是一种基于根号分解的方法，可以快速地计算一个范围内的所有素数。它的基本思路是首先将所有数字标记为未筛选，然后从小到大遍历数字，对于每个未筛选的数字，将其所有倍数标记为已筛选，直到遍历完成。最后，未被标记的数字就是范围内的所有素数。

以下是使用C++实现筛法求解范围内素数的代码示例：


#include <iostream>
#include <vector>
using namespace std;
vector<bool> sieve(int n) {
  vector<bool> primes(n + 1, true);
  primes[0] = primes[1] = false;
  for (int i = 2; i * i <= n; i++) {
    if (primes[i]) {
      for (int j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }
  return primes;
}
int main() {
  int n = 100;
  vector<bool> primes = sieve(n);
  for (int i = 2; i <= n; i++) {
    if (primes[i])
      cout << i << " ";
    
  }
  cout << endl;
  return 0;
}

在代码中，我们首先定义了一个sieve函数，它接受一个整数n作为输入，并返回一个长度为n+1的bool型向量。向量中第i个元素表示数字i是否为素数。

在sieve函数中，我们首先初始化向量中所有元素为true，然后将0和1标记为false，因为它们并不是素数。接下来，从2开始循环遍历所有数字，对于每个未被标记为非素数的数字i，我们将其所有倍数j标记为非素数。这一步可以通过一个双重循环实现，外层循环枚举每个未被标记的数字，内层循环标记它的倍数。最后，向量中未被标记为非素数的数字就是范围内的所有素数。

最后，在主函数中，我们定义了一个整数n，调用sieve函数求解范围内素数，并遍历向量输出所有素数。

使用C++求解范围内的素数，既简单又高效。通过使用筛法算法，可以快速计算出所有素数，并且在程序中方便地使用和操作这些数字。

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

下一篇: Qt 5.9 C++开发指南PDF下载

评论区

()

相似文章