求最小公倍数C++

Question

Problem A:最小公倍数

Time Limit:1000MS Memory Limit:65536K
Total Submit:13 Accepted:2

Description

简单的数学问题：给定2个正整数a,b,求它们的最小公倍数。

Input

输入有多组测试数据，每组测试数据包含2个正整数a，b。
当a=0，b=0时，输入结束。

Output

输出a,b的最小公倍数。

Sample Input

3 2
5 7
24 32
0 0

Sample Output

6
35
96

Answer 1

//******************************************************************************
// 给定2个正整数a,b,求它们的最小公倍数。
//******************************************************************************

#include<stdio.h>
int main()
{
int i, a, b;
while(scanf("%d%d", &a, &b) && (a != 0 && b != 0))
{
if(a > b) //a>b 互换a b值
{
a = a + b;
b = a - b;
a = a - b;
}
for(i = b;; i++)
if(i % a == 0&&i%b==0) //满足最小公倍数条件，输出
{
printf("%d\n", i);
break;
}
}
}
//祝你学习进步，更上一层楼！(*^__^*)追问

为什么提交上去说是time limit exceed

追答

#include
int main()
{
int i, a, b;
while(scanf("%d%d", &a, &b) && (a != 0 && b != 0))
{
if(a > b) //a>b 互换a b值
{
a = a + b;
b = a - b;
a = a - b;
}
for(i = b;; i+=b) //i+=b;减少循环次数 ***************
if(i % a == 0&&i%b==0) //满足最小公倍数条件，输出
{
printf("%d\n", i);
break;
}
}
}

本回答被提问者采纳

Answer 2

#include<iostream>
using namespace std;
int codi(int x,int y) //返回的是最大公约数
{
int i,k;
if(x<y)
{
k=x;
x=y;
y=k;
}
i=y%x;
while(i!=0)
{
y=x;
x=i;
i=y%x;
}
return x;
}
int main()
{
int k;
int a,b;
do
{ cout<<" a= ";cin>>a;cout<<endl;
cout<<" b= ";cin>>b;cout<<endl;

if(a==0&&b==0)
break;
else
k=codi(a,b);

cout<<a<<"与"<<b<<"的最小公倍数是："<<a*b/k<<endl;
}while(a*b);
return 0;
}

Answer 3

int lcm(int a,int b)
{
int m=a,n=b;
while(a>b?(a=a%b):(b=b%a));//碾转相除法
return m*n/(a+b);
}