C++ 素数（质数）的判定方法

 

 

素数的介绍：

素数定义：质数（prime number)又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说，就是该数除了1和它本身以外不再有其他的因数；否则称为合数。根据算术基本定理，每一个，比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积；而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的。最小的质数是2.

方法一：暴力筛选法

思路：根据素数的定义，我们能想到：若要判断n是否是素数，我们可以通过循环for（i=2;i<=n-1;i++)来进行n%i的运算，最后借n能否被i整除，来判断n是否为素数；若n能被整除，则n是素代码实现：

#include<iostream>using namespace std;bool is_prime(int n){int i;for(i=2;i<=n-1;i++){if(n%i==0){ return false;//若n能被i整除,则返回false;  break;}    }return true;//否则，返回true; }int main(){int n;cin>>n;is_prime(n);if(is_prime(true)){cout<<"Yes"<<endl;}else cout<<"No"<<endl;return 0;}

 在暴力筛选法中，我们可以发现其为时间复杂度O（n)，在此基础上，我们还可以优化将其变为时间复杂度O（sqrt(n)) .

优化原理：素数是因子为1和本身，若n不是素数，则一定是合数（一个合数一定含有小于它平方根的质因子）。假如该非素数为n=a*b,那么a,b一定有一个大于sqrt(n),一个小于sqrt(n)。所以必有一个小于或等于其平方根的因数，因此，验证n是否为素数时就只需要验证到n的平方根即可。

（不使用算术平方根）代码实现：

#include<iostream>using namespace std;bool is_prime(int n){int i;if(n<2)return false;for(i=2;i*i<=n;i++)  //这里可以不必单独使用平方算术根来表示{if(n%i==0) {return false;break; }}return true;}int main(){int n;cin>>n;is_prime(n);if(is_prime(true)){cout<<"Yes"<<endl;}else cout<<"No"<<endl;return 0;}

 （使用算术平方根）代码实现：

#include<iostream>#include<cmath>using namespace std;bool is_prime(int n){int i;if(n<2)return false;for(i=2;i<=sqrt(n);i++){if(n%i==0) {return false;break; }}return true;}int main(){int n;cin>>n;is_prime(n);if(is_prime(true)){cout<<"Yes"<<endl;}else cout<<"No"<<endl;return 0;}

方法二：count（有且仅有两因子：1和本身）

思路；根据素数的定义得出结论：构成素数的因子只有两个，即1和它本身，则通过count number(因子数）可以来筛选素数。

代码实现：一般型

#include<iostream>using namespace std;int main(){int i,n,count=0;cin>>n;for(i=1;i<=n;i++){if(n%i==0)//筛选出因子只有1和它本身的数count++;}if(count==2){cout<<"Yes"<<endl;}else cout<<"No"<<endl;return 0;}

函数型：

#include<iostream>using namespace std;bool is_prime(int n){int i,count=0;for(i=1;i<=n;i++){if(n%i==0){count++;}}if(count==2) return true;else return false;}int main(){int n;cin>>n;is_prime(n);if(is_prime(n)){cout<<"Yes"<<endl;}else cout<<"No"<<endl;return 0;}

 方法三：素数表筛选法

素数表筛选法顾名思义就是将素数存储到一个表中，然后对需要判断的数在该表中查找，能找到的即为素数，否则不是素数。

思路：（查找原理）若一个数不能整除比它小的任何素数，那么这个数就是素数。缺点：效率低下

代码实现：

/*n:所要判断的数；  j:素数表中素数的数； */#include<iostream>using namespace std;bool is_prime(int n){int i,j;for(i=0;i<j;i++){if(n%primearray[i]==0){return false;break;}return true;}}

 

 

 

 

 

本文链接：https://www.kjpai.cn/news/2024-04-25/162314.html，文章来源：网络cs，作者：付梓，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！