OpenJudge

3:筛法求素数

总时间限制:
1000ms
内存限制:
32767kB
描述

素数是仅仅能被它本身和1整除的任何整数。筛法求素数是一种查找素数的方法。它的算法如下:

1、创建一个数组,并将所有元素初始化为1(真)。具有素数下标的数组元素将保持为1,而其它数组元素最终将被设置为0

2、从数组下标2开始,每次找到一个值是1的数组元素时,在数组的剩余部分中循环,并将值为1的元素的下标整数倍的所有元素设置为0。对于数组下标2,数组中所有2以上的而且是2的整数倍的元素都将这是为0(下标46810等等)。对于数组下标3,数组中所有3以上,而且是3的整数倍的元素都将设置为0(下标691215等等)。

当这个过程结束时,仍然为1的数组元素的下标是一个素数。然后就可以输出这些素数。

编写一个程序,它使用具有1000个元素的数组,来确定和输出1999之间的所有素数。忽略数组元素01。每个输出占6列,左对齐。每行输出8个数。


输入
输出
1~999之间的所有素数
样例输入
样例输出
2     3     5     7     11    13    17    19    
23    29    31    37    41    43    47    53    
59    61    67    71    73    79    83    89    
97    101   103   107   109   113   127   131   
137   139   149   151   157   163   167   173   
179   181   191   193   197   199   211   223   
227   229   233   239   241   251   257   263   
269   271   277   281   283   293   307   311   
313   317   331   337   347   349   353   359   
367   373   379   383   389   397   401   409   
419   421   431   433   439   443   449   457   
461   463   467   479   487   491   499   503   
509   521   523   541   547   557   563   569   
571   577   587   593   599   601   607   613   
617   619   631   641   643   647   653   659   
661   673   677   683   691   701   709   719   
727   733   739   743   751   757   761   769   
773   787   797   809   811   821   823   827   
829   839   853   857   859   863   877   881   
883   887   907   911   919   929   937   941   
947   953   967   971   977   983   991   997   
全局题号
12370
添加于
2017-11-03
提交次数
91
尝试人数
48
通过人数
46