首页 > 试题广场 >

求最小公倍数

[编程题]求最小公倍数
  • 热度指数:344013 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值,设计一个算法,求输入A和B的最小公倍数。

数据范围:

输入描述:

输入两个正整数A和B。



输出描述:

输出A和B的最小公倍数。

示例1

输入

5 7

输出

35
示例2

输入

2 4

输出

4
// 先求出最大公约数,然后再求最小公倍数
while(line=readline()){
    var arr = line.split(" ");
    var numA = parseInt(arr[0]);
    var numB = parseInt(arr[1]);
    console.log(numA * numB / getGcd(numA, numB));
}

function getGcd(m, n) {
    let max = Math.max(m, n);
    let min = Math.min(m, n);
    if(max % min === 0) {
        return min;
    } else {
        return getGcd(max % min, min);
    }
}

编辑于 2020-01-29 15:40:06 回复(0)
import java.util.*;//两数最小公倍数等于两数乘积除以两数的最大公约数
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int A=sc.nextInt();
            int B=sc.nextInt();
            int result=A*B;
            result=result/getYinShu(A,B);
            System.out.println(result);
            }
        }
    public static int getYinShu(int m,int n){
    	int i=m;
            while((m%i!=0)||(n%i!=0)){
             i--;
            }
         return i;
    }
    }


发表于 2016-08-05 16:21:07 回复(3)
利用将range的起点和步长都设置为两个数中最小的那个,那么每次遍历的值一定能整出更小的数,只需要判断能否整除更大的数就行了
a,b=map(int, input().split())
for i in range(min(a,b),a*b+1,min(a,b)):
    if i%b==0:
        print(i)
        break


发表于 2022-07-03 17:42:03 回复(0)
while True:
    try:
        a,b = map(int,input().split())
        if a%b==0:   #先讨论b是a的因子的情况
            print(a)
        elif b%a==0: #a是b的因子的情况
            print(b)
        else:
            factor=1  
            for i in range(max(a,b),1,-1): #从a和b中较大的一个开始试因子,直到2,倒叙
                if a%i==0 and b%i==0:
                    factor *= i #公因子累积
                    a=a/i #a和b分别除以公因子
                    b=b/i
                else:
                    continue
            result=int(a*b*factor)  #除以所以公因子后的a和b,乘所有公因子之积
            print(result)
    except:
        break
                    

发表于 2021-10-27 06:18:56 回复(0)
using System;

namespace 最小公倍数
{
    class Program
    {
        static void Main(string[] args)
        {
            string line;
            while((line=Console.ReadLine())!=null)
            {
                string[] Array = line.Split(" ");
                int num1 = Convert.ToInt32(Array[0]);
                int num2 = Convert.ToInt32(Array[1]);
                int tmp;
                if (num1 < num2)
                {
                    tmp = num1; num1 = num2; num2 = tmp;
                }
                int a = num1; int b = num2;
                while (b != 0)
                {
                    tmp = a % b;
                    a = b;
                    b = tmp;
                }
                Console.WriteLine(num1 * num2 / a);
            }
        }
    }
}
发表于 2021-10-21 15:01:50 回复(0)
import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int a=sc.nextInt();
            int b=sc.nextInt();
            int max=a>b?a:b;
            int x=max;
            for(;;x+=max){
                if(x%a==0 && x%b==0){
                    System.out.println(x);
                    return;
                }
            }
        }
    }
}


发表于 2021-10-17 15:26:33 回复(0)
import java.util.Scanner;

//暴力法,时间复杂度高
// public class Main{
//     public static void main(String[] args){
//         Scanner sc = new Scanner(System.in);
//         while(sc.hasNext()){
//             int a = sc.nextInt();
//             int b = sc.nextInt();
//             int res = 0;
//             if(a>b) res=fun(b, a);
//             else if(a<b) res=fun(a, b);
//             else res=a;
//             System.out.println(res);
//         }
//     }
    
//     private static int fun(int a, int b){
//         for(int i=b; i<=a*b; i++){
//             if(i%a==0 && i%b==0) return i;
//         }
//         return 0;
//     }
// }

