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

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

相关文章

SpringBoot中六种批量更新Mysql的方式效率对比分析

《SpringBoot中六种批量更新Mysql的方式效率对比分析》文章比较了MySQL大数据量批量更新的多种方法,指出REPLACEINTO和ONDUPLICATEKEY效率最高但存在数据风险,MyB... 目录效率比较测试结构数据库初始化测试数据批量修改方案第一种 for第二种 case when第三种

MySQL深分页进行性能优化的常见方法

《MySQL深分页进行性能优化的常见方法》在Web应用中,分页查询是数据库操作中的常见需求,然而,在面对大型数据集时,深分页(deeppagination)却成为了性能优化的一个挑战,在本文中,我们将... 目录引言:深分页,真的只是“翻页慢”那么简单吗?一、背景介绍二、深分页的性能问题三、业务场景分析四、

Linux进程CPU绑定优化与实践过程

《Linux进程CPU绑定优化与实践过程》Linux支持进程绑定至特定CPU核心,通过sched_setaffinity系统调用和taskset工具实现,优化缓存效率与上下文切换,提升多核计算性能,适... 目录1. 多核处理器及并行计算概念1.1 多核处理器架构概述1.2 并行计算的含义及重要性1.3 并

Spring boot整合dubbo+zookeeper的详细过程

《Springboot整合dubbo+zookeeper的详细过程》本文讲解SpringBoot整合Dubbo与Zookeeper实现API、Provider、Consumer模式,包含依赖配置、... 目录Spring boot整合dubbo+zookeeper1.创建父工程2.父工程引入依赖3.创建ap

Linux下进程的CPU配置与线程绑定过程

《Linux下进程的CPU配置与线程绑定过程》本文介绍Linux系统中基于进程和线程的CPU配置方法,通过taskset命令和pthread库调整亲和力,将进程/线程绑定到特定CPU核心以优化资源分配... 目录1 基于进程的CPU配置1.1 对CPU亲和力的配置1.2 绑定进程到指定CPU核上运行2 基于

PowerShell中15个提升运维效率关键命令实战指南

《PowerShell中15个提升运维效率关键命令实战指南》作为网络安全专业人员的必备技能,PowerShell在系统管理、日志分析、威胁检测和自动化响应方面展现出强大能力,下面我们就来看看15个提升... 目录一、PowerShell在网络安全中的战略价值二、网络安全关键场景命令实战1. 系统安全基线核查

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. 查