C++的素数判断方法 |21xrx.com

C++的素数判断方法

2023-06-29 06:15:45 深夜i -- --

C++ prime number determination method

C++是一种广泛应用于编程和软件开发的计算机语言。在程序设计中，经常需要进行数字的素数判断，因此C++也提供了多种方法来进行素数判断。

首先，最基本的素数判断方法是通过试除法来进行判断。试除法的原理是对于任意正整数n，如果存在一个正整数x，使得x能够整除n，且x不等于1和n本身，则n为合数；反之，则n为素数。利用C++中的for循环和if语句，可以简单地实现试除法进行素数判断的程序代码如下：


#include <iostream>
using namespace std;
bool judgePrime(int n){
 if(n<=1)
  return false;//将小于等于1排除，因为1既不是素数也不是合数
 for(int i=2;i*i<=n;i++){//循环从2到sqrt(n)，进行试除判断
  if(n%i==0)
   return false;//如果能够整除，n为合数，返回false
 }
 return true;//所有都不能整除，n为素数，返回true
}
int main()
{
 int num;
 cout<<"请输入一个整数：";
 cin>>num;
 bool result=judgePrime(num);
 string str=result?"是":"不是";
 cout<<num<<" "<<str<<"素数"<<endl;
 return 0;
}

除了试除法，C++还提供了其他素数判断方法。其中，最常用的方法是“厄拉多塞筛法”，该方法使用一个数组记录每一个数字是否为素数。初始化时，将数组中所有元素都设为true，然后分别从2到sqrt(n)的范围内循环，将所有能够被整除的数标记为false。最后，数组中剩下的为true的数即为素数。C++实现厄拉多塞筛法的程序代码如下：


#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
bool prime[10000];//记录每个数是否为素数
void initPrime(){
 memset(prime,1,sizeof(prime));//初始化数组元素值为true
 prime[0]=prime[1]=false;//用0和1初始化数组，在筛法时不考虑这两个数
 for(int i=2;i<sqrt(10000);i++){//从2到sqrt(10000)进行筛法
  if(prime[i]){
   for(int j=i*i;j<10000;j+=i){//将i的倍数全部标记为false
    prime[j]=false;
   }
  }
 }
}
int main(){
 initPrime();//初始化素数数组
 int num;
 cout<<"请输入一个整数：";
 cin>>num;
 string str=prime[num]?"是":"不是";
 cout<<num<<" "<<str<<"素数"<<endl;//输出结果
 return 0;
}

总而言之，在C++中实现素数判断方法可以利用试除法和厄拉多塞筛法等方式。根据实际需要选择不同的方法，以便快速高效地进行数字的素数判断。

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

下一篇: C++实现两个数相乘的代码

评论区

()

相似文章