当前位置: 首页 > 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 一、…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...