C++教程：如何判断一个整数是否为素数 |21xrx.com

C++教程：如何判断一个整数是否为素数

2023-07-11 19:39:37 深夜i 22 0

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;
 
}

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

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

下一篇: C++虚函数的定义和概念

评论区

相似文章