C++代码：求素数 |21xrx.com

C++代码：求素数

2023-06-26 12:27:11 深夜i -- --

C++ 代码素数

在计算机编程中，经常需要求出一定范围内的素数。素数，指的是除了1和本身之外，没有其他因数的正整数。计算机语言C++提供了一种简单的方法来求出素数。

算法描述：

1.定义一个数组，存储从2开始的整数序列。

2.将第一个数（即2）标记为素数，并将所有在2的倍数下标处的数标记为合数。

3.循环处理数组中的所有素数，只处理小于等于数组中最大素数的一半的数。如果这些素数的平方大于最大素数，则退出循环。

4.对于每个素数，将它的倍数标记为合数。

5.输出所有未被标记为合数的数。

C++代码实现：


#include<iostream>
#include<cmath>
using namespace std;
int main()
{
  int n;
  cout<<"请输入数字n：";
  cin>>n;
  bool *a=new bool[n+1];
  for(int i=0;i<=n;i++)
    a[i]=true;
  a[0]=a[1]=false;
  for(int i=2;i<=sqrt(n);i++)
  {
    if(a[i])
    {
      for(int j=2;i*j<=n;j++)
        a[i*j]=false;
    }
  }
  cout<<"素数有：";
  for(int i=0;i<=n;i++)
  {
    if(a[i])
      cout<<i<<" ";
  }
  return 0;
}

以上代码中，首先从终端获取输入的数字n，然后定义一个长度为n+1的bool型数组a，将所有元素初始化为true。

算法中的第2、3步在循环中实现，第4、5步在循环外实现。循环的起点是2，即从数组中第2个元素开始判断。

在第2步中，将第一个元素（即2）标记为素数，并将所有2的倍数下标处的元素标记为合数。从第3个元素开始循环，如果这个元素已经被标记为合数，则跳过；否则标记为素数，并将其倍数的下标处的元素标记为合数。

在第3步中，循环处理数组中的所有素数，只处理小于等于数组中最大素数的一半的数。如果这些素数的平方大于最大素数，则退出循环。

在第4步中，对于每个素数，将它的倍数标记为合数。

在第5步中，输出所有未被标记为合数的数。

总结：

通过以上代码，我们看到了C++可以很方便地实现求素数的算法。这也是我们学习编程语言的一个非常重要的目标，即将常用的算法用代码实现。通过练习，我们可以熟练掌握语言的语法，提高自己的编程水平。

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

下一篇: C++实战笔记》电子版免费下载

评论区

()

相似文章