21xrx.com
2024-11-22 02:22:32 Friday
登录
文章检索 我的文章 写文章
C++教程:如何判断一个整数是否为素数
2023-07-11 19:39:37 深夜i     --     --
C++ 整数 素数 判断 教程

在计算机编程中,经常需要判断一个整数是否为素数。素数是只能被1和自身整除的大于1的整数。在C++中,可以通过以下方法判断一个整数是否为素数。

方法一:暴力枚举法

暴力枚举法是一种最简单的方法,但是效率较低。遍历整数n的所有小于等于sqrt(n)的正整数m,若n%m==0,则n不是素数;否则n为素数。代码如下:


#include <iostream>

using namespace std;

bool is_prime(int n){

 if(n<=1)

  return false;

 

 for(int i=2;i*i<=n;i++){

  if(n%i==0)

   return false;

  

 }

 return true;

}

int main(){

 int n;

 cin>>n;

 if(is_prime(n))

  cout<<n<<" is a prime number"<<endl;

 else

  cout<<n<<" is not a prime number"<<endl;

 

}

方法二:筛法

筛法是一种常用的优化算法,速度比暴力枚举法更快。筛法的核心思想是从小到大枚举素数,然后将其所有的倍数都标记成非素数。代码如下:


#include <iostream>

using namespace std;

bool is_prime(int n){

 if(n<=1)

  return false;

 

 bool *mark=new bool[n+1];

 for(int i=2;i<=n;i++){

  mark[i]=true;

 }

 for(int i=2;i*i<=n;i++){

  if(mark[i]){

   for(int j=i*i;j<=n;j+=i){

    mark[j]=false;

   }

  }

 }

 bool res=mark[n];

 delete[] mark;

 return res;

}

int main(){

 int n;

 cin>>n;

 if(is_prime(n))

  cout<<n<<" is a prime number"<<endl;

 else

  cout<<n<<" is not a prime number"<<endl;

 

}

综上所述,判断一个整数是否为素数的方法有很多种,可以根据实际情况选取适合的方法。在实际应用中,为了提高效率,一般采用筛法。

  
  

评论区

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