【算法】素数(质数)判断方法「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

注：本篇文章已搬至个人博客中, 点击前往

素数(质数)的判断在算法问题中经常遇到，这里小结几种常用的判断方法。

素数(质数)的定义

首先，我们来看一下素数(质数)的定义：质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。

方法一

我们可以从它的定义得到判断素数的 第一个方法: 从 $2$ 到 $n - 1$ , 判断是否存在能被n整除的数，既 $\% i == 0, 2 <= i <= n – 1)$ ,如果有就不是素数，否则为素数。

(这里为了比较几种算法的性能，用计算出1000,000中有多少个素数所需的时间作为性能比较的参考。附上本篇博文所有程序的运行环境(机房哈哈)：系统windows xp, cpu:E5200,2.50GHZ, 0.99GB内存，IDE：codeblocks)

首先，可以先作一个小的优化，既除2以外，只需判断所有的奇数是否是素数。

//素数判断方法1
#include<stdio.h>
#include<time.h>
#define Max 1000000
int main()
{ 
   
    int sum = 1;//2单独处理，sum为素数的个数
    for(int i = 3; i <= Max; i+=2)
    { 
   //因为偶数除了2之外都不是素数(质数),所以只需判断奇数，从3开始每次+2
        int j;
        for(j = 2; j < i; j++)//判断
            if(i%j == 0)break;
        if(j == i)
            sum++;
    }
    printf("Time used = %0.2f s\n",(double)clock()/CLOCKS_PER_SEC);//获取程序运行的时间
    printf("%d",sum);
    return 0;
}

程序的时间复杂度为O( $n^2$ )。
运行结果
这里写图片描述
结果表明n的数量级太大时，不宜采用该方法。
同时也可以得到结论 $1000, 000$ 中有 $78498$ 个素数。

接下来的方法其实都是对上述方法进行优化，可以很好地降低时间复杂度。
利用以下结论：对正整数 $n$ ，如果用2到 $\sqrt{n}$ 之间的所有整数去除，均无法整除，则 $n$ 为质数。

方法二

//素数判断方法2
#include<stdio.h>
#include<time.h>
#include<math.h>
#define Max 1000000
int main()
{ 
   
    int sum = 1;
    for(int i = 3; i <= Max; i+=2)
    { 
   //因为偶数除了2之外都不是素数(质数),所以只需判断奇数，从3开始每次+2
        int j;
        for(j = 2; j <= (int)sqrt(i); j++)//利用上述结论判断
            if(i%j == 0)break;
        if(j > (int)sqrt(i))
            sum++;
    }
    printf("Time used = %0.2f s\n",(double)clock()/CLOCKS_PER_SEC);
    printf("%d",sum);
    return 0;
}

程序的时间复杂度为O( $\sqrt{n}$ )。
运行结果
这里写图片描述
可以看到程序的运行时间已经大幅度地降低。

接下来的方法需要利用到孪生素数的一些特点和结论。

孪生素数

孪生素数：孪生素数指的是间隔为 $2$ 的相邻素数。
1.当 $n > = 6$ , $n - 1$ 和 $n + 1$ 为孪生素数，那么n 一定是6的倍数。
Proof :

$\begin{aligned} &∵ n – 1, n + 1是素数，也即 n – 1 和 n + 1是奇数\\ &∴n 是偶数，n 是 2 的倍数。\\ &设 n 不是 3 的倍数，即 n = 3k + 1 或 n = 3k + 2。\\ &(i)当 n = 3k + 1 时，那么 n – 1 = 3k,已经与 n – 1 是素数矛盾。\\ &(ii)当 n = 3k + 2 时，那么 n +１＝3(k + 1),已经与 n + 1是素数矛盾。\\ &综上所述，n 是 3 的倍数。\\ &∵n既是2的倍数，又是3的倍数\\ &∴n 是6的倍数。\\ \end{aligned}$

推论1 : 当 $x > = 1$ , $(6 x - 1)$ 或 $(6 x + 1)$ 不是素数时，它们的质因子不包括2和3的倍数，因为 $2 (3 x) - 1, 3 (2 x) - 1, 2 (3 x) + 1, 3 (2 x) + 1$ 。

2.素数的分布规律:当 $n > = 5$ 时，如果n为素数，那么 $\% 6 = 1 || n \% 6 = 5$ ，即n一定出现在 $6 x (x \geq 1)$ 两侧。(就是说大于等于5的素数一定是分布在6倍数的左右两侧，但在6倍数左右两侧的数不一定是素数)
Proof：
$\begin{aligned} &可以把6x附近的数用以下方式表示：\\ &……(6x – 1), 6x, 6x+1, 2(3x+1), 3(2x+1), 2(3x +2), 6x + 5, 6(x+1)……\\ &不在6x两侧的数为： 2(3x+1), 3(2x+1), 2(3x +2),它们不是素数，所以素数出现在6x的两侧。\\ \end{aligned}$
有了以上的理论基础，我们可以对方法2进一步地优化，首先不在 $6 x$ 左右的数 $2, 3$ 单独处理，接下来只要判断 $6 x$ 两侧的数是否为素数。因为合数总是可以写成素数的乘积，那么我们直接用n去除以质数就可以达到很好地优化目的。而质数一定是 $6 x$ 两侧的数（推论一已证明了当 $n > = 5$ 时，n不是素数时，n 不含质因子2,3） , $6 x$ 两侧的数是大于素数的集合，因此可以用 $n$ 除以 $6 x$ 两侧的数即if(n % i == 0 || n % (i + 2) == 0)时，不是素数。

方法三：基于孪生素数方法筛除

//素数判断方法3
#include<stdio.h>
#include<time.h>
#include<math.h>
#define Max 1000000
using namespace std;
int main()
{ 
   
    int sum = 1;//已经将2单独处理
    int flag = 0;
    for(int i = 3; i <= Max; i+=2)
    { 
   
        if(i == 3)//3单独处理
            sum++;
         
        if(i % 6 != 1 && i % 6 !=5)
            continue;//不是6x两侧的数不是素数
        
        for(int j = 5; j <= (int)sqrt(i); j+=6)//对6x两侧的数进行判断
            if(i%j == 0 || i%(j + 2) ==0)
            { 
   
                flag = 1;
                break;
            }
            if(flag == 1)
            { 
   
                flag = 0;
                continue;
            }
        sum++;
    }
    printf("Time used = %0.2f s\n",(double)clock()/CLOCKS_PER_SEC);
    printf("%d",sum);
    return 0;
}

运行结果：
【算法】素数(质数)判断方法「建议收藏」
方法3运行结果表明比方法2快速了许多倍，已经是很高效的算法了。

方法四:普通筛选法

更新日记：2018/1/31增加普通筛选法
比上面几种方法更快，也比较容易理解。
思想: 一个素数的倍数都不是素数。
时间复杂度: O(nloglogn)

#include<iostream>
#include<vector>
using namespace std;
const int maxt = 1000000;
vector<bool>prime;
int main()
{ 
   
	prime.resize(maxt,1);
	prime[0] = prime[1] = 0;//1是素数，0是非素数
	for(int i = 2; i*i <= prime.size(); i++)
	{ 
   
		if(prime[i] == 1)
		for(int j = i*2; j <= prime.size(); j += i)
		{ 
   
			prime[j] =  0;
		}
	}
	return 0;
}