不断优化的素数算法

前言：素数判断是算法中重要的一环，掌握优秀的素数判断方法是算法player的必修课。本文介绍的是由简到繁的素数算法，便于初学者从入门到精通。

素数（质数）：只能被 1 和它本身整除的数称作素数，如：2、3、5、7、11等

一、🍓 暴力算法 🍓

暴力算法是利用循环，看 $2 - n$ 之间是否有能被 $n$ 整除的数，若有，则 $n$ 就是素数，否则就不是。
Java代码如下： 时间复杂度为 $O (n)$

	/*** 不停地判断 2 ~ n-1 之间是否有数可以被 n 整除* @param n 输入的数字* @return 返回true为素数，false不为素数*/public static boolean isPrime(int n){for (int i= 2; i < n; i ++){//只要有数能被 n 整除，就返回falseif(n % i == 0)return false;}//没有数能被 n 整除就返回truereturn true;}

简单优化：
其实循环的范围可以缩小到 n 的平方根，这是数学定理，就不过多赘述，这样时间复杂度就减小到了 $O(\sqrt{n})$ ，那么代码就改变为如下：

	/*** 不停地判断 2 ~ 根号 n 之间是否有数可以被 n 整除* @param n 输入的数字* @return 返回true为素数，false不为素数*/public static boolean isPrime(int n){//Math.sqrt()的作用是求平方根for (int i= 2; i <= Math.sqrt(n); i ++){//只要有数能被 n 整除，就返回falseif(n % i == 0)return false;}//没有数能被n整除就返回truereturn true;}

小结： 暴力算法只适合单个或少量的素数判断，若判断某个范围之间有哪些素数，时间复杂度可能会达到 $\sqrt{n} )$ ，如下代码就会达到。

	//求 n 以内的所有素数for (int i = 2; i <= n; i++){if(isPrime(i))System.out.println(i);}

另外还有简单优化的方法，如：跳过偶数(2除外)的判断等就不再讲述

二、🍉 埃氏筛法 🍉

埃氏筛法是求 n 以内所有素数的方法，把不大于根号 n 的所有素数的倍数剔除，剩下的就是素数。方法及例子如下：

求 20 以内的所有素数：

列出 2 以后的所有序列：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
标记数列的第一个数为素数：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
划掉被标记的数的所有倍数：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2 3 5 7 9 11 13 15 17 19
标记剩下数列中当前标记的下一个数为素数，再次重复执行以上操作，最后标记的数应为 $\sqrt{n}$ （向下取整）：
2 3 5 7 9 11 13 15 17 19 标记 3
2 3 5 7 9 11 13 15 17 19 删除 3 的倍数
2 3 5 7 11 13 17 19 得到新的数列
2 3 5 7 11 13 17 19 下一个数 5 大于了 $\sqrt{n}$ ，就不用再标记了，当前数列已是结果
最后剩下的数都是 n 以内的素数：
2 3 5 7 11 13 17 19

说明：在暴力算法那里我们提到，判断素数只需要判断到是否能被 $\sqrt{n}$ 整除即可，所以在埃氏算法中，我们只需要标记到 $\sqrt{n}$ ，就能把所有非素数剔除

图解：我们可以借助一个 int 型数组，当前单元的值为 1 表示当前下标的数是素数，否则不是素数，我们是借助 0 来完成上面第三步的划掉倍数的操作。上面的例子最终得到的数组如下：
在这里插入图片描述

该图就表示：2 3 5 7 11 13 17 19 都是素数，其他都不是。虽然 0 和 1 下标上的元素也是 1，但我们可以控制下标从 2 开始，毕竟 2 是第一个素数

Java代码实现：

	/*** 埃氏筛法* @param n 要求的是 n 以内的素数* @return 返回 int 型数组，0 表示当前下标数字不是素数，1 则就是素数*/public static int[] sieve(int n){int[] arr = new int[n+1];// +1是为了让下标范围是 0 ~ n//让数组元素都为 1，即初始都为素数for (int i = 0; i <= n; i++)arr[i] = 1;//从 2 开始，若为素数就标记，并标记它的倍数不是素数for (int i = 2;i <= Math.sqrt(n); i++){//只需要标记到根号 n 即可if (arr[i] == 1){//素数才标记，因为当前位置可能是被标记的 0//j += i 控制 i 的倍数都被标记 0for (int j = 2 * i;j <= n;j += i){arr[j] = 0;}}}return arr;}

小结：埃氏筛法的时间复杂度为 $O (n * l o g n)$ ，相对于暴力算法有了优化，适用于 10 ⁶ 以内范围的数据处理。常见的应用有：n 以内范围的素数求总和、区间内的素数等

三、🍈 欧拉筛法 🍈

欧拉筛法是埃氏筛法的升级版。在埃氏筛法中，很多数都会被标记多次不是素数，例如 10 会在标记素数 2 、5 的时候都被标记不是素数，欧拉筛法则让每个数只被标记一次不是素数。使自身的时间复杂度达到线性的 $O (n)$ 。算法及例子如下，具体概念及证明就不在本文阐述，有兴趣的小伙伴可以去搜一下：

求 20 以内的所有素数：（红色表示素数，蓝色表示不是素数）

列出 2 以后的所有序列，初始都标记为素数：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
依次判断数列的每一个数，若为素数，则将其存放在一个数组中：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
依次标记当前数的所有已找到素数倍的数不是素数：（当前所有已找到素数只有 2，当前数为 2，那么标记 2 * 2 = 4 不是素数）
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
标记一次，就判断当前数是否是当前素数的倍数，是则停止标记非素数，进入到下一个数的判断（这是使每个数只被标记一次的关键）
重复以上操作，直到判断到最后一个数（20）：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 当前数为 3，是素数，先加入素数数组，当前素数有 2，3，则标记 6 和 9 不是素数
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 当前数为 4，不是素数，不加入数组，当前素数有 2，3，则标记 8 不是素数，因为４是２的倍数，就结束标记（否则会重复标记12），对应第４步，进入下一个数
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 当前数为 5，是素数，先加入数组，当前素数有 2，3，5，则标记 10 15 不是素数（25大于20，不用标记）
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 当前数为 6，不是素数，不加入数组，当前素数有 2，3，5，则标记 12 不是素数，因为 12 是 2 的倍数，就结束标记（可以看到前面阻止了对 12 的标记，避免和这里发生重复），进入下一个数
后续操作与同理，最后会发现每个数只被标记了一次。最终的数如下：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

说明：通过以上步骤可以得出，需要两个数组，一个存已找到的素数，一个标记各个数是否为素数的数组

Java代码实现：

	/*** 欧拉筛法求 n 以内的所有素数* @param isPrime 标记是否为素数的数组，1表示是素数，0则不是* @param prime 存放以求得的素数的数组* @param n 就是 n 本身* @return 返回一共有几个素数*/public static int euler(int[] isPrime,int[] prime,int n){int cnt = 0;    //记录素数个数//让所有数组元素都为 1，即初始都为素数for (int i = 0;i <= n;i++)isPrime[i] = 1;//从 2 开始，若为素数就标记，并标记当前数的所有已找到素数倍的数不是素数for (int i = 2; i <= n; i++){//当前数为素数，则加入素数数组，并使 cnt计数加一if (isPrime[i] == 1) prime[++cnt] = i;//标记当前数的所有已找到素数倍的数不是素数for (int j = 1;j <= cnt && i * prime[j] <= n; j++){int k = i * prime[j];isPrime[k] = 0;//判断当前数是否是当前素数的倍数，是则停止标记非素数，进入到下一个数的判断//这里是使复杂度降低在线性的关键if (i % prime[j] == 0) break;}}return cnt;}