统计找出一千万以内，一共有多少质数?（优化过程，效率更快）

2024-07-06 04:55| 来源: 网络整理| 查看: 265

质数概念: 只能被1和自己整除的数

初步思路

**：运用双层循环，判断是否为质数，true则num+1；false跳过

代码如下：

package somethings; import java.util.Locale; /** * @author Small_Tsky * @date 2020/2/23 - 16:21 **/ public class Unimportance { public static void main(String[] args) { long start = System.currentTimeMillis(); int n = 10000000 ; // 初始化num (因为2为质数未被计入for循环里） int num = 1; for (int i = 3; i // i除1和本身没有其他的因子，即为质数 if (i % j != 0) { num++; } } } System.out.println("一千万以内的质数个数为："+num); long end = System.currentTimeMillis(); System.out.println("所用时间："+(end - start)+"毫秒"); } }

运行结果：无

数据过于庞大，运算次数要循环1+2+…+（10000000-2）次。这个算法的时间复杂度是：O( N 2 N^2 N2)。每秒十亿指令的计算器运行时间复杂度为 n 2 n^2 n2，其中n= 1 0 6 10^6 106，所运行的时间为16.67min，而运行一千万则需要的时间为1667min，即27.8h，所以要等到结果出来需要等上一天多。

-------------------------------------------------------------------

如果复杂度是 N 2 N^2 N2,要下意识将复杂度改为 N l o g N NlogN NlogN,所以下面需要做的就是优化优化思路：

优化思路：

对于确定的质数先做标记，标记完成后，遍历标记的质数，num++；

代码如下：

import java.util.Arrays; /** * @author Small_Tsky * @date 2020/2/23 - 16:25 **/ public class Isprimes { public static void main(String[] args) { long start = System.currentTimeMillis(); int n = 10000000 +1;// 下标从1开始 int num = 0; boolean [] isprimes = new boolean[n]; // 定义isprimes[] Arrays.fill(isprimes,true); for (int i = 2; i // 标记不符合条件的num，即有因子的全部标记false； isprimes[i * j] = false; } } isprimes[1]=false;//注意：1为非质数 // 遍历isprimes[] for (int i = 1; i num++; } } long end = System.currentTimeMillis(); System.out.println("一千万以内的质数一共有 " + num + " 个"); System.out.println("所用时间为 " + (int) (end - start)+"毫秒"); } }

运行结果：

一千万以内的质数一共有 664579 个所用时间为 985毫秒 Process finished with exit code 0

此算法的时间复杂度是：O（NlogN)

----------------------------------------------------------------------- 前辈思路（埃氏筛法）：

埃拉托斯特尼筛法：简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

思想实现：要得到自然数n以内的全部素数，必须把不大于的所有素数的倍数剔除，剩下的就是素数。给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去…。

代码如下：

package arrylist; import property.Item; import java.util.Arrays; /** * @author Small_Tsky * @date 2020/2/23 - 16:30 **/ public class list { public static void main(String[] args) { long start = System.currentTimeMillis(); int n = 10000000 + 1; //总数，下标从1开始 boolean[] data = new boolean[n]; //存储是否为质数的容器 Arrays.fill(data, true); // 先假设都是质数 for (int i = 1; i data[i] = false; // 先将为偶数排除 } } data[2] = true;// 2为质数 data[1] = false;//注意：1不是质数 for (int i = 2; i // 这里的i为非偶数（上一步已经把偶数排除了），剩下只有非偶数 // 非偶数的平方为非质数，其平方的倍数也一定是非质数 for (int j = i * i; j if (data[i]) { num++; // 为质数则+1 } } long end = System.currentTimeMillis(); System.out.println("一千万以内的质数一共有 " + num + " 个"); System.out.println("所用时间为 " + (int) (end - start) + "毫秒"); } }

运行结果：

一千万以内的质数一共有 664579 个所用时间为 98毫秒

此算法的时间复杂度是：O(N)

#第三种结果比第二种结果足足快了800多毫秒#

所以时间复杂度越小越好，但是如果算法效率过高的话，很有可能出现错误

【本文地址】

公司简介

联系我们