//辗转相除法求最大公约数gbc(a,b)= gbc(b, a%b);,最小公倍数=两数乘积 / 最大公约数
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int a = sc.nextInt();
            int b = sc.nextInt();
            System.out.println((a*b)/gcb2(a, b));
        }
    }
    
    //递归写法gbc(a,b)= gbc(b, a%b)
    private static int gcb1(int a, int b){
        if(b==0) return a;
        
        //后面递归b大,a%b小,所以b先达到0
        return gcb1(b, a%b);
    }
    
    //迭代写法
    private static int gcb2(int a, int b){
        while(b>0){
            int temp = a%b;
            a = b;
            b = temp;
        }
        return a;
    }
}

发表于 2021-08-17 14:37:31 回复(0)
#include<stdio.h>

int main()
{
    int a,b;
    scanf("%d %d",&a,&b);
    for(int i=a;i<=a*b;i++)
    {
        if(i%a==0 && i%b ==0)
        {
            printf("%d",i);
            break;
        }
    }
    return 0;
}

发表于 2021-08-16 23:09:58 回复(0)
最小公倍数 = 两数的积 / 最大公约数
while (line = readline()) {
    var lines = line.split(' ');
    var a = parseInt(lines[0]);
    var b = parseInt(lines[1]);
    
    var minNum = Math.min(a, b);
    var maxY = 1
    for(var i = 2; i<= minNum; i ++) {
        if(a % i === 0 && b % i === 0) {
            maxY = i;
        }
    }
    print(a * b / maxY);
}

发表于 2021-07-20 10:28:46 回复(0)
a,b=map(int,input().split())
l=[]
for i in range(1, min(a, b)+1):
    if a % i == 0 and b % i == 0:
        l.append(i)
print(a*b//max(l))
发表于 2021-07-11 01:19:06 回复(1)
#include <stdio.h>
int main()
{
    int a,b,result,text,i=1,max,min;
    scanf("%d%d",&a,&b);
    max=a>b?a:b;
    min=a<b?a:b;
    while(1)
    {
        text=i*max;
        if(text%min==0)
            break;
        i++;
    }
    printf("%d\n",text);
    return 0;
}
发表于 2021-06-16 19:12:27 回复(0)
/**
Swift 没有使用递归调用的版本

思路:老老实实按照语文老师教的写了个 栈,把每次的公约数压了进去,最后除不尽时再将两位数字一起压入。解法可用于求最小公约数~
*/

while let value = readLine() {
    print("\(solution(value))")
}

func solution(_ inputStr: String) -> Int {
    let numArray = inputStr.split(separator: " ")
    var numA = Int(numArray[0]) ?? 0
    var numB = Int(numArray[1]) ?? 0
    
    var numStack = [Int]()
    
    var count = 2
    while count <= max(numA, numB) {
        
        if numA % count == 0, numB % count == 0 {
            numStack.append(count)
            numA /= count
            numB /= count
            
            // 达到最小值情况提前退出
            if count >= min(numA, numB) {
                numStack.append(numA)
                numStack.append(numB)
                break
            }
            
            continue
        
        } else if numA % count == 0 {
            numStack.append(count)
            numA /= count
            
        } else if numB % count == 0 {
            numStack.append(count)
            numB /= count
        }
        
        if count >= min(numA, numB) {
            numStack.append(numA)
            numStack.append(numB)
            break
        }
        count += 1
    }
    return numStack.reduce(1) { $0 * $1 }
}

发表于 2021-04-05 22:16:53 回复(0)
最小公倍数=两数之积除以最大公约数,最大公约数用辗转相除法来求就好。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null) {
            String[] pair = line.trim().split(" ");
            System.out.println(lcm(Integer.parseInt(pair[0]), Integer.parseInt(pair[1])));
        }
    }
    
    private static int lcm(int a, int b) {
        return a*b / gcd(a, b);     // 最小公倍数为两数之积除以最大公约数
    }
    
    // 辗转相除法求最大公约数
    private static int gcd(int a, int b) {
        if(a < b){
            int temp = a;
            a = b;
            b = temp;
        }
        while(b > 0){
            int remain = a % b;
            a = b;
            b = remain;
        }
        return a;
    }
}

编辑于 2021-04-04 09:45:41 回复(0)
import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt(), B = sc.nextInt();
        System.out.println(getLCM(A, B));
    }
    
    public static int getLCM(int A, int B) {
        return A*B/getGCD(A, B);
    }
    
    public static int getGCD(int A, int B) {
        //辗转相除法求最大公约数
        int x = Math.max(A, B);
        int y = Math.min(A, B);
        while(y > 0) {
            int mod = x%y;
            if(y > mod) {
                x = y;
                y = mod;
            } else {
                x = mod;
            }
        }
        return x;
    }
}

