5.整数的处理.pptVIP

* 整数的处理 概 述 数论被誉为数学的皇后, 它的研究对象是整数的性质, 本课程涉及的如：求两个数的最大公约数和最小公倍数, 求一个正整数的素因子分解, 辗转相除法, 求方程的整数解等等各种问题都是数论里的一些初等的概念和方法。 1.素数与合数 ? 素数 对于某个整数a1，如果它仅有平凡约数1和a，则 我们称a为素数(或质数)。如： 2,3,5,6,11,13,17,19,23,29,31,37,41,43,47,53,59,…, ? 合数 不是素数的整数a1称为合数。 ? 整数 1 被称为基数，它既不是质数也不是合数。 ? 整数 0 和所有负整数既不是素数，也不是合数。 ? 判断m是否素数的算法： 让m被2到 除，如果m能被2～ 之中任何一个整数相除，则提前结束循环，此时 i 必然小于或等于k（即 ）；如果m不能被2～k之间的任一整数整除，则在完成最后一次循环后，i还要加1，因此i＝k＋1，然后才终止循环。在循环之后判别 i 的值是否大于或等于k＋1，若是，则表明未曾被2～k之间任一整数整除过，因此m是素数。 例1： #includemath.h main() { int m, i, k; scanf(%d, m); k=sqrt(m); for(i=2;i=k;i++) if(m%i==0) break; if(i=k+1) printf(%d is a prime number\n, m); else printf(%d is not a prime number\n, m); } 2.求最大公约数和最小公倍数 算法： 设a,b的最大公约数为gcd(a, b),可用下式计算gcd(a, b), 而最小公倍数＝a*b/gcd(a, b)。 例如：gcd(24, 32)=gcd(32, 24)=gcd(24, 8)=gcd(8, 0)=8 例2： main() { int a, b, num1, num2, temp; printf(Please input two integer numbers:\n); scanf(%d,%d, num1, num2); while(num11||num21) { printf(Input isnt correct. Please input again:\n); scanf(%d, %d,num1, num2); } if(num1num2) { temp=num1; num1=num2; num2=temp; } a=num1; b=num2; while(b!=0) { temp=a%b; a=b; b=temp; } printf(zdgys=%d, zxgbs=%d\n, a, num1*num2/a); } 3.求完数 一个数如果恰好等于它的因子之和，这个数就称 为“完数”。 例如：6的因子为1、2、3，而6＝1＋2＋3，因此 6是“完数”。 例3：找出1000以内的所有完数 #include stdio.h void main() { int m, s, k; for(m=1; m=1000; m++) { s=0; for(k=1; k=m/2; k++) if(m%k==0) s+=k; if(s==m) { printf(%d its factors are 1, m); for(k=2; k=m/2; k++) if(m%k==0) printf(,%d,k); printf(\n); } } } 4.分解质因数 将一个整数写成几个质因数的连乘积，如： 输入36，则程序输出36=2*2*3*3 。 例4： main() { int n, k=2, isfirst=1; printf(Inp