试题四

[程序4说明]
本程序用古典的Eratosthenes的筛法求从2起到指定范围内的素数。如果要找出2至10中的素数，开始时筛中有2到10的数，然后取走筛中的最小的数2，宣布它是素数，并把该素数的倍数都取走。这样，第一步以后，筛子中还留下奇数3、5、7、9：重复上述步骤，再取走最小数3，宣布它为素数，并取走3的倍数，于是留下5、7。反复重复上述步骤，直至筛中为空时，工作结束，求得2至10中的全部素数。
程序中用数组sieve表示筛子，数组元素sieve[i]的值为1时，表示数i在筛子中，值为-1时表示数i已被取走。

[程序4]
#include <stdio.h>
#define MAX 22500
main()
{ unsigned int i , range , factor , k ;
int sieve[MAX] ;
printf(“please input the range : ”);
scanf(“%d”,&range); /*range指出在多大的范围内寻找素数 */
for (i=2 ; i<=range ; i++) /* 筛子初始化 */
(1) ;
factor=2 ;
while (factor<=range) {
if ( (2) ) { /*筛子最小数是素数 */
printf(“%d\t”,factor);
k=factor;
while (k<=range)
{ /*移走素数的倍数 */
(3) ; /*筛中的个数减一 */
k= (4) ;
}
}
(5) ;
}

[1]  [2]  [3]  [4]  [5]