巧解最大公约数/最小公倍数! 课后习题6.1 （C++代码）

解题思路:
 本题采用穷举法。两个数a,b。则最大公约数的范围是[1,Max(a,b)]

 最小公倍数等于a*b/最大公约数!

不断穷举所有的可能,直到最先遇到一个公因子使a和b都能整除它,则该公因子为最大公约数!

然后跳出循环。

方法二: C++自带求最大公约数的API：_ _gcd(a,b)

注意事项:
a,b的最值用三目运算符?:求解。Max=a>b?a:b

参考代码:

//解题方法:本题采用穷举法:
//最大公约数maxY肯定是小于a和b的最大值的,
//所以将最大公约数赋值为a,b的最大值,maxY=a>b?a:b
//最小公倍数minB与最大公约数maxY的关系是  minB=(a*b)/maxY 
//然后一一穷举！直到找到后跳出循环
  
#include <iostream>   //c++标准输入输出流 
using namespace std;  //std命名空间 

int main()
{
	int a,b,maxY,minB; //maxY为最大公约数，maxB为最小公倍数     
	cin>>a>>b;  //输入a,b
	for(maxY=a>b?a:b;maxY>=1;maxY--)//a>B?a:b是求a,b的最大值 
	{
		if(a%maxY==0 && b%maxY==0)  //a,b都能整除最大公约数时， 
		{
			minB=a*b/maxY;           
			cout<<maxY<<" "<<minB<<endl;
			break;		            //找到maxY,minB后跳出循环 
		}	
	}	
	return 0;
}

以下为蓝桥杯的一道题目:

问题描述

　　编写一函数lcm，求两个正整数的最小公倍数。

样例输入

一个满足题目要求的输入范例。
例：

3 5

样例输出

与上面的样例输入对应的输出。
例：

数据规模和约定

　　输入数据中每一个数的范围。
　　例：两个数都小于65536。

注意:

注意范围，如果按照上面的这种方法求最小公倍数，需要注意的是数值的范围。

65535 x 65535 = 4294836225

需要用long long存放。

输入输出用%I64d

代码：

#include <stdio.h>

long long lcm(long long a,long long b)
{
	long long gcd;  //最大公约数
	for(gcd=a>b?a:b; gcd>=1; gcd--)
	{
		if(a%gcd==0 && b%gcd==0)
		{
			printf("%I64d",a*b/gcd);
			break;
		}
	 } 
}

int main()
{
	long long a,b;
	scanf("%I64d%I64d",&a,&b);
	lcm(a,b);	
	return 0;
}