用筛法求出100以内的全部素数
萌到你眼炸
576次浏览
2021年02月02日 01:10
最佳经验
本文由作者推荐
严寒的反义词-一生所爱吉他谱
例
6
、用筛法求出
100
以内的全部素数，并按每行五个数显示。< br>
【问题分析】
⑴
把
2< br>到
100
的自然数放入
a[2]
到
a[100]
中（ 所放入的数与下标号相同）
；
⑵
在数组元素中，以下 标为序，按顺序找到未曾找过的最小素数
minp,
和它的位置
p
（即下标号 ）
；
⑶
从
p+1
开始，把凡是能被
minp
整除的各元素值从
a
数组中划去（筛掉）
，也就是给该元素 值置
0
；
⑷
让
p=p+ 1
，重复执行第②、③步骤，直到
minp>Trunc(sqrt(N))
为止；
⑸
打印输出
a
数组中留下来、未被筛掉的各元素值，并按每行五个数显示。
用筛法求素数的过程示意如下（图中用下划线作删去标志）
：
①
2 3 4 5 6 7 8 9 10 11 12 13 14 15
…
98 99 100
｛置数｝
②
2 3 4 5 6 7 8 9 10 11 12 13 14 15
…
98 99 100 {
筛去被
2
整除的数
}
③
2 3 4 5 6 7 8 9 10 11 12 13 14 15
…
98 99 100 {
筛去被
3
整除的数
}
……
2 3 4 5 6 7 8 9 10 11 12 13 14 15
…
98 99 100 {
筛去被整除的数
}
Program Exam53;
const N=100;
type xx=1 .. N; {
自定义子界类型
xx
（类型名）
}
Var a: array[xx] of boolean; i,j: integer;
Begin
Fillchar(a,sizeof(a),true);
a[1] := False;
for i:=2 to Trunc(sqrt(N)) do
if a[I] then
for j := 2 to N div I do
a[I*j]:= False;
t:=0;
for i:=2 to N do
if a[i] then
Begin
write(a[ i ]:5); inc(t);
if t mod 5=0 then writeln
end;
End.
【例
3
】
输入十个正整数，把这十个数按由大到小的顺序排列（将数据按一定顺序排列称为
排序，排序的 算法有很多，其中选择排序中的
“
简单选择排序
”
是一种较简单的方法）
分析：
要把十个数按从大到小顺序排列，
则排完后，第一个数最大，
第二个数次大，
……
；
因此，我们第一步可将第一个数与 其后的各个数依次比较，若发现，比它大的，
则与之交
换，比较结束后，则第一个数 已是最大的数。同理，第二步，将第二个数与其后各个数再依
次比较，又可得出次大的数。如此方法进行 比较，
最后一次，
将
第九个数与第十个数比较，
以决定次小的数。于是十个数的顺序排列结束。
例如下面对
5
个进行排序，这个五个数分别为
8
2
9
10
5
。按选择排序方法，过程如
下：
初始数据
：
8
2
9
10
5
第一轮排序：
8
2
9
10
5
9
2
8
10
5
10
2
8
9
5
10
2
8
9
5
第二轮排序：
10
8
2
9
5
10
9
2
8
5
10
9
2
8
5
第三轮排序：
10
9
8
2
5
10
9
8
2
5
第四轮排序：
10
9
8
5
2
对于十个数，则排序要进行
9
次。源程序如下：
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]);
｛读入
10
个初始数据｝
readln;
for i:=1 to 9 do
｛进行
9
次排序｝
begin
for j:=i+1 to 10 do
｛将第
i
个数与其后所有数比较｝
if a[i]
a[i]
大
,
则与之交换｝
begin
t:=a[i];a[i]:=a[j];a[j]:=t;
end;
write(a[i]:5);
end;
end.
例5
、
编程
输入十个正整数，然后自动按从大到小的顺序输出。
（冒泡排序 ）
【问题分析】
①用循环把十个数输入到
A
数组中；
②从
A[1]
到
A[10]
，相邻的两个数两两相比较，即：
A[1]
与A[2]
比，
A[2]
与
A[3]
比，……
A[9]< br>与
A[10]
比。
只需知道两个数中的前面那元素的标号，就能进行 与后一个序号元素（相邻数）比较，可写成通用形
式
A[ i ]
与
A[ i +1]
比较，那么，比较的次数又可用
1
～
( n - i )
循环进行控制
(
即循环次数与两两相比
较时前面那个元素序号有关
)
；
③在每次的比较中，若较大的数 在后面，就把前后两个对换，把较大的数调到前面，否则不需调换位
置。
下面例举
5
个数来说明两两相比较和交换位置的具体情形：
5 6 4 3 7 5
和
6
比较，交换位置，排成下行的顺序；
6 5 4 3 7 5
和
4
比较，不交换，维持同样的顺序；
6 5 4 3 7 4
和
3
比较，不交换，顺序不变
6 5 4 3 7 3
和
7
比较，交换位置，排成下行的顺序；
6 5 4 7 3
经过（
1
～（
5-1
）
）次比较后，将
3
调到了末尾。
经过第一轮的
1
～
(N-1)
次 比较，就能把十个数中的最小数调到最末尾位置，第二轮比较
1
～
(N-2)
次
进行同样处理，又把这一轮所比较的“最小数”调到所比较范 围的“最末尾”位置；……；每进行一轮两
两比较后，其下一轮的比较范围就减少一个。最后 一轮仅有一次比较。在比较过程中，每次都有一个“最
小数”往下“掉”
，用这种方法排列顺序，常被称之为“冒泡法”排序。
Program
Exam52;
const N=10;
Var a: array[1..N] of integer;
｛定义数组｝
i,j: integer;
procedure
Swap(Var x,y: integer);
｛交换两数位置的过程｝
Var t:integer;
begin
t:=x; x:=y; y:=t
end;
Begin
for i:=1 to N do
｛输入十个数｝
begin
Readln(a[ i ])
end;
for j:=1 to N-1 do
｛冒泡法排序｝
for i:=1 to N-j do {
两两相比较
}
if a[ i ] < a[i+1] then swap(a[ i ], a[i+1]); {
比较与交换
}
for i:=1 to N do
｛输出排序后的十个数｝
write(a[ i ]:6);
Readln
end.
例：读入５个学生的学号和成绩，计算他们的平均 分，若比平均分高１０分的等第为
A
，若比平
均分高小于１０分的等地为
B< br>，若低于平均分，则等第为
C
，输出他们的成绩和等第。
program sample7d1(input,output);
const n=5;
type
no=array[1..n] of integer;
s=array[1..n]of real;
var
i:integer;
k:real;
num:no;
score:s;
begin