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

《用筛法求出100以内的全部素数.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、例6、用筛法求出100以内的全部素数，并按每行五个数显示。【问题分析】⑴把2到100的自然数放入a[2]到a[100]中（所放入的数与下标号相同）；⑵在数组元素中，以下标为序，按顺序找到未曾找过的最小素数minp,和它的位置p（即下标号）；⑶从p+1开始，把凡是能被minp整除的各元素值从a数组中划去（筛掉），也就是给该元素值置0；⑷让p=p+1，重复执行第②、③步骤，直到minp>Trunc(sqrt(N))为止；⑸打印输出a数组中留下来、未被筛掉的各元素值，并按每行五个数显示。用筛法求素数的过程示意如下（图中用下划线作删去标志）：①23456789101112

2、131415…9899100｛置数｝②23456789101112131415…9899100{筛去被2整除的数}③23456789101112131415…9899100{筛去被3整除的数}……23456789101112131415…9899100{筛去被整除的数}ProgramExam53;constN=100;typexx=1..N;{自定义子界类型xx（类型名）}Vara:array[xx]ofboolean;i,j:integer;BeginFillchar(a,sizeof(a),true);a[1]:=False;fori:=2toTrunc(sq

3、rt(N))doifa[I]thenforj:=2toNdivIdoa[I*j]:=False;t:=0;fori:=2toNdoifa[i]thenBeginwrite(a[i]:5);inc(t);iftmod5=0thenwritelnend;End.【例3】输入十个正整数，把这十个数按由大到小的顺序排列（将数据按一定顺序排列称为排序，排序的算法有很多，其中选择排序中的“简单选择排序”是一种较简单的方法）分析：要把十个数按从大到小顺序排列，则排完后，第一个数最大，第二个数次大，……；因此，我们第一步可将第一个数与其后的各个数依次比较，若发现，比它大的，则与之

4、交换，比较结束后，则第一个数已是最大的数。同理，第二步，将第二个数与其后各个数再依次比较，又可得出次大的数。如此方法进行比较，最后一次，将第九个数与第十个数比较，以决定次小的数。于是十个数的顺序排列结束。例如下面对5个进行排序，这个五个数分别为829105。按选择排序方法，过程如下：初始数据：829105第一轮排序：829105928105102895102895第二轮排序：108295109285109285第三轮排序：109825109825第四轮排序：109852对于十个数，则排序要进行9次。源程序如下：programex5_2;vara:array[1..

5、10]ofinteger;i,j,t:integer;beginwriteln('Input10integers:');fori:=1to10doread(a[i]);｛读入10个初始数据｝readln;fori:=1to9do｛进行9次排序｝beginforj:=i+1to10do｛将第i个数与其后所有数比较｝ifa[i]

6、】①用循环把十个数输入到A数组中；②从A[1]到A[10]，相邻的两个数两两相比较，即：A[1]与A[2]比，A[2]与A[3]比，……A[9]与A[10]比。只需知道两个数中的前面那元素的标号，就能进行与后一个序号元素（相邻数）比较，可写成通用形式A[i]与A[i+1]比较，那么，比较的次数又可用1～(n-i)循环进行控制(即循环次数与两两相比较时前面那个元素序号有关)；③在每次的比较中，若较大的数在后面，就把前后两个对换，把较大的数调到前面，否则不需调换位置。下面例举5个数来说明两两相比较和交换位置的具体情形：564375和6比较，交换位置，排成下行的顺序；6

7、54375和4比较，不交换，维持同样的顺序；654374和3比较，不交换，顺序不变654373和7比较，交换位置，排成下行的顺序；65473经过（1～（5-1））次比较后，将3调到了末尾。经过第一轮的1～(N-1)次比较，就能把十个数中的最小数调到最末尾位置，第二轮比较1～(N-2)次进行同样处理，又把这一轮所比较的“最小数”调到所比较范围的“最末尾”位置；……；每进行一轮两两比较后，其下一轮的比较范围就减少一个。最后一轮仅有一次比较。在比较过程中，每次都有一个“最小数”往下“掉”，用这种方法排列顺序，常被称之为“冒泡法”排序。ProgramExam52;cons

8、tN=10