首页 > 试题广场 >

求最小公倍数

[编程题]求最小公倍数
  • 热度指数：347073 时间限制：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
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)
Java
牛客432759555号头像 牛客432759555号
import java.util.Scanner;

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

        }
    }
}
发表于 2023-03-13 13:41:00 回复(0)
Java
牛客268032525号头像 牛客268032525号 
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();
        in.close();

        int lcm = A * B / gcd(A, B);
        System.out.println(lcm);
    }

    private static int gcd(int x, int y) {
        while (y != 0) {
            int temp = x % y;
            x = y;
            y = temp;
        }
        return x;
    }
}

发表于 2023-03-01 22:16:45 回复(0)
Java
牛客849313640号头像 牛客849313640号 
import java.util.Scanner;

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

发表于 2023-02-14 21:54:57 回复(2)
Java
Jeremy777头像 Jeremy777 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] strings = in.nextLine().split(" ");
        Node node = new Node(Integer.parseInt(strings[0]),
                             Integer.parseInt(strings[1]));
        int result = 1;
        while (!isDoublePrime(node)) {
            result *= node.num;
            node.x1 /= node.num;
            node.x2 /= node.num;
        }
        System.out.println(result * node.x1 * node.x2);
    }

    public static Boolean isDoublePrime(Node node) {
        for (int i = Math.min(node.x1, node.x2); i > 1; i--)
            if (node.x1 % i == 0 && node.x2 % i == 0) {
                node.num = i;
                return false;
            }
        return true;
    }
}

class Node {
    int x1;
    int x2;
    int num = 1;    // 公因数
    public Node(int x1, int x2) {
        this.x1 = x1;
        this.x2 = x2;
    }
}

发表于 2023-01-04 00:41:18 回复(0)
Java
。LAN头像 。LAN
数论基础，辗转相除法求出最大公约数，再利用最大公约数求出最小公倍数。 
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println(a/new Main().gcd(a,b)*b);
    }
    int gcd(int a, int b){
        return b ==0?a:gcd(b,a%b);
    }
}

发表于 2022-09-18 15:29:21 回复(0)
Java
牛客685639456号头像 牛客685639456号
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        
        while(sc.hasNext()){
            int n1 = sc.nextInt();
            int n2 = sc.nextInt();
            //判断n1 和n2 谁大，大的为循环次数
            int n = 0;
            if(n1>=n2){
                n=n1;
            }else{
                n = n2;
            }
            
            //
            int sum = 0;
            for(int i =1; i<= n; i++){
                sum =i * n1; //计算其中一个数的倍数
                if(!(sum % n2 ==0)){//如果倍数刚好能正数另外一个数，则是最小公倍数
                    continue;
                }else{
                    break;
                }
            }
            System.out.println(sum);
            
        }

    }
}
发表于 2022-09-04 11:00:58 回复(0)
提交观点

问题信息

基础数学 递归
难度：
106条回答 78061浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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