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)，因此在实践中，它可以很快地计算出小于较大数的所有质数。

相似文章

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政