21xrx.com
2024-11-10 00:19:39 Sunday
登录
文章检索 我的文章 写文章
C++ 编程求解 100 以内的所有质数 - 洛谷练习题
2023-07-05 07:29:59 深夜i     --     --
C++ 编程 求解 100以内 质数 洛谷

在计算机编程领域中,判断质数是经常遇到的问题之一。质数指只能被1和本身整除的数字,如2、3、5、7等。

在C++编程中求解100以内的所有质数,我们可以采用“筛法”,即从小到大的枚举每个数,如果发现它是质数,则将它的倍数都标记为合数,从而得到100以内的所有质数。代码如下:


#include<iostream>

using namespace std;

int main()

{

  bool a[101];

  for(int i=2;i<=100;i++)

  {

    a[i]=true;//初始化

  }

  for(int i=2;i<=50;i++)//循环遍历

  {

    if(a[i]==true)//如果该数是质数,就标记所有倍数

    {

      for(int j=2*i;j<=100;j+=i)//j是i的倍数,j不是质数

      {

        a[j]=false;

      }

    }

  }

  for(int i=2;i<=100;i++)//输出所有质数

  {

    if(a[i]==true)

    

      cout<<i<<" ";

    

  }

  cout<<endl;

  return 0;

}

代码中,我们定义了一个bool型数组a[101],用于标记每个数是否是质数。数组初始化时,所有元素都标记为true;在后面的循环中,用for循环依次枚举从2到50的每个数i,如果a[i]为true,则标记2i、3i、4i……的所有倍数为false,从而排除它们是质数的可能性。最后,再次循环遍历a数组,输出所有值为true的元素,即为100以内的所有质数。

除了筛法外,还有其他方法判断质数,比如试除法、费马小定理、米勒-拉宾算法等。不同的方法有不同的优缺点,具体使用时需要根据需求和程序复杂度进行选择。

通过本文的介绍,大家可以了解到如何在C++编程中求解100以内的所有质数。同时,也可以以此为基础,进一步了解和练习其他计算机编程技能,提高自己的编程水平。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复