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

2024-01-11 05:08

本文主要是介绍统计找出一千万以内,一共有多少质数?(优化过程,效率更快),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

质数概念: 只能被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 <= n; i++) {for (int j = 2; j <i ; j++) {
//                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 <= isprimes.length; i++) {for (int j = 2; i * j < isprimes.length; j++) {
//                        标记不符合条件的num,即有因子的全部标记false;isprimes[i * j] = false;}}isprimes[1]=false;//注意:1为非质数//                  遍历isprimes[]for (int i = 1; i <isprimes.length ; i++) {if (isprimes[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.length; i++) {    //  遍历容器if (i % 2 == 0) {data[i] = false;    //  先将为偶数排除}}data[2] = true;//  2为质数data[1] = false;//注意:1不是质数for (int i = 2; i <= Math.sqrt(n); i++) {   //优化:只需考虑根号n以内的数的倍数if (data[i]) {  //    这里的i为非偶数(上一步已经把偶数排除了),剩下只有非偶数//  非偶数的平方为非质数,其平方的倍数也一定是非质数for (int j = i * i; j < n; j += 2 * i) {   data[j] = false;    //优化:如果一个数(i * i)不是质数,那么它的倍数(i*i+2*i)一定不是质数}}}int num = 0;    //  计数质数总数for (int i = 1; i < data.length; i++) {if (data[i]) {num++;  //  为质数则+1}}long end = System.currentTimeMillis();System.out.println("一千万以内的质数一共有 " + num + " 个");System.out.println("所用时间为 " + (int) (end - start) + "毫秒");}
}

运行结果:

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

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

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

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

这篇关于统计找出一千万以内,一共有多少质数?(优化过程,效率更快)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/593255

相关文章

Java进程异常故障定位及排查过程

《Java进程异常故障定位及排查过程》:本文主要介绍Java进程异常故障定位及排查过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、故障发现与初步判断1. 监控系统告警2. 日志初步分析二、核心排查工具与步骤1. 进程状态检查2. CPU 飙升问题3. 内存

SpringBoot整合liteflow的详细过程

《SpringBoot整合liteflow的详细过程》:本文主要介绍SpringBoot整合liteflow的详细过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋...  liteflow 是什么? 能做什么?总之一句话:能帮你规范写代码逻辑 ,编排并解耦业务逻辑,代码

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

MyBatisPlus如何优化千万级数据的CRUD

《MyBatisPlus如何优化千万级数据的CRUD》最近负责的一个项目,数据库表量级破千万,每次执行CRUD都像走钢丝,稍有不慎就引起数据库报警,本文就结合这个项目的实战经验,聊聊MyBatisPl... 目录背景一、MyBATis Plus 简介二、千万级数据的挑战三、优化 CRUD 的关键策略1. 查

MySQL中的InnoDB单表访问过程

《MySQL中的InnoDB单表访问过程》:本文主要介绍MySQL中的InnoDB单表访问过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、访问类型【1】const【2】ref【3】ref_or_null【4】range【5】index【6】

浏览器插件cursor实现自动注册、续杯的详细过程

《浏览器插件cursor实现自动注册、续杯的详细过程》Cursor简易注册助手脚本通过自动化邮箱填写和验证码获取流程,大大简化了Cursor的注册过程,它不仅提高了注册效率,还通过友好的用户界面和详细... 目录前言功能概述使用方法安装脚本使用流程邮箱输入页面验证码页面实战演示技术实现核心功能实现1. 随机

在Linux终端中统计非二进制文件行数的实现方法

《在Linux终端中统计非二进制文件行数的实现方法》在Linux系统中,有时需要统计非二进制文件(如CSV、TXT文件)的行数,而不希望手动打开文件进行查看,例如,在处理大型日志文件、数据文件时,了解... 目录在linux终端中统计非二进制文件的行数技术背景实现步骤1. 使用wc命令2. 使用grep命令

Navicat数据表的数据添加,删除及使用sql完成数据的添加过程

《Navicat数据表的数据添加,删除及使用sql完成数据的添加过程》:本文主要介绍Navicat数据表的数据添加,删除及使用sql完成数据的添加过程,具有很好的参考价值,希望对大家有所帮助,如有... 目录Navicat数据表数据添加,删除及使用sql完成数据添加选中操作的表则出现如下界面,查看左下角从左

CSS3打造的现代交互式登录界面详细实现过程

《CSS3打造的现代交互式登录界面详细实现过程》本文介绍CSS3和jQuery在登录界面设计中的应用,涵盖动画、选择器、自定义字体及盒模型技术,提升界面美观与交互性,同时优化性能和可访问性,感兴趣的朋... 目录1. css3用户登录界面设计概述1.1 用户界面设计的重要性1.2 CSS3的新特性与优势1.

canal实现mysql数据同步的详细过程

《canal实现mysql数据同步的详细过程》:本文主要介绍canal实现mysql数据同步的详细过程,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的... 目录1、canal下载2、mysql同步用户创建和授权3、canal admin安装和启动4、canal