21xrx.com
2025-03-23 22:20:22 Sunday
文章检索 我的文章 写文章
C++求素数
2023-07-08 09:44:54 深夜i     12     0
C++ 素数 判断 循环 算法

素数是指除了1和本身之外没有其他因数的数，如2、3、5、7、11等。在计算机领域，求素数是一个非常基础的问题，因为在很多算法中都需要用到素数。

C++是一门常用的编程语言，在其中求素数也非常简单。下面介绍一种常用的方法。

方法一：试除法

试除法是指从2开始，逐个试除直到该数的平方根，若没有其他因数，即可确定该数是素数。

下面是该方法的C++代码实现：

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
  int n;
  cout<<"请输入一个整数"<<endl;
  cin>>n;
  bool prime=true;
  for(int i=2;i<=sqrt(n);i++)
  {
    if(n%i==0)
    
      prime=false;
      break;
    
  }
  if(prime)
    cout<<n<<"是素数"<<endl;
  else
    cout<<n<<"不是素数"<<endl;
  return 0;
}

方法二：埃氏筛法

埃氏筛法是一种筛法，可以在一段范围内快速筛选出所有的素数。具体做法是从2开始，将所有能被2整除的数标记为合数，然后从下一个素数3开始，将所有能被3整除的数标记为合数，以此类推，直到已知范围内的最大素数的平方根。

下面是该方法的C++代码实现：

#include<iostream>
#include<cmath>
using namespace std;
void Sieve(int n)
{
  bool *arr = new bool[n+1];
  for(int i=0;i<n+1;i++)
    arr[i]=true;
  for(int i=2;i<sqrt(n);i++)
  {
    if(arr[i]==true)
    {
      for(int j=i*i;j<n+1;j+=i)
        arr[j]=false;
    }
  }
  for(int i=2;i<n+1;i++)
  {
    if(arr[i]==true)
      cout<<i<<" ";
  }
  cout<<endl;
  delete[] arr;
}
int main()
{
  int n;
  cout<<"请输入一个整数"<<endl;
  cin>>n;
  cout<<"从1到"<<n<<"的所有素数是："<<endl;
  Sieve(n);
  return 0;
}

以上是C++求素数的两种常用方法。在实际应用中，可以根据需要选择不同的方法来求解。无论使用哪种方法，都需要运用数学知识和编程技巧来实现。

  
  

评论区