发表于 2021-03-17 15:14:11 回复(0)
def gcd(a, b):
    """Return greatest common divisor using Euclid's Algorithm."""
    while (a % b != 0):
        t = a % b
        a = b  # 新的a用原来的b值
        b = t  # 新的b用原来的余数值
    return b  # 若a除以b能整除,则b就是两个数的最大公约数。
# 首先,从键盘键入两个数a和b的值,变量t来保存余数。用while循环来判断能否整除,根据“辗转相除法”,先用第一个数a÷b再将除数b赋给a,
# 余数赋给b,循环往复,直到能整除时结束循环,此时的除数b即为最大公约数。

def lcm(a, b):
    """Return lowest common multiple."""
    return a * b // gcd(a, b)


while True:
    try:
        a, b = map(int, input().split())
        print(lcm(a, b))
    except:
        break

 特别说明:a<b,例如a=18b=99t=a%b=18%99=18;新的a用原来的b————a=99;新的b用原来的余数值b=t=18我们发现通过一次循环交换了ab的值,这时就能满足a>b的条件了,再继续根据辗转相除的方法即可得到最大公约数。因此,无须顾及输入的两个整数ab谁大谁小。
编辑于 2020-12-24 12:09:50 回复(0)
import sys


def gcd(a, b):
    while b:
        a, b = b, a%b
    return a


def lcm(a, b):
    return a*b//gcd(a, b)


for s in sys.stdin:
    a, b = map(int, s.split())
    print(lcm(a, b))

发表于 2020-12-19 19:14:11 回复(0)
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while((str=br.readLine()) != null) {
            String[] inArr = str.split(" ");
            int a = Integer.parseInt(inArr[0]);
            int b = Integer.parseInt(inArr[1]);
            int max = a*b;
            int min = Math.max(a, b);
            for(int i=min; i<=max; i++) { //肯定在两者大的那个 和 两者的乘积之间(闭区间)
                if(i%a==0 && i%b==0) {
                    System.out.println(i);
                    break;
                }
            }
        }
    }
}
发表于 2020-09-20 01:15:14 回复(0)

Java 欧几里得公式

思路

利用欧几里得公式进行计算;

实现

import java.util.Scanner;

/**
 * @author : cunyu
 * @version : 1.0
 * @className : OneZeroEight
 * @date : 2020/8/8 22:41
 * @description : 108.求最小公倍数
 */

public class OneZeroEight {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {

            int m = Integer.parseInt(input.nextLine().split(" ")[0]);
            int n = Integer.parseInt(input.nextLine().split(" ")[1]);
            System.out.println(getLcm(m, n));
        }
    }

    /**
     * @param m
     * @param n
     * @return
     * @description 求最大公约数
     * @date 2020/8/8 22:50
     * @author cunyu1943
     * @version 1.0
     */
    public static int getGcd(int m, int n) {
        while (n > 0) {
            int tmp = m % n;
            m = n;
            n = tmp;
        }
        return m;
    }

    /**
     * @param m
     * @param n
     * @return
     * @description 求最小公倍数
     * @date 2020/8/8 22:50
     * @author cunyu1943
     * @version 1.0
     */
    public static int getLcm(int m, int n) {
        return m * n / getGcd(m, n);
    }
}
发表于 2020-08-08 22:57:36 回复(0)
def Num(a,b):
    for i in range(min(a,b),(a*b+1)):
        if i%a == 0 and i%b == 0:
            print(i)
            break
            
a = int(input('A:'))
b = int(input('B:'))
Num(a,b)

为什么提交通过率是0%啊,在IDLE上没错啊
发表于 2020-08-02 15:12:55 回复(1)
import java.util.*;


public class Main{
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        System.out.println(a*b/fun(a,b));
    }
 
    public static int fun(int min,int max){
        if(min>max){
            min = min^max;
            max = min^max;
            min = min^max;
        }
        
        int k;
        while(min!=0){
            k = max%min;
            max = min;
            min = k;
        }
        return max;
    }
    
    
}





发表于 2020-08-01 12:10:54 回复(0)