C++程序设计:筛选法求解2~200间的素数

需积分: 42 1 下载量 74 浏览量 更新于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语言的优势,并增加了面向对象编程的支持,使得程序设计更加灵活且易于维护。