素数的几种判断方法总结（含C++代码）

2024-07-13 11:51| 来源: 网络整理| 查看: 265

素数的几种判断方法总结（含C++代码）一、素数定义二、素数判断方法1.定义法2.定义法改进3.取模法5.筛选法改进三、总结

一、素数定义

素数（prime number），也称质数，是指大于1的自然数中因数只有1和它本身的数。例如，2是素数，其只有1和2两个因数；29是素数，其只有1和29两个因数；51不是素数，除了1和51，它还有3和17两个因数，故称51为合数。

二、素数判断方法

给定一个正整数n (n≥2)：

1.定义法

即将n除以[2,n-1]的所有整数，若有其中一个数运算后的余数为0，也就是说这个数是n的因数，故n不为素数。代码如下：

bool isPrime(int n){ bool yes=true; for(int i=2;i yes=false; break; } } return yes; } 2.定义法改进

由于n的因数总是成对出现的，且分别分布在[1, n \sqrt n n ]和[ n \sqrt n n ,n]范围内（若因数为 n \sqrt n n ，我们当作两个重复的因数），那么我们只需判断一个范围即可。代码如下：

bool isPrime2(int n){ bool yes=true; for(int i=2;i yes=false; break; } } return yes; } 3.取模法

当n≥6时，由于n可以表示为6x+1、6x+2、6x+3、6x+4、6x+5、6x (x≥1)中的一种，那么，若n的表达式为6x+2、6x+4或6x，很显然n不是素数；故，当n的表达式为6x+1或6x+5时，可能为素数，再应用方法2。代码如下：

bool isPrime3(int n){ bool yes=false; if(n==2||n==3||n==5){ //当n if(n%i==0){ yes=false; break; } } } return yes; }

测试一下，消耗时间为

### 4.筛选法（Eratosthenes筛选）我们可以很容易的判断出2、3、5等较简单的数是素数，而且，当一个数是素数后，它的倍数一定为合数。因此，我们可以将一定范围的整数筛选掉合数，剩下的即是素数。代码如下： ```cpp bool isPrime4(int n){ bool yes=false; //先生成一定范围的整数表，再应用筛选法，得到素数表，最后与素数表比对 //生成0~100000内的素数表 int num[100000]={0}; //0表示素数，1表示合数 for(int i=2;i5，则在筛选5的倍数时已经筛掉5×a这个数了；这样一直到从a×a开始筛选，才没有被之前的过程筛掉。为什么筛掉a×a+2×a×i（i=0，1，2……）？我们可以将这个式子转化一下：a×a+2×a×i=a×(a+2×i)。可以看出当从a×a开始筛选时，筛掉a×(a+0)、a×(a+2)、a×(a+4)……符合前面过程中的规律。将上述过程总结成代码：

bool isPrime5(int n){ bool yes=false; int num[100000]={0}; //生成3~2*99999+3范围内的奇数数组 //先判断当n=2时的情况 if(n==2){ yes=true; } else{ for(int i=0;i for(int j=(2*i+3)*(2*i+3);j if(!num[(n-3)/2]){ yes=true; } } return yes; } 三、总结

将上述几种方法放到一起，代码如下：

#include #include #include #define SIZE 10000 using namespace std; bool isPrime(int n) { bool yes = true; for (int i = 2; i yes = false; break; } } return yes; } bool isPrime2(int n) { bool yes = true; for (int i = 2; i yes = false; break; } } return yes; } 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 yes = false; break; } } } return yes; } bool isPrime4(int n) { bool yes = false; int num[SIZE] = { 0 }; for (int i = 2; i for (int j = i + i; j yes = true; } return yes; } bool isPrime5(int n) { bool yes = false; int num[SIZE] = { 0 }; if (n == 2) { yes = true; } else { for (int i = 0; i for (int j = (2 * i + 3) * (2 * i + 3); j if (!num[(n - 3) / 2]) { yes = true; } } return yes; } int main() { cout cout if (isPrime2(i)) { cout if (isPrime3(i)) { cout if (isPrime4(i)) { cout if (isPrime5(i)) { cout

【本文地址】

公司简介

联系我们