素数是指只能被1和它本身整除的正整数，例如2、3、5、7、11等。求n以内所有素数是一个常见的问题，在这里我们介绍一种C++程序实现方法。

程序思路：使用一个布尔数组来标记每个数是否为素数，初始化为true。然后从2开始遍历到n，如果发现当前数i没被标记为非素数，那么就将i的倍数都标记为非素数。最后再遍历一遍数组，输出所有为素数的数字。

程序代码如下：

#include <iostream>
using namespace std;
int main()
{
  int n;
  cout << "请输入一个正整数n：";
  cin >> n;
  bool *isPrime = new bool[n + 1]; //使用动态数组，方便处理
  for (int i = 2; i <= n; i++)   //初始化，全部标记为true
  {
    isPrime[i] = true;
  }
  for (int i = 2; i <= n; i++)   //遍历每个数
  {
    if (isPrime[i])       //如果当前数是素数，那么将它的倍数都标记为非素数
    {
      for (int j = 2 * i; j <= n; j += i)
      {
        isPrime[j] = false;
      }
    }
  }
  cout << "1到" << n << "之间的素数如下：" << endl;
  for (int i = 2; i <= n; i++)   //输出所有为素数的数字
  {
    if (isPrime[i])
    
      cout << i << " ";
    
  }
  cout << endl;
  delete[] isPrime;        //记得释放内存
  return 0;
}

使用该程序，可以较快地求出任意范围内所有素数。例如，如果输入n=20，则输出如下：

请输入一个正整数n：20
1到20之间的素数如下：
2 3 5 7 11 13 17 19

值得注意的是，这个程序的时间复杂度为O(nloglogn)，比起最朴素的方法（枚举每个数，检查是否为素数）要高效得多。因此，在需要求素数的时候，使用该程序是一个明智的选择。

相似文章

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