2. 计算机
  3. 阅读下列程序说明和C代码，回答问题1～2。 [说明] 本程序用古典的Eratosthenes的筛法求从2起到指定范围内的素数。如果要找出2至10中的素数，开始时筛中有2到10的数，然后取走筛中的最小的数2，宜布它是素数，并把该素数的倍数都取走。这样，

阅读下列程序说明和C代码，回答问题1～2。 [说明] 本程序用古典的Eratosthenes的筛法求从2起到指定范围内的素数。如果要找出2至10中的素数，开始时筛中有2到10的数，然后取走筛中的最小的数2，宜布它是素数，并把该素数的倍数都取走。这样，

admin2009-02-15  75
问题 阅读下列程序说明和C代码，回答问题1～2。
[说明]
   本程序用古典的Eratosthenes的筛法求从2起到指定范围内的素数。如果要找出2至10中的素数，开始时筛中有2到10的数，然后取走筛中的最小的数2，宜布它是素数，并把该素数的倍数都取走。这样，第一步以后，筛子中还留下奇数3、5、7、9：重复上述步骤，再取走最小数3，宣布它为素数，井取走3的倍数，于是留下5、7。反复重复上述步骤，直至筛中为空时，工作结束，求得2至 10中的全部素数。
   程序中用数组sieve表示筛子，数组元素sieve的值为1时，表示数i在筛子中，值为-1时表示数i已被取走。
[程序]
#include ＜ stdio, h ＞
#define MAX 22500
main( )
{  unsigned int i , range , factor , k;
    int sieve[MAX];
    prinff( "please input the ’range:" );
    scanf(" %d" ,&range);            /* range 指出在多大的范围内寻找素数* /
    for(i=2 ;i<=range; i++)  (1); /*筛子初始化*/
    factor = 2 ;
   while (factor ＜ = range) {
    if((2)= = 1)l           /*筛子中最小数是素数*/
            pfinff( "% d\t" ,factor);
             k = factor;
            while (k ＜ =range) {           /* 取走素数的倍数*/
             (3);
                k=(4);
   factor + +;
  }
}
[问题1]将程序代码中的(1)～(4)处补充完整。
[问题2]在上述代码的执行过程中，若factor为5，从筛子中取走的头两个数是5和(5)。
选项
答案[问题1](1)sieve[i]=1 (2)sieve[factor] (3) sieve[k]=-1 (4)k+factor [问题2](5)25
解析 初始时，2到range以内的数i都在筛子中，即sieve=1；
(2)每用一次筛法，筛子中留存的最小数都不是前面素数的倍数，因而也是素数，我们只需用这个数来继续筛选。例如，用factor=2、3筛选以后，筛于中最小数是5，所以factor=4的情形不需考虑，只需对fsctor=5，即 sieve[factor]==1的情形继续执行筛选；
(3)若k是素数factor的倍数，则将k从筛子中移出，即设置sieve[k]=-1；
(4)由于k应该是素数factor的倍数，因此从韧值factor开始需要每次自增factor；
(5)当factor为2时，取走了2的倍数；当factor为3时，取走了3的倍数；于是当factor为5时取走的第二个数是5的倍数、但不是2或者3的倍数，这个数应该是 25。
转载请注明原文地址:https://kaotiyun.com/show/aojZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

相关试题推荐
随机试题
最新回复(0)