资源预览内容
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
亲,该文档总共6页全部预览完了,如果喜欢就下载吧!
资源描述
郑珺 浙江传媒学院 数论问题 郑珺 浙江传媒学院 最大公约数最大公约数 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;
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号