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

【C++】实现100以内素数的求解


在这里插入图片描述

博客主页: [小ᶻ☡꙳ᵃⁱᵍᶜ꙳]
本文专栏: C++

文章目录

  • 💯前言
  • 💯代码概览
  • 💯代码结构与逻辑分析
    • 1. 包含的头文件和命名空间
    • 2. 素数判断函数 `isPrime`
      • 功能
      • 输入与输出
      • 核心逻辑
      • 数学背景
    • 3. 主函数 `main`
      • 功能
      • 核心逻辑
      • 输出示例
  • 💯代码优化与改进
    • 1. 循环范围优化
    • 2. 特殊数的处理
    • 3. 高效输出格式
  • 💯扩展与思考
  • 💯总结


在这里插入图片描述


💯前言

  • 本文系统性地解析了一段C++程序,旨在计算并输出100以内的所有素数。通过全面分析该程序的逻辑结构与实现细节,并结合数学背景与算法优化,本文不仅阐明了素数求解的基本原理,还探讨了多种优化策略与扩展思考。这些内容从基础到高级,既适合初学者掌握基本编程思维,也为进阶研究者提供了深入探讨的契机。
    C++ 参考手册
    在这里插入图片描述

💯代码概览

以下是原代码:

#include <iostream>
using namespace std;bool isPrime(int n) {if (n <= 1) return false; // 1 和负数不是素数for (int i = 2; i * i <= n; i++) { // 只需检查到 sqrt(n)if (n % i == 0) return false; // 如果能被整除,则不是素数}return true; // 如果没有找到任何因数,则是素数
}int main() {for (int i = 2; i < 100; i++) { // 遍历 2 到 99 的每个整数if (isPrime(i)) { // 判断是否为素数cout << i << " "; // 输出素数并加空格}}cout << endl; // 换行return 0;
}

在这里插入图片描述

该代码的核心功能是输出从100以内的所有素数,并以空格分隔。


💯代码结构与逻辑分析

在这里插入图片描述


1. 包含的头文件和命名空间

在这里插入图片描述

#include <iostream>
using namespace std;
  • #include <iostream>: 引入C++标准输入输出库,为程序提供 cincout 的输入输出能力。
  • using namespace std;: 使用标准命名空间,避免在调用标准库函数时添加 std:: 前缀。

通过这些设置,代码简洁明了,更适合教学和初学者。


2. 素数判断函数 isPrime

在这里插入图片描述

bool isPrime(int n) {if (n <= 1) return false; // 1 和负数不是素数for (int i = 2; i * i <= n; i++) { // 只需检查到 sqrt(n)if (n % i == 0) return false; // 如果能被整除,则不是素数}return true; // 如果没有找到任何因数,则是素数
}

功能

在这里插入图片描述
判断一个给定的整数是否为素数。


输入与输出

在这里插入图片描述

  • 输入:一个整数 n
  • 输出:布尔值 truefalse,分别表示该数是否为素数。

核心逻辑

在这里插入图片描述

  1. 特殊情况处理

    • n <= 1,直接返回 false,因为素数定义为大于1的自然数。
  2. 循环验证因数

    • 使用从 2 开始到 sqrt(n) 的整数依次验证。
    • 若发现 n % i == 0,说明 n 可被 i 整除,即存在非平凡因数,返回 false
  3. 返回结果

    • 若循环结束且未找到任何因数,则返回 true,表示 n 是素数。

数学背景

在这里插入图片描述
根据素数定义,若一个数 n 可以被某个因数整除,则较小的那个因数必定小于等于 sqrt(n)。因此,验证到 sqrt(n) 已足够,大大减少了运算量。


3. 主函数 main

在这里插入图片描述

int main() {for (int i = 2; i < 100; i++) { // 遍历 2 到 99 的每个整数if (isPrime(i)) { // 判断是否为素数cout << i << " "; // 输出素数并加空格}}cout << endl; // 换行return 0;
}

功能

在这里插入图片描述
该函数的作用是遍历2到99之间的所有整数,利用 isPrime 函数判断是否为素数,并将结果打印出来。


核心逻辑

在这里插入图片描述

  1. 循环遍历

    • 使用 for 循环,从 i = 2 开始,到 i < 100 结束。
    • 每个整数 i 都会调用 isPrime 函数进行素数判定。
  2. 输出素数

    • isPrime(i) 返回 true,则输出该整数 i,并在每个素数后加空格分隔。
  3. 格式美化

    • 最后输出换行符以便于美观。

输出示例

在这里插入图片描述
程序运行后,将输出:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

💯代码优化与改进

在这里插入图片描述
虽然上述代码能够正确实现功能,但在效率和代码设计上还有改进空间。


1. 循环范围优化

在这里插入图片描述
当前代码中,判断是否为素数时的循环条件为 i * i <= n。这一条件已在原代码中优化过,但仍存在冗余的平方计算。可以通过预计算 sqrt(n) 来进一步优化:

#include <cmath>bool isPrime(int n) {if (n <= 1) return false;int limit = sqrt(n); // 预计算平方根for (int i = 2; i <= limit; i++) {if (n % i == 0) return false;}return true;
}

2. 特殊数的处理

在这里插入图片描述
当前实现中,所有数都经过循环判断。对于某些特殊数(如2和3),可以直接返回结果,从而减少运算量:

bool isPrime(int n) {if (n <= 1) return false;if (n == 2 || n == 3) return true; // 直接判断 2 和 3if (n % 2 == 0 || n % 3 == 0) return false; // 排除偶数和 3 的倍数int limit = sqrt(n);for (int i = 5; i <= limit; i += 6) { // 检查 6k ± 1if (n % i == 0 || n % (i + 2) == 0) return false;}return true;
}

3. 高效输出格式

在这里插入图片描述
若素数数量较多,可以按行分隔输出,以提高可读性:

int count = 0;
for (int i = 2; i < 100; i++) {if (isPrime(i)) {cout << i << " ";count++;if (count % 10 == 0) cout << endl; // 每 10 个换行}
}

💯扩展与思考

在这里插入图片描述

1. 素数在计算机科学中的应用
在这里插入图片描述
素数在数学与计算机科学领域有广泛的应用,包括但不限于:

  • 密码学:现代加密算法(如RSA)广泛依赖大素数的生成与分解。
  • 随机数生成:使用素数提高伪随机数生成器的质量。
  • 哈希函数:素数在分布式哈希表中用于减少冲突。

2. 更高效的素数算法
在这里插入图片描述

埃拉托色尼筛法(Sieve of Eratosthenes)
在这里插入图片描述
通过标记非素数的方式筛选素数,其时间复杂度为 O ( n log ⁡ log ⁡ n ) O(n \log\log n) O(nloglogn)

  1. 创建大小为 n 的布尔数组,初始化为 true
  2. 从第一个素数 2 开始,标记其所有倍数为非素数。
  3. 继续筛选,直至完成。

线性筛法
在这里插入图片描述
线性筛法在埃拉托色尼筛法基础上进一步优化,实现时间复杂度 O ( n ) O(n) O(n)


💯总结

  • 在这里插入图片描述
    通过本次解析,我们从多个角度深入探讨了C++实现素数求解的问题,涵盖了代码逻辑数学背景算法优化以及实际应用。从基础的实现细节到高级的扩展问题,本文不仅为初学者提供了全面的入门指导,也为研究者指引了深度优化的方向。希望本文能帮助您进一步理解编程与数学的结合,为素数算法的学习与探索提供坚实的理论与实践基础。

在这里插入图片描述


相关文章:

【C++】实现100以内素数的求解

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 &#x1f4af;前言&#x1f4af;代码概览&#x1f4af;代码结构与逻辑分析1. 包含的头文件和命名空间2. 素数判断函数 isPrime功能输入与输出核心逻辑数学背景 3. 主函数 main功能核心逻辑输出示例 &#…...

Python 浏览器自动化新利器:DrissionPage,让网页操作更简单!

Python 浏览器自动化新利器&#xff1a;DrissionPage&#xff0c;让网页操作更简单&#xff01; 文章目录 Python 浏览器自动化新利器&#xff1a;DrissionPage&#xff0c;让网页操作更简单&#xff01;&#x1f680; 引言&#x1f31f; DrissionPage简介&#x1f6e0;️ 三大…...

Rust学习笔记_13——枚举

Rust学习笔记_10——守卫 Rust学习笔记_11——函数 Rust学习笔记_12——闭包 枚举 文章目录 枚举1. 定义1.1 无值变体1.2 有值变体1.3 枚举与泛型的结合 2. 使用2.1 和匹配模式一起使用2.2 枚举作为类型别名 3. 常用枚举类型 在Rust编程语言中&#xff0c;枚举&#xff08;enum…...

Postgresql 格式转换笔记整理

1、数据类型有哪些 1.1 数值类型 DECIMAL/NUMERIC 使用方法 DECIMAL是PostgreSQL中的一种数值数据类型&#xff0c;用于存储固定精度和小数位数的数值。DECIMAL的精度是由用户指定的&#xff0c;可以存储任何位数的数值&#xff0c;而小数位数则由用户自行定义。DECIMAL类型的…...

AI开发:卷积神经网络CNN原理初识,简易例程 - 机器学习

一 、卷积神经网络是什么 &#xff08;1&#xff09;印象 今天说的CNN&#xff0c;并不是我们熟知的美国有线电视新闻网。 那什么是CNN呢&#xff1f; Convolutional Neural Networks, CNN&#xff09;简单来说&#xff0c;就是用一个筛子来筛面粉的。 筛子就是卷积核&…...

详细介绍vue的递归组件(重要)

递归组件在 Vue 中是一个非常强大的概念&#xff0c;尤其在渲染层级结构&#xff08;如树形结构、嵌套列表、评论系统等&#xff09;时&#xff0c;能够极大地简化代码。 什么是递归组件&#xff1f; 递归组件就是一个组件在其模板中引用自身。这种做法通常用于渲染树形结构或…...

【单片机基础知识】基础知识(CortexM系列、STM32系统框架、存储器映射、寄存器映射)

1. CortexM系列介绍 ARM官方资料&#xff1a; &#x1f4ce;Arm Cortex-M4 Processor Datasheet.pdf&#x1f4ce;Arm-Cortex-M7-Processor-Datasheet.pdf&#x1f4ce;Arm Cortex-M Comparison Table_v3.pdf&#x1f4ce;Arm Cortex-M3 Processor Datasheet.pdf 课程资料&a…...

yolov5导出命令

python export.py --weights yolov5s.pt --img-size 640 --batch-size 1 --device cpu --include onnx 关闭动态输入&#xff0c;cpu导出 检测onnx模型能否加载成功指令&#xff1a; python detect.py --weights yolov5s.onnx --dnn 终端调用detect.py检测图片命令&…...

RabbitMQ的常用术语介绍

出版商 “出版商”一词在不同的上下文中有不同的含义。一般来说&#xff0c;在消息传递中 发布者&#xff08;也称为“生成者”&#xff09;是应用程序&#xff08;或应用程序实例&#xff09; 发布 &#xff08;生成&#xff09; 消息。同一应用程序也可以使用消息 因此同时也…...

Docker魔法:用docker run -p轻松开通容器服务大门

前言 “容器”与“虚拟化”作为现代软件开发和运维中的关键概念,已经广泛应用于各个技术领域。然而,在使用 Docker 部署应用时,常常会遇到这样的问题:容器正常运行,却无法让外界访问其内部服务?即使容器内的应用顺利启动,外部无法通过浏览器或 API 进行连接。此时,doc…...

【后端面试总结】Redis过期删除策略

Redis会将每个设置了过期时间的key放入一个独立的字典中&#xff0c;以后会定时遍历这个字典来删除到期的key。除了定时遍历之外&#xff0c;它还会使用惰性策略来删除过期的key。所谓惰性策略就是在客户端访问这个key的时候&#xff0c;Redis对key的过期时间进行检查&#xff…...

数字图像处理(15):图像平移

&#xff08;1&#xff09;图像平移的基本原理&#xff1a;计算每个像素点的移动向量&#xff0c;并将这些像素按照指定的方向和距离进行移动。 &#xff08;2&#xff09;平移向量包括水平和垂直分量&#xff0c;可以表示为&#xff08;dx&#xff0c;dy&#xff09;&#xff…...

高级java每日一道面试题-2024年12月08日-JVM篇-什么是类加载器?

如果有遗漏,评论区告诉我进行补充 面试官: 什么是类加载器? 我回答: 在Java高级面试中&#xff0c;类加载器&#xff08;ClassLoader&#xff09;是一个重要的概念&#xff0c;它涉及到Java类的加载和初始化机制。以下是对类加载器的详细解释&#xff1a; 定义与作用 类加…...

JAVA子类的无参构造器中第一行的super

在 Java 中&#xff0c;子类的构造器是否需要显式调用 super 取决于父类&#xff08;超类&#xff09;的构造器。 如果父类有一个无参构造器&#xff1a; 如果父类有一个无参构造器&#xff0c;那么子类的构造器可以不显式调用 super。在这种情况下&#xff0c;如果子类构造器的…...

mysql程序介绍,选项介绍(常用选项,指定选项的方式,特性),命令介绍(查看,部分命令),从sql文件执行sql语句的两种方法

目录 mysql程序 介绍 选项 介绍 常用选项 指定选项的方式 ​编辑配置文件 环境变量 选项特性 指定选项 选项名 选项值 命令 介绍 查看客户端命令 tee/notee prompt source system help contents 从.sql文件执行sql语句 介绍 方式 source 从外部直接导入…...

Unity教程(十九)战斗系统 受击反馈

Unity开发2D类银河恶魔城游戏学习笔记 Unity教程&#xff08;零&#xff09;Unity和VS的使用相关内容 Unity教程&#xff08;一&#xff09;开始学习状态机 Unity教程&#xff08;二&#xff09;角色移动的实现 Unity教程&#xff08;三&#xff09;角色跳跃的实现 Unity教程&…...

lanqiaoOJ 3744:小蓝的智慧拼图购物 ← pair+优先队列

【题目来源】https://www.lanqiao.cn/problems/3744/learning/【题目描述】 在小蓝的生日那天&#xff0c;他得到了一个由神秘人赠送的拼图游戏&#xff0c;每个拼图都有其特定的价值和相应的优惠券。小蓝决定要买下所有的拼图&#xff0c;但他希望能尽可能地节省花费。小蓝手中…...

Spring Boot教程之二十一:文件处理

Spring Boot – 文件处理 Spring Boot 是一种流行的、基于 Spring 的开源框架&#xff0c;用于开发强大的 Web 应用程序和微服务。由于它建立在 Spring 框架之上&#xff0c;因此它不仅具有 Spring 的所有功能&#xff0c;而且还包括某些特殊功能&#xff0c;例如自动配置、健康…...

【Linux】Linux的基本常识+指令

目录 1. 整体学习思维导图 2. 常见快捷键操作 3. 基本指令 pwd指令 whoami指令 ls 指令 touch指令 cd 指令 Stat 指令 mkdir 指令 alias指令 nano 指令 rmdir 和 rm 指令 man 指令手册 cp 命令 cat/echo/tac 指令 mv 指令 less 指令 head/tail 指令 date…...

Rocky Linux 9.3系统搭建Slurm环境【笔记】

实践环境:Rocky Linux 9.3 [root@m1 ~]# cat /etc/redhat-release Rocky Linux release 9.3 (Blue Onyx) [root@m1 ~]# uname -r 5.14.0-362.8.1.el9_3.x86_64 [root@m1 ~]#主机名和IP ● 控制节点m1:10.1.1.10 ● 计算节点c1:10.1.1.11 ● 计算节点c2:10.1.1.12 一、…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...