下列程序的功能是:将不超过整数m(m<2000)的所有素数存入数组xx。请编写函数 num(int m,int xx[])

Question

下列程序的功能是：将不超过整数m(m＜2000)的所有素数存入数组xx。请编写函数 num(int m，int xx[])实现程序的要求，最后调用函数readwriteDat()把结果输出到文件out.dat中。

例如：若输入30，则应输出：2，3，5，7，11，13，17，19，23，29。

部分源程序已给出。

请勿改动主函数main()和输出数据函数readwriteDat()的内容。

include ＜conio.h＞

include ＜stdio.h＞

void readwriteDat();

int num(int m, int xx[])

{

}

main ( )

{

int m,n,xx[2000];

clrscr();

printf("\nPlease enter the integer m:");

scanf(" %d" ,&m);

n = num(m, xx);

for(m-0;m printf(" %d" ,xx[m]);

printf("\n" );

readwriteDat();

}

viod readwriteDat ()

{

int m,n,xx[1000], i;

FILE *rf,*wf;

rf=fopen("in.dat" ," r" );

wf=fopen(" out.dat" ," w" );

for(i=0;i＜10;i++){

fscanf(rf," %d" ,&m);

n=num(m, xx);

for(m=0;m＜n;m++)fprintf(wf," %d" ,xx[m]);

fprintf(wf,"\n" );

}

fclose(rf);

fclose(wf);

}

Answer 1

正确答案：int hum(int m int xx[]) { int s=0； int flag[2000]； /*初始化标记数组*/ for (i=0； i=m； i++) flag[i]=0； /*0和1不是素数*/ flag[0]=flag[1]=1； /*从2开始搜索素数*/ for(i=2； i=m；i++) { /*被标记为1的不是素数*/ if(flag[i])continue； /*i是素数输出*/ xx[s++]=i； /*将所有i的倍数标记为1*/ /*小优化：小于i*i的数必有小于i的素因数已标记*/ for(j=i*i；i=m；j+=i) flag[j]=1； } /*返回不超过m的素数个数*/ return S； }
int hum(int m， int xx[]) { int s=0； int flag[2000]； /*初始化标记数组*/ for (i=0； i=m； i++) flag[i]=0； /*0和1不是素数*/ flag[0]=flag[1]=1； /*从2开始搜索素数*/ for(i=2； i=m；i++) { /*被标记为1的不是素数*/ if(flag[i])continue； /*i是素数，输出*/ xx[s++]=i； /*将所有i的倍数标记为1*/ /*小优化：小于i*i的数必有小于i的素因数，已标记*/ for(j=i*i；i=m；j+=i) flag[j]=1； } /*返回不超过m的素数个数*/ return S； } 解析：类型：素数筛选。
关键点：素数筛选算法。
求给定范围1～n内的所有素数的题，可以使用筛选法，步骤如下：
创建一个0-1标志数组，对应1～n，1代表该数非素数，0代表素数。初始化全为0，以下面的方式将某些位置以1标记：
(1)标记位置1为1(1不是素数)，当前位置为2。
(2)从当前位置开始，找到第一个标记为0的数p，p是素数；若找不到，转到6。
(3)遍历数组，将所有p的倍数的位置标记为1。
(4)当前位置前进到p+1。
(5)返回2继续。
(6)输出数组中所有标记为0的数(此步可并入第2步，找到一个输出一个)。