最大公约数于最小公倍数和分解质因数的问题

你说的是辗转相除法吧，最大公约数与最小公倍数的乘积等于这2个数的乘积
证明：设A=a*……*b*c*……*h（a、b、c……h互质）
B=a*……*b*i*j*k*l*……*z（i、j、k……z互质）
公约数是a*……*b
公倍数是a*……*b*c*……*h*i*j*k*l*……*z
故相乘为A*B

C实现代码设n，m其中N>=M
while(m!=0)
{
r=n%m;
n=m;
m=r; //递归gcd(n,m)=gcd(m,n%m即余数)
}
s1=n; //最大公约数
s2=p/n; //最小公倍数

辗转相除法原理
http://blog.sina.com.cn/s/blog_53ed49360100052c.html

短除法就是把一个数依次除2 3 5 7 ……如果除了2之后还可以被2除则继续除直到不能被2除，再除3，
不知道楼主是否明白，
具体请参看小学数学

质因数是被短除法除出来的
最大公约数是两数或两数以上公有因数中最大的那个
最小公倍数是两数或两数以上公有倍数中最小的那个
是最大公约数,不是最小公约数

办法有两个,一是用短除法,这种最常见.二是翻倍法,就是用其中较大的那个数依次乘以2,3,4....求得的这些积中,最先是其他各数的倍数的那个积就是最小公倍数