当前位置：首页 > news >正文

判断质数及其优化方法

news 来源：原创 2025/7/13 4:39:34

判断质数（素数）及其优化方法

质数是指 大于1的自然数，且 只有1和它本身两个正约数。以下是几种判断方法及其优化策略。

基础方法（试除法）

检查从 2 到 n-1 的所有整数，若存在能整除 n 的数，则 n 不是质数。

代码实现

bool isPrime(int n) {if (n <= 1) return false;for (int i = 2; i < n; i++) {if (n % i == 0) return false;}return true;
}

最简单直接的方法，时间复杂度：O(n)，仅适用于学习，实际效率低

优化1：仅检查到√n

数学原理
若n不是质数，则必有一个因数≤√n

bool isPrimeSqrt(int n) {if (n <= 1) return false;for (int i = 2; i * i <= n; i++) {if (n % i == 0) return false;}return true;
}

时间复杂度：O(√n)，最常用的单次判断方法

优化2：跳过偶数

除了 2，所有偶数都不是质数，因此可以跳过所有偶数。

bool isPrime(int n) {if (n <= 1) return false;if (n == 2) return true;      // 2 是质数if (n % 2 == 0) return false; // 排除所有偶数for (int i = 3; i * i <= n; i += 2) { // 只检查奇数if (n % i == 0) {return false;}}return true;
}

时间复杂度：O(√n/2)

方法4：6k±1法则（高级优化）

bool isPrime(int n) {if (n <= 1) return false;if (n <= 3) return true;if (n % 2 == 0 || n % 3 == 0) return false;for (int i = 5; i * i <= n; i += 6) {if (n % i == 0 || n % (i + 2) == 0) return false;}return true;
}

基于数学定理：质数呈6k±1分布，时间复杂度：O(√n/3)，最高效的单次判断方法

方法5：筛法预处理（适合多次查询）

