C++程序设计:筛选法求解2~200间的素数
需积分: 42 3 浏览量
更新于2024-08-24
收藏 8.81MB PPT 举报
"用筛选取法求出2~200之间的所有素数。筛法:首先将1~n个数为数组置初值。2的倍数不是素数,置0;3的倍数不是素数,置0;5的倍数不是素数,置0;....,依次类推,最后将数组中不是0的元素输出。"
在计算机编程中,求解素数是一项基础任务,尤其在算法和数学问题中经常出现。筛选取法,也称为埃拉托斯特尼筛法(Sieve of Eratosthenes),是一种古老的求解素数的方法,适用于找出一个范围内所有的素数。在这个方法中,我们首先创建一个从1到目标范围(例如2到200)的数列,然后按照顺序标记每个数的倍数为非素数,通常从2开始,因为2是最小的素数。具体步骤如下:
1. 创建一个布尔类型的数组,长度为目标范围(这里是200),并初始化所有元素为`true`,表示假设它们都是素数。
2. 从2开始,对于每个未被标记为非素数的数(即数组中的`true`值),将其所有倍数标记为非素数(将对应数组位置设为`false`)。例如,2的所有倍数(4, 6, 8, ...)都是合数,因此将这些位置设为`false`。
3. 继续这个过程,下一个未被标记的数是3,因为2的倍数已经处理过,所以从3开始标记它的倍数(如6, 9, 12, ...)。
4. 以此类推,直到遍历到目标范围的平方根,因为大于这个数的倍数肯定已经在之前的倍数处理过程中被标记过了。
5. 最后,数组中剩下的`true`值所对应的数就是素数。
这段描述展示了筛选取法的简化过程,用于找出2到200之间的素数。数组初始状态如下:
```
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2 3 0 5 0 7 0 9 0 11 0 13 0 15 0 17 0 19 0
```
然后进一步优化,消除已标记的3和5的倍数:
```
2 3 0 5 0 7 0 0 0 11 0 13 0 0 0 17 0 19 0
```
最终,数组中未被标记为0的数(即`true`值)就是素数。
标签中提到的"谭浩强 C++"是指谭浩强编著的《C++程序设计》一书,这是一本经典的C++学习教材,适合初学者了解C++语言。书中详细介绍了C++的基本概念、语法和编程技巧。第一章C++概述部分讲述了C++语言的发展历程,以及C语言的特点,包括其结构化特性、高效性、可移植性以及对程序员自由度的较高要求。C++是在C语言基础上发展起来的,保留了C语言的优势,并增加了面向对象编程的支持,使得程序设计更加灵活且易于维护。
2020-04-24 上传
2012-10-09 上传
点击了解资源详情
点击了解资源详情
点击了解资源详情
点击了解资源详情
点击了解资源详情
2013-01-22 上传
Happy破鞋
- 粉丝: 12
- 资源: 2万+
最新资源
- C语言数组操作:高度检查器编程实践
- 基于Swift开发的嘉定单车LBS iOS应用项目解析
- 钗头凤声乐表演的二度创作分析报告
- 分布式数据库特训营全套教程资料
- JavaScript开发者Robert Bindar的博客平台
- MATLAB投影寻踪代码教程及文件解压缩指南
- HTML5拖放实现的RPSLS游戏教程
- HT://Dig引擎接口,Ampoliros开源模块应用
- 全面探测服务器性能与PHP环境的iprober PHP探针v0.024
- 新版提醒应用v2:基于MongoDB的数据存储
- 《我的世界》东方大陆1.12.2材质包深度体验
- Hypercore Promisifier: JavaScript中的回调转换为Promise包装器
- 探索开源项目Artifice:Slyme脚本与技巧游戏
- Matlab机器人学习代码解析与笔记分享
- 查尔默斯大学计算物理作业HP2解析
- GitHub问题管理新工具:GIRA-crx插件介绍