本文共 1712 字，大约阅读时间需要 5 分钟。

目录

题目描述

正整数A和正整数B的最小公倍数是指：能被A和B整除的最小的正整数值。设计一个算法，求A和B的最小公倍数。

输入/输出示例

解决方案

对于正整数A和B，假设这两个数字的最大值为max，最小值为min。则他们的最小公倍数范围在闭区间 [max,  max * min] 中。我们定义一个临时变量current = max，current依次递增到 max * min，在每一次递增时观察其是否是A，B的公倍数，若是则找到A和B的最小公倍数current。

对于current的递增有一个注意点。在current递增的过程中，依次自增1会浪费大量的时间。current只需要每次递增max就可以准确找到A和B的最小公倍数了。（即每次递增max值保证整除max，若找到同时能够整除两者则为最小公倍数）

代码

package mainimport (	"bufio"	"fmt"	"os"	"strconv"	"strings")func MaxNumber(number1, number2 int) int {	if number1 > number2 {		return number1	}	return number2}func main() {	reader := bufio.NewReader(os.Stdin)	data, _, _ := reader.ReadLine()	dataList := strings.Split(string(data), " ")	number1, _ := strconv.Atoi(dataList[0])	number2, _ := strconv.Atoi(dataList[1])	min := MaxNumber(number1, number2)	current := min	for {		if current % number1 == 0 && current % number2 == 0 {			break		}		current += min	}	fmt.Println(current)}

代码走读

package mainimport (   "bufio"   "fmt"   "os"   "strconv"   "strings")# 返回两个int数的最大值func MaxNumber(number1, number2 int) int {   if number1 > number2 {      return number1   }   return number2}func main() {   # 读取两个正整数   reader := bufio.NewReader(os.Stdin)   data, _, _ := reader.ReadLine()   dataList := strings.Split(string(data), " ")   number1, _ := strconv.Atoi(dataList[0])   number2, _ := strconv.Atoi(dataList[1])   # 确定最小公倍数范围下限min   min := MaxNumber(number1, number2)   max := number1 * number2   # 遍历current, current每次递增min（即A、B两个数中的最大值）。若current同时满足整除A和B，则跳出循环，此时current为最小公倍数   current := min   for {      if current >= max {         break      }      if current % number1 == 0 && current % number2 == 0 {         break      }      current += min   }   fmt.Println(current)}

传送门

转载地址：http://ddsoi.baihongyu.com/