问答题 [说明]
本程序用古典的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++) (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[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。