1、国家三级（数据库技术）机试模拟试卷 98及答案与解析 一、程序设计题 1 下列程序的功能是：将不超过整数 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 readwriteDa
2、t(); int num(int m, int xx) main ( ) int m,n,xx2000; clrscr(); printf(“nPlease enter the integer m:“); scanf(“ %d“ , n = num(m, xx); for(m-0;m printf(“ %d“ ,xxm); printf(“n“ ); readwriteDat(); viod readwriteDat () int m,n,xx1000, i; FILE *rf,*wf; rf=fopen(“in.dat“ ,“ r“ ); wf=fopen(“ out.dat“ ,“ w“
3、); for(i=0;i 10;i+) fscanf(rf,“ %d“ , n=num(m, xx); for(m=0;m n;m+)fprintf(wf,“ %d“ ,xxm); fprintf(wf,“n“ ); fclose(rf); fclose(wf); 国家三级（数据库技术）机试模拟试卷 98答案与解析 一、程序设计题 1 【正确答案】 int hum(int m， int xx) int s=0； int flag2000； /*初始化标记数组 */ for (i=0； i =m； i+) flagi=0； /*0和 1不是素数 */ flag0=flag1=1； /*从 2开始
4、搜索素数 */ for(i=2； i =m； i+) /*被标记为 1的不是素数 */ if(flagi)continue； /*i是素数，输出 */ xxs+=i； /*将所有 i的倍数标记为 1*/ /*小优化：小于 i*i的数必有小于 i的素因数，已标记 */ for(j=i*i； i =m； j+=i) flagj=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步，找到一个输出一个 )。
