1、第二课数论相关知识及基本算法综合实践考核2/22素数和整除问题1、基本概念和基本性质(1)整除和约数整除和约数一个整数一个整数 a能被另一个整数能被另一个整数 d整除，记作整除，记作 d|a。 0可被每个可被每个整数整除。如果整数整除。如果 a0且且 d|a，则，则 |d|#include #include int main(void)int *a,i,k,n,s;while(scanf(“%d“,8/22素数和整除问题a=(int *)malloc(n+1)*sizeof(int);for(i=2;i=n;i+) /为便于操作，舍前 2两个元素未用ai=1;k=1;s=(int)sqrt(d
2、ouble)n);while(k=s)while(a+k=0);/找到下一个素数for(i=k*k;i=n;i+=k)/删除该素数的倍数ai=0;for(i=2;i=n;i+)/输出if(ai=1)printf(“%8d“,i);printf(“n“);free(a);return 0;上述算法存在同一个数多次筛选的问题，那么怎样才能一个数只被筛一次呢？留为课后作业。9/22素数和整除问题(2)朴素的判别法。从朴素的判别法。从 2开始试除小于开始试除小于 n的所有自然数。的所有自然数。 请大家请大家写出判别函数，并写出测试程序。写出判别函数，并写出测试程序。(3)注意到若注意到若 a是是 n的
3、因子，那么的因子，那么 n/a也是也是 n的因子，所以若的因子，所以若 n有有一个大于一个大于 1的真因子，则它必有一个不大于的真因子，则它必有一个不大于 n1/2的因子。的因子。(4)更进一步的，若更进一步的，若 n是合数，它必有一个素因子不大于是合数，它必有一个素因子不大于 n1/2。如果要检测一个如果要检测一个 M以内的数是否为素数，需要先建立一个以以内的数是否为素数，需要先建立一个以M1/2内素数表。按照此种方法，检验一个数是否是素数的步内素数表。按照此种方法，检验一个数是否是素数的步骤是怎样的？如果是一个软件系统，应该如何设计可以提高骤是怎样的？如果是一个软件系统，应该如何设计可以提高检验一个数是素数的效率？检验一个数是素数的效率？(5)米勒米勒 -勒宾勒宾 (Miller-Rabbin)测试：令大奇数测试：令大奇数 n=2lm+1,其中其中 l是非负整数，是非负整数， m是正奇数。若是正奇数。若 bm1(mod n)或或 n-1(mod n)， 0jl-1，则称，则称 n通过以通过以 b为基的的米勒为基的的米勒 -勒宾测试。若勒宾测试。若 n是素是素数，数， b是整数，且是整数，且 n不能整数不能整数 b，则，则 n必须通过以必须通过以 b为基的米勒为基的米勒 -勒宾测试。勒宾测试。10/22素数和整除问题例例 1：求：求 。分析：设 ， ，则
