首页 > 试题广场 >

求最小公倍数

[编程题]求最小公倍数
  • 热度指数：360783 时间限制：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
算法知识视频讲解
添加回答
Java
牛客160935469号头像 牛客160935469号 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt(), b = in.nextInt();
        System.out.println(a*b/gcd(a,b));
    }

    // 辗转相除法求最大公因数
    public static int gcd(int a, int b) {
        if (a % b == 0) return b;
        return gcd(b, a % b);
    }
}
发表于 2024-10-03 15:08:43 回复(0)
Java
段航舟头像 段航舟
将纯小学生思维进行Code 
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int num1 = scanner.nextInt();
			int num2 = scanner.nextInt();

			int result = 1;
			// i <= Math.min(num1, num2)防止两数成倍数关系
			for (int i = 2; i <= Math.min(num1, num2); i++) {
				if (num1 % i == 0 && num2 % i == 0) {
					// 先把公约数进行乘积运算
					result *= i;
					num1 /= i;
					num2 /= i;
					i--;
				}
			}
			//将所有公约数乘积后再对没有除尽的进行乘积运算
			result *= num1 * num2;

			System.out.println(result);

		}
		scanner.close();
	}
}


发表于 2024-09-27 19:16:43 回复(0)
Java
认真的芝士在敲键盘头像 认真的芝士在敲键盘
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(lcm(a, b));
        }
    }
    // 最小公倍数
    // (5*7)/1
    // (2*4)/2
    public static int lcm (int a, int b) {
        return (a * b) / gcb(a, b);
    }
    // 最大公约数
    // gcb(5,7)  gcb(5,2)  gcb(2,1)  gcb(1,0)  -->  a=1
    // gcb(2,4)  gcb(4,2)  gcb(2,0)  -->  a=2
    public static int gcb (int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcb(b, a % b);
    }
}

发表于 2024-09-11 10:14:02 回复(0)
Java
想去广东逛gai的里根说等下个版本吧头像 想去广东逛gai的里根说等下个版本吧 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int bottom = Math.max(m, n);
        while (true) {
            if (bottom % m == 0 && bottom % n == 0) {
                break;
            }
            bottom++;
        }
        System.out.println(bottom);
    }
}

发表于 2024-08-25 10:32:58 回复(0)
Java
牛啊牛啊__头像 牛啊牛啊__ 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int num1 = in.nextInt();
            int num2 = in.nextInt();
            for(int i = num1 > num2 ? num1 : num2; i <= num1 * num2; i++){
                if(i % num1 == 0 && i % num2 == 0){
                    System.out.println(i);
                    break;
                }
            }
        }
    }
}

发表于 2024-07-16 01:51:52 回复(0)
Java
Mars_Yu头像 Mars_Yu 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int result = 1;
            // 所有公约数相乘
            for (int i = 2;i<=Math.min(a,b);i++) {
                while (a%i==0 && b%i==0){
                    result*=i;
                    a = a/i;
                    b = b/i;
                }
            }
            result = result*a*b;
            System.out.println(result);
        }
    }
}

编辑于 2024-04-14 11:41:43 回复(0)
Java
擦声而过头像 擦声而过 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int A = in.nextInt();
        int B = in.nextInt();
        for (int i = Math.min(A,B); i <= A*B; i++){
            if ((i%A==0) && (i%B==0)){
                System.out.println(i);
                break;
            }
        }
    }
}

发表于 2024-04-01 22:38:52 回复(0)
Java
不再crud头像 不再crud 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt(), b = in.nextInt();
        System.out.println((a * b) / gcd(a, b));
    }

    public static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

编辑于 2024-03-16 19:41:21 回复(0)
Java
Dovis丶头像 Dovis丶 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        // 最小公倍数 = a*b/(ab的最大公约数)
        if (a < b) {
            int temp = a;
            a = b;
            b = temp;
        }
        System.out.println(a * b / zdgys(a, b));
    }
    public static int zdgys(int a, int b) {
        int c = a % b;
        if (c == 0) return b;
        return zdgys(b, c);
    }

}

