3864 - D.找素数

题目描述
 用筛法求出n(1000000)以内的全部素数,并按每行五个数显示。(每行数之间用空格隔开)
输入
 输入一个正整数。
输出
 输出一组素数。
说明

⑴ 把2到100的自然数放入a[2]到a[100]中(所放入的数与下标号相同);

⑵ 在数组元素中,以下标为序,按顺序找到未曾找过的最小素数minp,和它的位置p(即下标号);

⑶ 从p+1开始,把凡是能被minp整除的各元素值从a数组中划去(筛掉),也就是给该元素值置 0;

⑷ 让p=p+1,重复执行第②、③步骤,直到minp>floor(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

//筛去被整除的数

来源

D.一维数组模拟

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 8
通过人数 4
金币数量
难度 未标记


上一题 下一题