问答题 [说明] 本程序用古典的Eratosthenes的筛法求从2起到指定范围内的素数。如果要找出2至10中的素数,开始时筛中有2到10的数,然后取走筛中的最小的数2,宜布它是素数,并把该素数的倍数都取走。这样,第一步以后,筛子中还留下奇数3、5、7、9:重复上述步骤,再取走最小数3,宣布它为素数,井取走3的倍数,于是留下5、7。反复重复上述步骤,直至筛中为空时,工作结束,求得2至 10中的全部素数。 程序中用数组sieve表示筛子,数组元素sieve[i]的值为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++){{U}} (1) {{/U}}; /*筛子初始化*/ factor = 2 ; while (factor < = range) { if({{U}} (2) {{/U}}= = 1)l /*筛子中最小数是素数*/ pfinff( "% d/t" ,factor); k = factor; while (k < =range) { /* 取走素数的倍数*/ {{U}}(3) {{/U}}; k={{U}} (4) {{/U}}; factor + +; } }[问题1]将程序代码中的(1)~(4)处补充完整。 [问题2]在上述代码的执行过程中,若factor为5,从筛子中取走的头两个数是5和{{U}} (5) {{/U}}。
【正确答案】
【答案解析】[问题1](1)sieve[i]=1 (2)sieve[factor] (3) sieve[k]=-1 (4)k+factor [问题2](5)25 初始时,2到range以内的数i都在筛子中,即sieve[i]=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。