用筛法求出100以内的全部素数.pdf

【筛法求素数】 筛法，也称埃拉托斯特尼筛法，是一种寻找所有小于给定数N的素数的有效算法。该方法的基本思想是通过逐步筛掉非素数来找出素数。以下是对这个算法的详细解释： 1. 初始化：创建一个长度为N的布尔数组a，所有元素设为真，表示这些数字可能是素数。数组下标从1开始，因为1不是素数，所以a[1]设为假。 2. 从2开始，找到数组中第一个未标记为假的数minp（最小素数）。在本例中，N=100，所以minp的初始值是2。 3. 遍历数组，从minp+1开始，将所有能被minp整除的数标记为假。这样，我们就筛掉了所有2的倍数（除了2本身）。 4. 移动指针p到下一个未标记为假的位置，重复步骤2和3，直到minp>√N。这是因为在所有大于√N的数中，如果它们是合数，那么它们必然有一个因子小于或等于√N。 5. 数组中未被标记为假的数就是素数。遍历整个数组，打印出所有值为真的元素，并按照每行五个数的形式显示。 给出的C语言代码实现如下： ```c #include <stdio.h> #include <math.h> int main() { const int N = 100; bool a[N+1]; // 初始化数组 for(int i = 2; i <= N; i++) { a[i] = true; } a[1] = false; // 筛法求素数 for (int i = 2; i <= trunc(sqrt(N)); i++) { if (a[i]) { for (int j = i * i; j <= N; j += i) { a[j] = false; } } } // 输出素数 int t = 0; for (int i = 2; i <= N; i++) { if (a[i]) { printf("%d", i); t++; if (t % 5 == 0) { printf("\n"); } else { printf(" "); } } } return 0; } ``` 这段代码首先初始化数组a，然后用筛法标记合数，最后输出未被标记的数，即素数。 【选择排序】 选择排序是一种简单的排序算法，其基本思路是找到数组中最小（或最大）的元素，将其与数组的第一个元素交换位置。然后在剩下的元素中找到次小（或次大）的元素，与数组的第二个元素交换，以此类推，直到数组完全排序。 以下是对选择排序的示例： ```pascal program Ex5_2; var a: array[1..10] of integer; i, j, t: integer; begin writeln('Input 10 integers:'); for i := 1 to 10 do read(a[i]); writeln('Sorted: '); for i := 1 to 9 do begin for j := i + 1 to 10 do if a[i] < a[j] then begin t := a[i]; a[i] := a[j]; a[j] := t; end; write(a[i]:5); end; end. ``` 这段代码首先读取10个整数，然后通过9次迭代，每次迭代找到剩余未排序部分的最大元素并将其移至正确位置。 【冒泡排序】 冒泡排序也是一种简单的排序算法，通过不断交换相邻的两个元素，使较大的元素逐渐“浮”到数组的一端。以下是冒泡排序的示例： ```pascal program Ex5_3; var a: array[1..10] of integer; i, j, t: integer; begin writeln('Input 10 integers:'); for i := 1 to 10 do read(a[i]); writeln('Sorted: '); for i := 1 to 9 do for j := i + 1 to 10 do if a[i] > a[j] then begin t := a[i]; a[i] := a[j]; a[j] := t; end; for i := 1 to 10 do write(a[i]:5); end. ``` 这段代码同样读取10个整数，但使用冒泡排序算法进行排序，每次比较相邻元素，如果顺序错误就交换它们，直到整个数组排序完成。