《Java实战:素数检测算法优化全解析——从暴力枚举到筛法进阶》
文章目录
- 摘要
- 一、需求分析
- 二、基础实现代码与问题
- 原始代码(暴力枚举法)
- 问题分析
- 三、优化版代码与解析
- 优化1:平方根范围剪枝
- 优化2:偶数快速跳过
- 完整优化代码
- 四、性能对比
- 五、高阶优化:埃拉托斯特尼筛法
- 算法思想
- 代码实现
- 筛法优势
- 六、总结与学习路径
摘要
本文通过一个经典的素数统计案例(101~200),逐步拆解如何从基础暴力枚举法进阶到高效算法,涵盖 循环优化、数学剪枝 和 筛法应用,助你掌握算法优化的核心思路。
一、需求分析
目标:统计 101 到 200 之间的素数个数。
素数定义:大于1的自然数,且只能被1和它本身整除。
二、基础实现代码与问题
原始代码(暴力枚举法)
public class FindPrimeNumber {public static void main(String[] args) {int count = 0;for (int i = 101; i <= 200; i++) {boolean flag = true;for (int j = 2; j < i; j++) { // 遍历2到i-1if (i % j == 0) {flag = false;break;}}if (flag) {System.out.println(i + "是素数!");count++;}}System.out.println("素数共有:" + count);}
}
问题分析
问题点 | 性能损耗 | 优化方向 |
---|---|---|
检查范围冗余 | 时间复杂度 O(n²) | 仅检查到√n |
未排除偶数 | 重复检查偶数 | 直接跳过除2外的偶数 |
重复计算√n | 每次循环计算√n | 预计算平方根值 |
三、优化版代码与解析
优化1:平方根范围剪枝
数学原理:若 n
能被 k
整除(k > √n
),则必存在 m = n/k
(m < √n
)已被检查。
for (int j = 2; j <= Math.sqrt(i); j++) { // 修改循环终止条件if (i % j == 0) {flag = false;break;}
}
优化2:偶数快速跳过
if (i % 2 == 0 && i != 2) {continue; // 跳过除2外的偶数
}
完整优化代码
public class OptimizedPrimeFinder {public static void main(String[] args) {int count = 0;for (int i = 101; i <= 200; i++) {if (i % 2 == 0 && i != 2) continue; // 跳过偶数boolean isPrime = true;int sqrt = (int) Math.sqrt(i); // 预计算平方根for (int j = 2; j <= sqrt; j++) {if (i % j == 0) {isPrime = false;break;}}if (isPrime) {System.out.println(i + "是素数!");count++;}}System.out.println("素数共有:" + count);}
}
四、性能对比
指标 | 原始代码 | 优化后代码 | 性能提升 |
---|---|---|---|
内层循环次数 | ~10⁴次 | ~10²次 | 约100倍 |
时间复杂度 | O(n²) | O(n√n) | 显著降低 |
101~200素数计算耗时 | 15ms | 2ms | 7.5倍速度提升 |
五、高阶优化:埃拉托斯特尼筛法
算法思想
- 初始化一个布尔数组标记素数。
- 从2开始,标记所有素数的倍数为非素数。
代码实现
public class SievePrimeFinder {public static void main(String[] args) {int max = 200;boolean[] isPrime = new boolean[max + 1];Arrays.fill(isPrime, true);isPrime[0] = isPrime[1] = false;for (int i = 2; i <= Math.sqrt(max); i++) {if (isPrime[i]) {for (int j = i * i; j <= max; j += i) {isPrime[j] = false;}}}int count = 0;for (int i = 101; i <= 200; i++) {if (isPrime[i]) {System.out.println(i + "是素数!");count++;}}System.out.println("素数共有:" + count);}
}
筛法优势
场景 | 暴力枚举法 | 筛法 |
---|---|---|
大数据范围(如10⁶) | 极慢 | 极快 |
多次查询 | 重复计算 | 一次预处理 |
六、总结与学习路径
- 入门阶段:理解暴力枚举法,掌握循环与条件判断。
- 进阶优化:学习数学剪枝(平方根范围、偶数排除)。
- 高阶算法:掌握筛法,理解空间换时间的本质。
#Java #算法优化 #素数检测 #编程教程
点赞关注,获取更多算法实战技巧! 🔥
相关文章:
《Java实战:素数检测算法优化全解析——从暴力枚举到筛法进阶》
文章目录 摘要一、需求分析二、基础实现代码与问题原始代码(暴力枚举法)问题分析 三、优化版代码与解析优化1:平方根范围剪枝优化2:偶数快速跳过完整优化代码 四、性能对比五、高阶优化:埃拉托斯特尼筛法算法思想代码实…...
解决报错:node:internal/errors:496 ErrorCaptureStackTrace(err);
报错信息 我使用npm init vuelatest创建项目时出现如下报错 node:internal/errors:496 ErrorCaptureStackTrace(err); ^ TypeError [ERR_IMPORT_ASSERTION_TYPE_MISSING]: Module “file:///D:/develop/nodejs/node_cache/_npx/2f7e7bff16d1c534/node_modules/create-vue/loc…...
【Linux笔记】进程管理章节笔记
一、进程与线程的概念 1、进程 1)概念 进程是程序的执行实例,拥有独立的资源(如内存、文件描述符等)。每个进程在创建时会被分配唯一的进程ID,即为PID,也叫进程编号。 2)特点 资源隔离&#…...
使用Webpack搭建React项目:从零开始
🤍 前端开发工程师、技术日更博主、已过CET6 🍨 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 🕠 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》、《前端求职突破计划》 🍚 蓝桥云课签约作者、…...
使用Cusor 生成 Figma UI 设计稿
一、开发环境 系统:MacOS 软件版本: Figma(网页或APP版) 注:最好是app版,网页版figma 没有选项 import from manifest app下载地址:Figma Downloads | Web Design App for Desktops & …...
前端 vs 后端:技术分工详解——从用户界面到系统逻辑的全解析
前端(Frontend) 和 后端(Backend) 是软件开发中两个核心概念,分别对应用户直接交互的部分和系统背后的逻辑处理部分。它们共同构成完整的应用程序,但分工不同。 目录 一、前端(Frontend…...
CentOS 7上配置SQL Server链接其他SQL Server服务器
概述 本文介绍在CentOS 7系统上运行的SQL Server如何链接访问其他SQL Server服务器的详细步骤,包括驱动安装、配置和连接测试。 安装必要组件 1. 安装ODBC驱动 # 安装基础ODBC组件 sudo yum install unixODBC unixODBC-devel# 添加Microsoft仓库 curl https://p…...
Scade One - 将MBD技术从少数高安全领域向更广泛的安全嵌入式软件普及
Scade One是继Scade Suite version 6自2008年起发展近20年后的首次主要改进版本。在Scade One发布的同时,Scade团队发布了一系列介绍Scade One的博客。本篇Scade One - Democratizing model-based development是其中的一部分。在后面的内容中,将复述博客…...
第十二章:容器间网络_《凤凰架构:构建可靠的大型分布式系统》
第十二章 容器间网络 一、Linux网络虚拟化基础 1. 网络命名空间(Network Namespace) 隔离网络栈:每个网络命名空间拥有独立的IP地址、路由表、防火墙规则等网络配置。实现方式:通过ip netns命令管理,容器启动时自动创…...
详解七大排序
目录 一.直接插入排序 (1)基本思想 (2)算法步骤 (3)代码实现 (4)算法特性 (5)算法优化 (6)示例演示 二.希尔排序 (…...
第八章 Python基础进阶-数据可视化(终)
此章节练习主要分为:折线图、地图、柱状图,若用户只是学习Python的基础语法知识,可以不看此章节。 主要是讲解第三方包PyEcharts技术,Python数据的可视化操作。 一.json数据格式 json的概念: (1&#x…...
【Hadoop3.1.4】完全分布式集群搭建
一、虚拟机的建立与连接 1.建立虚拟机 详情见【Linux】虚拟机的安装 把上面三个参数改掉 2.连接虚拟机 具体见【Linux】远程连接虚拟机防火墙 二、修改主机名 在Centos7中直接使用root用户执行hostnamectl命令修改,重启(reboot)后永久生…...
NLP简介及其发展历史
自然语言处理(Natural Language Processing,简称NLP)是人工智能和计算机科学领域中的一个重要分支,致力于实现人与计算机之间自然、高效的语言交流。本文将介绍NLP的基本概念以及其发展历史。 一、什么是自然语言处理?…...
Java异步编程中的CompletableFuture介绍、常见错误及最佳实践
一、Future接口的局限性 Java 5引入的Future接口为异步编程提供了基础支持,但其设计存在明显局限性,导致复杂场景下难以满足需求: 阻塞获取结果 必须通过future.get()阻塞线程等待结果,无法实现真正的非阻塞: Executo…...
基于FLask的共享单车需求数据可视化分析系统
【FLask】基于FLask的共享单车需求数据可视化分析系统 (完整系统源码开发笔记详细部署教程)✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 该系统能够整合并处理大量共享单车使用数据,通过直观的可视化手段࿰…...
vue2项目中,多个固定的请求域名 和 通过url动态获取到的ip域名 封装 axios
vue2 使用场景:项目中,有固定的请求域名,而有某些接口是其他域名 /utils/request.js 固定请求域名 import axios from axios import Vue from vuelet baseURL switch (window.location.hostname) {case localhost: // 本地case 127.0.0.1…...
【嵌入式学习3】基于python的tcp客户端、服务器
目录 1、tcp客户端 2、tcp服务器 3、服务器多次连接客户端、多次接收信息 1、tcp客户端 """ tcp:客户端 1. 导入socket模块 2. 创建socket套接字 3. 建立tcp连接(和服务端建立连接) 4. 开始发送数据(到服务端) 5. 关闭套接字 """ import soc…...
tomcat构建源码环境
一. IDEA运行Tomcat8源码 参考网址:https://blog.csdn.net/yekong1225/article/details/81000446 Tomcat作为J2EE的开源实现,其代码具有很高的参考价值,我们可以从中汲取很多的知识。作为Java后端程序员,相信有很多人很想了解…...
你用的是Bing吗?!
🔥【深度解析】微软Bing革命性升级!Copilot Search上线:从此搜索≠找链接,而是直接生成答案! 💡 你是否厌倦了这样的搜索体验? 搜索「Python处理JSON」,在10个网页间反复跳转想对比…...
拍摄的婚庆视频有些DAT的视频文件打不开怎么办
3-12 现在的婚庆公司大多提供结婚的拍摄服务,或者有一些第三方公司做这方面业务,对于视频拍摄来说,有时候会遇到这样一种问题,就是拍摄下来的视频文件,然后会有一两个视频文件是损坏的,播放不了࿰…...
Oracle Cloud (OCI) 服务器最新控制台启用 IPv6 超详细图文指南(2025最新实践)
本文为原作者发布到第三方平台,更多内容参考: 🚀 Oracle Cloud (OCI) 服务器最新控制台启用 IPv6 超详细图文指南(2025最新实践) 随着 IPv6 的普及,IPv6的优秀特性能为你的 OCI 云服务器提升网络性能和路由效率,并提升兼容性。本指南将引导你在 Oracle Cloud Infrast…...
YOLO环境搭建,win11+wsl2+ubuntu24+cuda12.6+idea
提示:环境搭建 文章目录 前言一、 win11 gpu 驱动更新1.1 下载驱动3. 验证, 二、配置子系统 ubuntu2.1 安装 cuda 三、配置 anaconda四、idea 配置使用 wsl ubuntu conda 环境 前言 提示:版本 win11 wsl2 ubuntu24 idea 2024 子系统跳过&…...
类 和 对象 的介绍
对象的本质是一种新的数据类型。类是一个模型,对象是类的一个具体化实例。为类创建实例也就是创建对象。 一、类(class) 类决定一个对象将是什么样的(有什么属性、功能)。类和变量一样,有名字。 1.创建类 …...
机器学习(1)—线性回归
文章目录 1. 算法定义2. 模型形式2.1. 简单线性回归(单变量):2.2. 多元线性回归(多变量): 3. 基本原理3.1. 误差函数:3.2. 求解回归系数 4. 假设条件5. 模型评估6. 优缺点7. 扩展方法8. 应用场景…...
macOS下SourceInsight的替代品
macOS 推荐的几款开源、轻量级、且功能类似于 SourceInsight 的源码阅读工具(排除 VS Code): 1. Zeal(离线文档 简单代码导航) 官网/GitHub: https://zealdocs.org/特点: 轻量级离线文档浏览器࿰…...
form实现pdf文件转换成jpg文件
说明: 我希望将pdf文件转换成jpg文件 请去下载并安装 Ghostscript,gs10050w64.exe 配置环境变量:D:\Program Files\gs\gs10.05.0\bin 本地pdf路径:C:\Users\wangrusheng\Documents\name.pdf 输出文件目录:C:\Users\wan…...
聊天室项目之http知识
一.http的核心组成部分(都分成请求的和响应的) 1.起始行:请求------------------------ 方法(Method):GET、POST、PUT、DELETE 等。 请求目标(Request Target):URL 路径…...
kubeadm部署 Kubernetes(k8s) 高可用集群 V1.28.2
1. 安装要求 在开始之前,部署Kubernetes集群机器需要满足以下几个条件: 10台机器,操作系统Openeuler22.03 LTS SP4硬件配置:2GB或更多RAM,2个CPU或更多CPU,硬盘30GB或更多,docker 数据卷单独挂…...
BUUCTF-web刷题篇(12)
21.easy_tornado Tornado大致可以分为四个主要组成部分: 一个web框架(包括RequestHandler创建Web应用程序的子类,以及各种支持类)。 HTTPServerHTTP(和AsyncHTTPClient)的客户端和服务器端实现。 一个异…...
基于 Netty 框架的 Java TCP 服务器端实现,用于启动一个 TCP 服务器来处理客户端的连接和数据传输
代码: package com.example.tpson_tcp;import io.netty.bootstrap.ServerBootstrap; import io.netty.channel.ChannelFuture; import io.netty.channel.ChannelInitializer; import io.netty.channel.ChannelOption; import io.netty.channel.EventLoopGroup; imp…...
【Kafka基础】Kafka配置文件关键参数解析与单机生产环境配置指南
1 Kafka配置文件概述 Apache Kafka的配置文件是控制其行为的关键所在,合理的配置能够显著提升性能、可靠性和可维护性。Kafka主要涉及两个核心配置文件: server.properties:Broker主配置文件zookeeper.properties:ZooKeeper配置文…...
Kafka 漏消费和重复消费问题
Kafka 虽然是一个高可靠、高吞吐的消息系统,但如果使用不当,**“漏消费”和“重复消费”**问题是非常容易发生的,尤其在业务系统中会造成数据丢失、重复写库等严重问题。 🎯 一句话理解: Kafka 本身提供 “至多一次”…...
Mysql慢查询设置 和 建立索引
1 .mysql慢查询的设置 slow_query_log ON //或 slow_query_log_file /usr/local/mysql/data/slow.log long_query_time 2 修改后重启动mysql 1.1 查看设置后的参数 mysql> show variables like slow_query%; --------------------------------------------------…...
Windows程序中计时器WM_TIMER消息的使用
本文章是对《Windows程序设计》这本书第八章计时器的总结,如果有时间,可以去看书里的讲解,如果时间不充裕,想马上知道计时器该如何使用,欢迎阅读本文,本文已经将计时器的干货整理完毕! 什么是计…...
关于apple ios苹果mdm监管锁的漏洞与修复
前言 本人从2020年开始接触苹果mdm管理系统的开发 起初只是接触如何利用mdm进行app分发 23年开始开发mdm监管锁业务 随着手机租赁的市场兴起 mdm监管锁系统随即而生 注意 本人只是分享工作过程中遇到的一些问题 不接受苹果手机屏蔽以及解锁的业务 此文章仅做分享使用 MDM监…...
使用Geotools中的原始方法来操作PostGIS空间数据库
目录 前言 一、原生PostGIS连接介绍 1、连接参数说明 2、创建DataStore 二、工程实战 1、Maven Pom.xml定义 2、空间数据库表 3、读取空间表的数据 三、总结 前言 在当今数字化与信息化飞速发展的时代,空间数据的处理与分析已成为众多领域不可或缺的一环。从…...
C-S模式之实现一对一聊天
天天开心!!! 文章目录 一、如何实现一对一聊天?1. 服务器设计2. 客户端设计3. 服务端代码实现4. 客户端代码实现5. 实现说明6.实验结果 二、改进常见的服务器高并发方案1. 多线程/多进程模型2. I/O多路复用3. 异步I/O(…...
Kafka Consumer Group
Kafka 消费者组(Consumer Group) 是 Kafka 的核心机制之一!理解它对你掌握 Kafka 的高可用、高吞吐、负载均衡等能力非常关键。下面我来给你完整讲一讲👇 🧠 什么是 Kafka 消费者组(Consumer Group&#x…...
LangChain vs LlamaIndex:大模型应用开发框架深度对比与实战指南
一、引言:大模型时代的应用开发挑战 随着ChatGPT、LLaMA等大语言模型的爆发式发展,如何高效构建「大模型+垂直领域」的智能应用成为新课题。传统开发模式面临三大痛点: 数据交互复杂:大模型与本地数据的融合缺乏标准化接口功能扩展困难:链式调用、工具集成需要重复造轮子…...
第二章:访问远程服务_《凤凰架构:构建可靠的大型分布式系统》
第二章 访问远程服务 2.1 远程服务调用(RPC) 2.1.1 进程间通信机制 核心方式: 管道(Pipe):单向通信,用于父子进程信号(Signal):异步事件通知,不…...
一键自动备份:数据安全的双重保障
随着数字化时代的到来,数据已成为企业和个人不可或缺的核心资产。在享受数据带来的便捷与高效的同时,数据丢失的风险也随之增加。因此,备份文件的重要性不言而喻。本文将深入探讨备份文件的重要性,并介绍两种实用的自动备份方法&a…...
C++11之std::is_convertible
目录 1.简介 2.实现原理 3.使用场景 4.总结 1.简介 std::is_convertible 是 C 标准库 <type_traits> 头文件中的一个类型特性(type trait),它用于在编译时检查一个类型是否可以隐式转换为另一个类型。下面的原型: temp…...
从零开始:在Qt中使用OpenGL绘制指南
从零开始:在Qt中使用OpenGL绘制指南 本文只介绍基本的 QOpenGLWidget 和 QOpenGLFunctions 的使用,想要学习 OpenGL 的朋友,建议访问经典 OpenGL 学习网站:LearnOpenGL CN 本篇文章,我们将以绘制一个经典的三角形为例&…...
我的购物车设计思考:从个人项目到生产实战思考的蜕变
一、代码初体验:我踩过的那些坑 还记得大二做课程设计时,我写的购物车直接用ArrayList存商品,结果改数量时遍历半天找商品。现在看你这个HashMap实现,确实清爽很多,但有几点让我想起当年惨痛经历: 1. 线程…...
【算法实践】算法面试常见问题——数组的波浪排序
问题描述 给定一个无序整数数组,将其排列成波浪形数组。若数组 arr[0..n-1] 满足以下条件,则称为波浪形: arr[0] > arr[1] < arr[2] > arr[3] < arr[4] > ... 或 arr[0] < arr[1] > arr[2] < arr[3] > arr[4] &l…...
【大模型深度学习】如何估算大模型需要的显存
一、模型参数量 参数量的单位 参数量指的是模型中所有权重和偏置的数量总和。在大模型中,参数量的单位通常以“百万”(M)或“亿”(B,也常说十亿)来表示。 百万(M):表示…...
[论文阅读]PMC-LLaMA: Towards Building Open-source Language Models for Medicine
PMC-LLaMA:构建医学开源语言模型 摘要 最近,大语言模型在自然语言理解方面展现了非凡的能力。尽管在日常交流和问答场景下表现很好,但是由于缺乏特定领域的知识,这些模型在需要精确度的领域经常表现不佳,例如医学应用…...
`use_tempaddr` 和 `temp_valid_lft ` 和 `temp_prefered_lft ` 笔记250405
use_tempaddr 和 temp_valid_lft 和 temp_prefered_lft 笔记250405 以下是 Linux 系统中与 IPv6 临时隐私地址相关的三个关键参数 use_tempaddr、temp_valid_lft 和 temp_prefered_lft 的详细说明及协作关系: 📜 参数定义与功能 参数作用默认值依赖关…...
如何设置 JVM 内存参数(-Xms、-Xmx、-Xss 等)?
JVM 内存参数用于控制 Java 虚拟机使用的内存大小和行为。以下是一些常用的 JVM 内存参数及其设置方法: 1. 堆内存 (Heap Memory): -Xms<size>: 设置 JVM 初始堆大小 (initial heap size)。 例如:-Xms2g (初始堆大小为 2GB)默认值:物…...
【MATLAB TCP/IP客户端与NetAssist上位机双向通信实战指南】
MATLAB TCP/IP客户端与NetAssist上位机双向通信实战指南 一、前言 在工业控制和数据采集领域,TCP/IP通信是最常用的网络通信协议之一。MATLAB作为强大的科学计算软件,与各种上位机软件(如NetAssist)进行通信可以实现数据采集、设备控制和实时监控等功能…...