#include <vector>
using namespace std;vector<bool> sieve(int max_num) 
{vector<bool> is_prime(max_num + 1, true);is_prime[0] = is_prime[1] = false;for (int i = 2; i * i <= max_num; i++)  {if (is_prime[i]) {for (int j = i * i; j <= max_num; j += i) //i如果是质数，那么i*i就肯定不是质数{is_prime[j] = false;}}}return is_prime;
}int main() {int max_num = 100;vector<bool> is_prime = sieve(max_num); //调用sieve得到一个标记了质数的数组，可以用O(1)的时间复杂度判断一个数是否为质数int num = 17;cout << num << (is_prime[num] ? " 是质数" : " 不是质数") << endl;return 0;
}

筛法中为什么要标记`ii`而不是`i2`或者`i*3`

关键推论：当处理到质数i时：i*2, i*3,..., i*(i-1)都已被更小的质数标记过（避免重复标记）

举例说明：

以n=30为例，标记过程对比：
从i*i开始的标记顺序：
i=2: 4,6,8,10,12,14,16,18,20,22,24,26,28,30
i=3: 9,15,21,27
i=5: 25
（共标记14次）

从i*2开始的标记顺序：
i=2: 4,6,8,…,30
i=3: 6,9,12,…,30（其中6,12,18…已标记）
i=5: 10,15,20,25,30（其中10,15,20,30已标记）
（共标记25次，其中11次是重复的）

当n=1,000,000时：
优化版：约执行800,000次标记
非优化版：约执行1,500,000次标记
（节省近50%的操作）

判断质数及其优化方法

判断质数（素数）及其优化方法质数是指大于1的自然数，且只有1和它本身两个正约数。以下是几种判断方法及其优化策略。目录基础方法（试除法）优化1：仅检查到√n优化2：跳过偶数优化3&#xff…...

编程日记 2025/7/13 4:39:34

【源码阅读/Vue Flask前后端】简历数据查询功能

目录一、Flask后端部分modelServiceroute 二、Vue前端部分index.js main.vue功能界面templatescriptstyle 一般就是三个层面，model层面用来建立数据库的字段，service用来对model进行操作，写一些数据库操作的代码，route就是具体的…...

编程日记 2025/7/13 3:56:33

R语言对偏态换数据进行转换（对数、平方根、立方根）

我们进行研究的时候经常会遇见偏态数据，数据转换是统计分析和数据预处理中的一项基本技术。使用 R 时，了解如何正确转换数据有助于满足统计假设、标准化分布并提高分析的准确性。在 R 中实现和可视化最常见的数据转换：对数、平方根和立方根转…...

编程日记 2025/7/11 11:04:18

链表（C++）

这是本人第二次学习链表，第一次学习链表是在大一上的C语言课上，首次接触，感到有些难；第二次是在大一下学习数据结构时（就是这次），使用C再次理解链表。同时，这也是开启数据结构学习写…...

编程日记 2025/7/12 5:50:31

算法-前缀和与差分

一、前缀和（Prefix Sum） 1. 核心思想前缀和是一种预处理数组的方法，通过预先计算并存储数组的前缀和，使得后续的区间和查询可以在**O(1)**时间内完成。 2. 定义给定数组 nums，前缀和数组 prefixSum 的每个元素 p…...

编程日记 2025/7/10 1:22:51

网关接口超时？用Java实现接口快速返回，后台继续执行的方法

网关接口超时？用Java实现接口快速返回，后台继续执行的方法在开发过程中，我们经常会遇到网关接口由于超时限制而导致请求失败的情况。然而，有些接口本身就需要较长时间来执行任务，这时我们不能简单地增加超时时间&…...

编程日记 2025/7/10 12:11:29

HTTP---基础知识

天天开心！！！ 文章目录一、HTTP基本概念1. 什么是HTTP，又有什么用？2. 一次HTTP请求的过程3.HTTP的协议头4.POST和GET的区别5. HTTP状态码6.HTTP的优缺点二、HTTP的版本演进1.各个版本的应用场景2、注意要点三、HTTP与…...

编程日记 2025/7/8 23:31:14

python基础学习三（元组及字符串的使用）

文章目录元组什么是元组元组的创建方式为什么要将元组设计成不可变序列元组的遍历集合集合的相关操作集合操作集合的数学操作集合生成式列表，字典，元组，集合总结字符串字符串的驻留机制判断字符串的操作方法字符串的比较操作字符串的切片操…...

编程日记 2025/7/10 16:05:18

c#winform，倒鸭子字幕效果，typemonkey字幕效果，抖音瀑布流字幕效果

不废话直接上效果图 C# winform 开发抖音的瀑布流字幕。也是typemonkey插件字幕效果或者咱再网上常说的倒鸭子字幕效果主要功能 1，软件可以自定义添加字幕内容 2，软件可以添加字幕显示的时间区间 3，可以自定义字幕颜色，可以随…...

编程日记 2025/7/9 5:23:11

1、C51单片机(STC8G2K64S4)串口实验

一、串口1接线图 1、下面是单片机外接电路图，P30,P31分别用于RXD和TXD功能引脚 2、我们来查看单片机手册串口1需要设置的寄存器串口1的功能脚配置选择位，看电路图选择的是P3.0,P3.1。 3、串口1：SCON控制寄存器设置为0x50:0101 0000。&a…...

编程日记 2025/7/10 15:31:58

ue材质学习感想总结笔记

2025 - 3 - 27 1.1 加法对TexCoord上的每一个像素加上一个值，如果加上0.1，0.1， 那么左上角原来0,0的位置变成了0.1,0.1 右上角就变成了1.1,1.1，那么原来0,0的位置就去到了左上角左上边，所以图像往左上偏移。总而言…...

编程日记 2025/7/5 16:06:58

MFC TRACE 宏的使用说明

书籍：《Visual C 2017从入门到精通》的2.7 字符串环境：visual studio 2022 内容：几个字符串类型->（将单字节char*转换为宽字节wchar_t *）（将宽字节wchar_t* 转换为单字节char *） 问题&am…...

编程日记 2025/7/9 1:40:05

1、基本结构 \documentclass[a4paper, 12pt]{article} %文档类型 \begin{document}\title{My First Document}\author{My Name}\date{\today}\maketitleA sentence of text. \end{document}2、带有章、节、小节的结构 \documentclass[a4paper, 12pt]{article}\begin{document…...

编程日记 2025/7/11 7:27:05

Unity编辑器功能及拓展(3) —[Attribute]特性

在 Unity 中，[Attribute]格式的特性是用于扩展编辑器功能、控制序列化行为和调整 Inspector 显示,进行编辑器拓展的核心工具。一.基础编辑器拓展 1.基础序列化控制 1.[SerializeField] 强制显示私有变量到Inspector 2.[HideInInspector] 隐藏该字段在Inspect…...

编程日记 2025/6/28 6:22:00

Rust基础语法

以下是 Rust 语言基础语法的核心要点，结合与 JavaScript 的对比，帮助前端开发者快速掌握核心概念： 一、变量与常量 1. 变量声明 Rust：变量默认不可变，需用 mut 显式声明可变性。let x 5; // 不可变变量 le…...

编程日记 2025/7/12 20:09:30

＜tauri＞＜rust＞＜GUI＞基于rust和tauri，实现一个大寰电爪PGHL（串口设备）定制化控制程序

前言本文是基于rust和tauri，由于tauri是前、后端结合的GUI框架，既可以直接生成包含前端代码的文件，也可以在已有的前端项目上集成tauri框架，将前端页面化为桌面GUI。环境配置系统：windows 10平台：visual studio code语言：rust、javascript库：tauri2.0概述本文是…...

编程日记 2025/7/9 15:05:11

Sentinel 相关知识点

Sentinel 实现原理？ Sentinel 是面向分布式服务架构的流量控制组件，主要以流量为切入点，从限流、流量整形、熔断降级、系统负载保护等多个维度来帮助开发者保障微服务的稳定性。以下是 Sentinel 的实现原理： 核心概念资源&…...

编程日记 2025/7/10 4:51:03

DFS飞机降落

问题描述 NN 架飞机准备降落到某个只有一条跑道的机场。其中第 ii 架飞机在 TiTi 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 DiDi 个单位时间，即它最早可以于 TiTi 时刻开始降落，最晚可以于 TiDiTiDi 时刻开始降落。降落…...

编程日记 2025/7/9 23:28:40

SpringCould微服务架构之Docker（5）

Docker的基本操作： 镜像相关命令： 1.镜像名称一般分两部分组成：[repository]:[tag]。 2. 在没有指定tag时，默认是latest，代表着最新版本的镜像。镜像命令的案例： 镜像操作常用的命令： dock…...

编程日记 2025/7/12 21:44:11

音乐webpack（通杀webpack-1）

本文章中所有内容仅供学习交流使用，不用于其他任何目的，不提供完整代码，抓包内容、敏感网址、数据接口等均已做脱敏处理，严禁用于商业用途和非法用途，否则由此产生的一切后果均与作者无关！ 本文章未经许可…...

编程日记 2025/7/5 9:53:18

数据结构与算法——顺序表之手撕OJ题

文章目录一、前言二、拿捏OJ题2.1移除元素2.2删除有序数组中的重复项2.3合并两个有序数组三、总结一、前言 Do you study today?up在上一次已经讲解完毕了有关顺序表的所有知识，不知道大家是否已经沉淀完毕了呢？有一句老话说得好啊——光看不练假把…...

编程日记 2025/6/28 4:40:15

减少采样空间方法变成后验概率

又因为后验概率很难计算 --所以通过引入变分分布来近似后验概率分布同时引入 kl散度来度量近似的效果好不好什么是kl散度 kl散度带变分： 第一个问题 ：积分变期望问题二：贝叶斯公式第三个问题：为啥可以独立出来因为相比…...

编程日记 2025/6/28 1:33:41

如何使用K8S快速部署测试环境

目录一、Windows 系统使用 Rancher Desktop 二、Linux系统集群使用 Ansible 一键部署三、Linux系统使用 kubeadm 快速搭建单节点集群四、Kubernetes (K8S) 快速部署测试环境 4.1 准备 K8S 集群 4.2部署测试应用 4.3访问测试服务 4.4持久化存储（可选&…...

编程日记 2025/7/11 18:43:32

GAMES101-现代计算机图形学入门（Animation/simulation）

目录一些科普Keyframe AnimatorPhysical Simulation质点弹簧系统 Mass Spring Rope粒子系统运动学 Forward Kinematics逆运动学Inverse KinematicsRiggingMotion Capture 第二次课 cont.Single Particle Simulation流体模拟 Fluid Simulation GitHub主页：https://g…...

编程日记 2025/7/11 4:53:46

2两数相加解题记录

哎呀，以为这道题也不用写题解的……结果还是有坑没跳出来。最开始想法先计算总和再求出链表 func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {// 先算出这个值。测试用例会int类型溢出total : 0wei : 1for l1!nil && l2!nil {total (l1.Vall…...

编程日记 2025/6/28 6:32:06

uniapp 获取dom信息（封装获取元素信息工具函数）

在uniapp开发中，需要获取到dom的信息，需要用到uniapp的指定方式 uni.createSelectorQuery()，但是每次需要用到的时候都需要很长一段的繁琐代码，本篇文章将呈现获取dom信息方法封装，话不多说，上菜&#xff1…...

编程日记 2025/7/11 18:43:30

Mybatis_Plus中常用的IService方法

查询方法名查询记录总数 /*** 查询总记录数** see Wrappers#emptyWrapper()*/default long count() {return count(Wrappers.emptyWrapper());} 方法实现 Testpublic void testGetCount(){long count userService.count();System.out.println("总记录数：&…...

编程日记 2025/7/11 21:39:49

【华为OD技术面试真题 - 技术面】- Java面试题（16)

华为OD面试真题精选专栏：华为OD面试真题精选目录: 2024华为OD面试手撕代码真题目录以及八股文真题目录线程创建的方式 1. 通过继承Thread类创建一个自定义线程类，继承Java中的Thread类，并重写run()方法。然后通过调用start()方法来启动线程。示例代码： // 继承Th…...

编程日记 2025/7/3 20:15:47

React(六）React过渡动画-CSS编写方式

React过渡动画 react-transition-group介绍在开发中，我们想要给一个组件的显示和消失添加某种过渡动画，提高用户体验→可通过react-transition-group实现。React曾为开发者提供过动画插件 react-addons-css-transition-group，后由社区维护…...

编程日记 2025/7/9 10:38:44

计算机视觉初步（环境搭建）

1.anaconda 建议安装在D盘，官网正常安装即可，一般可以安装windows版本安装成功后，可以在电脑应用里找到： 2.创建虚拟环境打开anaconda prompt， 可以用conda env list 查看现有的环境，一般打开默认bas…...

编程日记 2025/7/8 1:57:12

JAVA反序列化深入学习（九）：CommonsCollections7与CC链总结

CC7 依旧是寻找 LazyMap 的触发点 CC6使用了 HashSet而CC6使用了 Hashtable JAVA环境 java version "1.8.0_74" Java(TM) SE Runtime Environment (build 1.8.0_74-b02) Java HotSpot(TM) 64-Bit Server VM (build 25.74-b02, mixed mode) 依赖版本 Apache Commons …...

编程日记 2025/7/10 12:41:01

软考《信息系统运行管理员》- 6.1 信息系统安全概述

信息系统安全的概念信息系统安全是指保障计算机及其相关设备、设施(含网络)的安全，运行环境的安全， 信息的安全，实现信息系统的正常运行。信息系统安全包括实体安全、运行安全、信息安全和人员安全等几个部分。影响信息系统安全的因素…...

编程日记 2025/7/9 21:28:49

MDK中结构体的对齐、位域、配合联合体等用法说明

测试环境:STM32H7R3MDK 5.39AC5 注：PC、PowerPC等环境不适用本文。一.字节对齐一般采用自然对齐（默认方式），提高数据存取速度。采用1字节对齐，变量在内存中无空隙，紧密存储，节省存…...

编程日记 2025/7/10 5:49:37

C++实现布隆过滤器

1.布隆过滤器概念位图虽然能高效且节省存储数据，但是类型必须是整型，不能存储其它类型。布隆过滤器是由布隆提出的一中紧凑型，比较巧妙的概率型数据结构，特点是高效的插入和查询，可以得知什么是一定不存在或者可能存…...

编程日记 2025/6/28 1:37:55

React 揭秘：从新手到高手的进阶之路

目录 React：前端开发新宠 React 初相识什么是 React React 的核心特性 1.组件化开发 2.虚拟 DOM 与 Diff 算法单向数据流搭建 React 开发环境环境准备创建 React 项目项目结构解析 React 基础语法与核心概念 JSX 语法基本语法规则…...

编程日记 2025/7/9 10:47:06

JAVA的内存图理解

目录一、方法区1、类常量池2、静态常量池3、方法区过程二、栈三、堆1、字符常量池2、堆内存图的绘制 java中内存可以分为方法区、堆、栈、程序计数器、本地方法栈，其中比较中重要的是方法区、堆、栈。一、方法区 1.方法区（Method Area&…...

编程日记 2025/7/12 15:43:32

k8s存储介绍（六）StorangeClass

一、Kubernetes 存储类（StorageClass）详解 1. 什么是 StorageClass？ 在 Kubernetes 中，StorageClass（存储类）是一种用于动态创建 PersistentVolume（PV）的资源对象。它允许管理员根…...

编程日记 2025/7/9 18:25:33

SourceMap原理

点击查看原文 1 webpack中使用详见 js的模块化-webpack打包示例 2 webpack的配置 const { resolve } require(path)module.exports {mode: development,devtool: source-map,entry: ./src/index.js,output: {path: resolve(__dirname, dist),filename: "bundle.js&q…...

编程日记 2025/7/2 21:30:01

硬件基础--14_电功率

电功率电功率:指电流在单位时间内做的功(表示用电器消耗电能快慢的一个物理量)。单位:瓦特(W)，简称瓦。公式:PUI(U为电压，单位为V，i为电流，单位为A，P为电功率，单位为W)。单位换算:进位为1000&#xff…...

编程日记 2025/7/9 10:33:26

练习题：110

目录 Python题目题目题目分析需求理解关键知识点实现思路分析代码实现代码解释函数定义： 计算值的总和： 测试函数： 运行思路结束语 Python题目题目定义一个函数，接受一个字典作为参数，返回字…...

编程日记 2025/7/9 1:08:33

Promise使用

Promise 是 JavaScript 中用于处理异步操作的一种对象，它代表了一个异步操作的最终完成（或失败）及其结果值。Promise 有三种状态： 1. pending（进行中）：初始状态，既不是成功也不是失…...

编程日记 2025/7/12 23:06:04

心理咨询法律咨询预约咨询微信小程序系统源码独立部署

预约咨询微信小程序：基于ThinkPHPUniapp的全场景解决方案与SEO深度优化指南在心理健康、医疗问诊、法律咨询等领域线上化需求激增的背景下，预约咨询微信小程序凭借其灵活部署、多场景适配与隐私安全保障，成为机构与从业者提升服务效率的核心…...

编程日记 2025/7/9 1:30:10

JavaFX基础- Button 的基本使用

说明本文记录一下对Button的基本使用，包括但不限于样式的设置，事件的监听等。按钮样式的设置方式一 ： Java代码的方式 // 创建一个按钮Button button new Button("按钮");// 设置按钮的位置button.setLayoutX(50);button.set…...

编程日记 2025/7/5 1:54:40

Golang使用 ip2region 查询IP的地区信息

利用 ip2region 进行 IP 地址定位 import ("fmt""log""github.com/lionsoul2014/ip2region/binding/golang/xdb" )func main() {ip : "213.118.179.98"dbPath : ".\\cmd\\ip\\ip2region.xdb"// 1、初始化查询器//searcher,…...

编程日记 2025/7/11 1:17:33