C 最大公约数和最小公倍数main(){int i,m,n,c,w;scanf("%d%d",&m,&n);for(i=m;i>=2;i--){if(m%2==0 && m%i==0){c=i;break;}}for(i=m;i
来源:学生作业帮助网 编辑:作业帮 时间:2024/08/03 15:52:04
![C 最大公约数和最小公倍数main(){int i,m,n,c,w;scanf(](/uploads/image/z/384403-67-3.jpg?t=C+%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0%E5%92%8C%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0main%EF%BC%88%EF%BC%89%7Bint+i%2Cm%2Cn%2Cc%2Cw%3Bscanf%28%22%25d%25d%22%2C%26m%2C%26n%29%3Bfor%28i%3Dm%3Bi%3E%3D2%3Bi--%29%7Bif%28m%252%3D%3D0+%26%26+m%25i%3D%3D0%29%7Bc%3Di%3Bbreak%3B%7D%7Dfor%28i%3Dm%3Bi)
C 最大公约数和最小公倍数main(){int i,m,n,c,w;scanf("%d%d",&m,&n);for(i=m;i>=2;i--){if(m%2==0 && m%i==0){c=i;break;}}for(i=m;i
C 最大公约数和最小公倍数
main()
{
int i,m,n,c,w;
scanf("%d%d",&m,&n);
for(i=m;i>=2;i--)
{if(m%2==0 && m%i==0){c=i;break;}}
for(i=m;i
C 最大公约数和最小公倍数main(){int i,m,n,c,w;scanf("%d%d",&m,&n);for(i=m;i>=2;i--){if(m%2==0 && m%i==0){c=i;break;}}for(i=m;i
if(m%2==0 && m%i==0){c=i;break;}}
改成
if(n%2==0 && m%i==0){c=i;break;}}
我有更好的办法:
两个方法:
假设这两个数是a,b a>=b;
1
让变量i从b开始递减,for(i-b;i>2;i--)
判断能否被b整除
这个方法速度慢
2
设m为a,b的最大公约数,那么 a%m==0 b%m==0
令a = w*m; b= e*m; w,e都为整数
(a%b) == a - k*b; k肯定是一个整数;
=> a%b = w*m - k*b = w*m-k*e*m = (w-k*e)*m;
因为 w,e,k都是整数,并且a%b>=0;
=> (a%b) %m ==0;
所以求a,b的公约数就是求a%b,b的公约数
该方法速度很快.
int gcd(int a,int b) // a>=b
{
int t = a% b;
while( t > 0 )
{
a= b;
b= t;
t = a%b;
}
return b;
}