发表于 2024-01-17 14:54:32 回复(1)
Java
牛客287768837号头像 牛客287768837号 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            int b = in.nextInt();
            int max = Math.max(a, b);
            int min = Math.min(a, b);
            for(int i=1; i<=min; i++){
                if((max*i)%min==0){
                    System.out.println(max*i);
                    break;
                }
            }
        }
    }
}

发表于 2023-10-26 09:15:53 回复(0)
Java
黑驴他爷头像 黑驴他爷
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            if (a > b) {
                int m = a % b;
                if (m == 0) {
                    System.out.println(a);
                } else {

                    System.out.println(getNum( b, a,0));
                }
            } else {
                int m = b % a;
                if (m == 0) {
                    System.out.println(b);
                } else {
                    System.out.println(getNum(a , b,0));
                }

            }

        }
    }

    public static int getNum(int sm, int big,int r) {
        for(int i=0; i<100000;i++){
            if(big * (i+1) % sm ==0){
                r= big * (i+1);
                break;
            }
        }
        return r;
    }
}
发表于 2023-08-28 13:27:17 回复(0)
Java
W_wwwww头像 W_wwwww
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int ab = zdgys(a, b);
        //a、b的最小公倍数等于a*b/（a和b的最大公约数）
        System.out.println(a * b / (ab));
    }
    //求a和b的最大公约数
    public static int zdgys(int m, int n) {
        if (m == n) {
            return m;
        }
        if (m < n) {
            int temp = m;
            m = n;
            n = temp;
        }
        int r;
        while ((r = m % n) > 0) {
            m = n;
            n = r;
        }
        return n;
    }
}

发表于 2023-08-10 07:34:54 回复(0)
Java
SUMMERENT头像 SUMMERENT 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int a = in.nextInt();
        int b = in.nextInt();
        for(int i = 1;i <= a*b;i++){
            if(i % a ==0 && i % b == 0){
                System.out.println(i);
                break;
            }
        }
    }
}

发表于 2023-06-09 14:26:19 回复(1)
Java
👑Kaiser👑头像 👑Kaiser👑
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
           
            int sum = a * b;
            // 将两个值相乘，提取公因子后再除
            int min = a < b ? a : b;
            int max = a > b ? a : b;
           
            for (int i = min; i >= 2; i--) {
                if (a % i == 0 && b % i == 0) {
                    if (sum / i < max) {
                        break;
                    } else {
                        sum /= i;
                    }
                }
            }
            System.out.println(sum);
        }
        in.close();
    }
}
发表于 2023-05-08 19:36:01 回复(0)
Java
牛客604637229号头像 牛客604637229号
 //获取最大公约数
    public static int getMaxYue(int a,int b){
        if(a==b){
            return a;
        }
        int maxNum = (int)Math.max(a,b);
        int minNum = (int)Math.min(a,b);
        if(minNum==0){
            return 1;
        }
        //辗转相除，小的数除以余数，直到余数为0，则为小的数；如小的数除以余数整除，则为余数
        int yu = maxNum%minNum;//7%5=2;2%1=0;500%255=245;245%10=5
        if(yu==0){
            return minNum;
        }
        int sy = minNum%yu;//5%2=1;; 255%245=10;10%5=0
        if(sy==0){
            return yu;
        }else{
            return getMaxYue(yu,sy);
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(a*b/getMaxYue(a,b));
        }
    }
发表于 2023-04-22 14:03:49 回复(0)
Java
西奥多小朵头像 西奥多小朵 
import java.util.Scanner;

// 辗转相除法
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int c = 1;//用来存储最大公约数
        for (int i = 2; i <= a; i++) {
            if (b % i == 0 && a % i == 0) {
                c = c * i;
                b = b / i;
                a = a / i;
                i--;
            }
        }
        //最终结果等于最大公约数乘各自的剩余互质的数
        System.out.println(c * a * b);
    }
}

发表于 2023-04-08 11:55:11 回复(0)
提交观点

问题信息

基础数学 递归
难度：
113条回答 79845浏览

热门推荐

通过挑战的用户

查看代码

相关试题

求最小公倍数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号