文章导读
大家好，我是苏承栈，今天我们来聊聊素数判断这个话题。素数，也就是质数，在编程中经常遇到。那么，怎么快速判断一个数是不是素数呢？下面我给大家详细介绍几种方法，并附上C++代码示例。
素数定义
素数，顾名思义，就是只能被1和它本身整除的自然数。比如2、3、5、7等都是素数，而4、6、8等则不是。
素数判断方法
1. 定义法
最简单的方法就是试除法，将待判断的数除以从2到它本身减1的所有整数，如果有任何一个整数能整除它，那么它就不是素数。
bool isPrime(int n){
bool yes=true;
for(int i=2;i2. 定义法改进
由于一个数的因数总是成对出现的，所以只需要判断到它的平方根即可。
bool isPrime2(int n){
bool yes=true;
for(int i=2;i<=sqrt(n);i++){
if(n%i==0){
yes=false;
break;
}
}
return yes;
}3. 取模法
对于大于6的数，我们可以通过取模的方式快速排除一些非素数。
bool isPrime3(int n){
bool yes=false;
if(n==2||n==3||n==5){
yes=true;
}
else if(n%6==1||n%6==5){
yes=true;
for(int i=2;i<=sqrt(n);i++){
if(n%i==0){
yes=false;
break;
}
}
}
return yes;
}4. 筛选法（Eratosthenes筛选）
筛选法是一种更高效的方法，通过筛选掉一定范围内的合数，剩下的就是素数。
bool isPrime4(int n){
bool yes=false;
int num[100000]={0};
for(int i=2;i<100000;i++){
if(!num[i]){
for(int j=i+i;j<100000;j+=i){
num[j]=1;
}
}
}
if(!num[n]){
yes=true;
}
return yes;
}5. 筛选法改进
筛选法可以通过优化，提高判断素数的效率。
bool isPrime5(int n){
bool yes=false;
int num[100000]={0};
if(n==2){
yes=true;
}
else{
for(int i=0;i<100000;i++){
if(!num[i]){
for(int j=(2*i+3)*(2*i+3);j<(2*100000+3);j+=2*(2*i+3)){
num[(j-3)/2]=1;
}
}
}
}
if((n-3)%2==0){
if(!num[(n-3)/2]){
yes=true;
}
}
return yes;
}总结
以上就是几种判断素数的方法，每种方法都有其优缺点。在实际应用中，可以根据需要选择合适的方法。
我是苏承栈，如果你对编程有任何疑问，欢迎来「极星编程网」（www.jxgpc.com）和我交流。