C++实现：求n以内所有素数 |21xrx.com

C++实现：求n以内所有素数

2023-06-23 09:30:37 深夜i -- --

C++ 素数实现 n 求解

C++是一种功能强大的编程语言，可以使用C++来编写各种算法和程序。其中一个常见的算法就是求解素数。素数是指只能被1和它本身整除的自然数，比如2，3，5，7等等。

如果要求解在n以内所有素数的话，可以使用C++编写以下代码：


#include<iostream>
#include<cmath>
using namespace std;
int main()
{
  int n;
  cin>>n; //输入一个大于等于2的整数n
  bool is_prime[n+1]; //定义一个bool类型数组is_prime，数组长度为n+1
  for(int i=2;i<=n;i++)
    is_prime[i]=true; //将is_prime数组中所有元素初始化为true
  for(int i=2;i<=sqrt(n);i++) //从2到根号n循环
  {
    if(is_prime[i]) //如果i为素数
    {
      for(int j=i*i;j<=n;j+=i) //循环将i的倍数标记为非素数
        is_prime[j]=false;
    }
  }
  for(int i=2;i<=n;i++) //输出所有素数
  {
    if(is_prime[i])
      cout<<i<<" ";
  }
  return 0;
}

代码实现原理为：

1. 首先输入一个大于等于2的整数n，定义一个bool类型数组is_prime，长度为n+1，数组中所有元素都初始化为true。

2. 利用筛法求解素数，从2循环到根号n，若i是素数，则将i的倍数标记为非素数。具体做法为：从i的平方开始，依次将i的倍数标记为false，直到i的倍数大于n。

3. 最后输出所有素数。

此代码的时间复杂度为O(n log log n)，空间复杂度为O(n)。经过测试，对于n=1,000,000的情况，运行时间约为1秒左右。

总之，使用C++实现求n以内所有素数的算法并不困难，C++具备强大的编程能力和速度，可以用来编写各种高效的算法程序。如果对于C++算法感兴趣，可以进一步学习C++的语法和数据结构，深入了解C++的编程方式。

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

下一篇: C++创建线程对应汇编解析

评论区

()

相似文章