短除法解题

解题思路:

两正整数m,n

最大公因数A

最小公倍数B

如上80=16*5,75=15*5

其中 5 为80,75的最大公因数

两者的最小公倍数为 16*15*5 或者说 (80/5)*(75/5)*5

从上面的例子可知  m,n的最小公倍数 B=(m/A)*(n/A)*A

以上我们解决了最小公倍数,那么最大公因数A怎么求

int main(){

int m,n,m1,n1,sum=1,i;

scanf("%d %d",&m,&n);  //取m,n

if(m==1 || n==1){            //当 m or n 其中为1时,其最大公因数只为1,最小公倍数为|m-n|+1(即m,n中较大的),或m*n

printf("1\n");

printf("%d",m*n);

return 0;

}

m1=m,n1=n;

for(i=2;i<=m&&i<=n;i++){ //这里使用穷举思想,每个小于等于m,n的数都试一遍

while(m%i==0&&n%i==0){ //当m,n能被除尽时,该i为m,n的共同系数

m/=i;

n/=i;

sum*=i; 

}

注意事项:

参考代码:

#include<stdio.h>
#include<stdlib.h>
int main(){
	int m,n,m1,n1,sum=1,i;
	scanf("%d %d",&m,&n),m1=m,n1=n;
	if(m==1 || n==1)printf("1\n%d",m*n),exit(3);
	for(i=2; i<=m&&i<=n; i++) while(m%i==0&&n%i==0) m/=i,n/=i,sum*=i;
	printf("%d\n%d",sum,(m1/sum)*(n1/sum)*sum);
	return 0;
}