朝阳区网站开发公司,宝塔 wordpress 多站点,自助建站 知乎,小红书推广费用前言#xff1a;素数判断是算法中重要的一环#xff0c;掌握优秀的素数判断方法是算法player的必修课。本文介绍的是由简到繁的素数算法#xff0c;便于初学者从入门到精通。 素数#xff08;质数#xff09;#xff1a;只能被 1 和它本身整除的数称作素数#xff0c;如… 前言素数判断是算法中重要的一环掌握优秀的素数判断方法是算法player的必修课。本文介绍的是由简到繁的素数算法便于初学者从入门到精通。 素数质数只能被 1 和它本身整除的数称作素数如2、3、5、7、11等 目录 一、 暴力算法 二、 埃氏筛法 三、 欧拉筛法 一、 暴力算法 暴力算法是利用循环看 2 − n 2 -n 2−n 之间是否有能被 n n n 整除的数若有则 n n n 就是素数否则就不是。 Java代码如下 时间复杂度为 O ( n ) O(n) 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 ( n ) O(\sqrt{n}) O(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;}小结 暴力算法只适合单个或少量的素数判断若判断某个范围之间有哪些素数时间复杂度可能会达到 O ( n n ) O(n \sqrt{n} ) O(nn ) 如下代码就会达到。 //求 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标记剩下数列中当前标记的下一个数为素数再次重复执行以上操作最后标记的数应为 n \sqrt{n} 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 大于了 n \sqrt{n} n 就不用再标记了当前数列已是结果最后剩下的数都是 n 以内的素数 2 3 5 7 11 13 17 19
说明在暴力算法那里我们提到判断素数只需要判断到是否能被 n \sqrt{n} n 整除即可所以在埃氏算法中我们只需要标记到 n \sqrt{n} 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[n1];// 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 ) O(n*log n) O(n∗logn)相对于暴力算法有了优化适用于 10 6 以内范围的数据处理。常见的应用有n 以内范围的素数求总和、区间内的素数等
三、 欧拉筛法 欧拉筛法是埃氏筛法的升级版。在埃氏筛法中很多数都会被标记多次不是素数例如 10 会在标记素数 2 、5 的时候都被标记不是素数欧拉筛法则让每个数只被标记一次不是素数。使自身的时间复杂度达到线性的 O ( n ) O(n) 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是素数先加入素数数组当前素数有 23则标记 6 和 9 不是素数 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 当前数为 4不是素数不加入数组当前素数有 23则标记 8 不是素数因为是的倍数就结束标记否则会重复标记12对应第步进入下一个数 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 当前数为 5是素数先加入数组当前素数有 235则标记 10 15 不是素数25大于20不用标记 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 当前数为 6不是素数不加入数组当前素数有 235则标记 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;}小结欧拉筛将复杂度降低到线性较于其他两种算法有了非常大的提升但是远不及埃氏筛法容易理解需要细细品味。但是算法嘛很多时候都是先背板子再刷题理解去掌握的多用就好了。
