郑珺 浙江传媒学院 数论问题 郑珺 浙江传媒学院 最大公约数最大公约数 gcd 欧几理德法：碾转相除。 int gcd(int a,int b) if(b=0) return a; else return gcd(b,a%b); 郑珺 浙江传媒学院 最大公约数最大公约数 gcd 欧几理德法：大数反复减小数，直到2者相等。 int gcd(int x,int y) while(x!=y) if(xy) x=x-y; else y=y-x; return x; 郑珺 浙江传媒学院 最小公倍数最小公倍数 x*y/gcd(x,y) 如果如果x*y超出范围，可用超出范围，可用x/gcd(x,y)*y 郑珺 浙江传媒学院 素数 判断判断n是否为素数是否为素数 int isPrime(int n) int i; if(n=1)return 0; if(n=2)return 1; if(n%2=0)return 0; for(i=3;i=sqrt(n);i=i+2) if(n%i=0) return 0; return 1; 郑珺 浙江传媒学院 求小于求小于n素数，筛法素数，筛法 bi为0表示为素数，1表示非素数 a中保存所有小于n的素数，k为个数 int a100,b100; memset( b, 0, sizeof(b); k=0; for(i=2;i=n;i+) if(bi) continue; ak+=i; for(j=i+i;j=n;j+=i) bj=1;