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

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...