首页 > 试题广场 >

求最小公倍数

[编程题]求最小公倍数
  • 热度指数:1560 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

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


输入描述:

输入两个正整数A和B。



输出描述:

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

示例1

输入

5 7

输出

35
#include<bits/stdc++.h>
using namespace std;
int a,b;
int main(){
    cin>>a>>b;
    cout<<a*b/(__gcd(a,b));
    return 0;
}

发表于 2019-11-10 10:52:12 回复(1)
import java.util.*;
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 = 1; i <= b; i++) {
            if ((a*i) % b == 0){
                System.out.println(a*i);
                return;
            }
        }
    }
}

发表于 2022-03-29 16:09:57 回复(0)
#include<bits/stdc++.h>
using namespace std;

int GCD(int n,int m){
    if(m==0){
        return n;
    }
    else{
        return GCD(m,n%m);
    }
}

int main(){
    int n,m;
    while(cin>>n>>m){
        cout<<n*m/GCD(n,m)<<endl;
    }
    return 0;
}
发表于 2022-10-06 16:43:30 回复(0)
#include <stdio.h>
int min_gong(int a, int b)
{
    int min = 0;
    int i = 1;
    while (1)
    {
        min = i * a;
        if (min % b == 0)
        {
            return min;
        }
        i++;
    } 
}

int main()
{
    int a = 0;
    int b = 0;
    scanf("%d %d", &a, &b);
    printf("%d", min_gong(a, b));
    return 0;

}

发表于 2022-06-19 13:25:54 回复(0)
#include <iostream>

using namespace std;

int gcb(int a, int b){
    int r;
    while(r = a % b){
        a = b;
        b = r;
    }
    return b;
}

int main(){
    int a, b;
    cin >> a >> b;
    // 最小公倍数 = 两数之积除以最大公约数
    // 这里使用碾转相除法进行最大公约数的求解:
    // 即a与b的最大公约数可以转化为a、b之间的余数为两者之间最小的数之间的公约数。
    // 所以对于输入的两个数进行连续求余,直到余数为0,求余的分母即为结果。
    cout << a * b / gcb(a, b);
    return 0;
}

发表于 2020-06-03 14:02:26 回复(0)
import java.util.*;
public class Main{
    public static int gcd (int a, int b) {
        if (b == 0){
            return a;
        }
        return gcd (b,a%b);
    }
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println((a*b)/gcd(a,b));
    }
}

发表于 2019-12-17 22:27:49 回复(0)

int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d",&a,&b);
	//计算
	int m = (a > b ? a : b);
	while (1)
	{
		if (m % a == 0 && m % b == 0)
			break;
		m++;
	}
	printf("%d",m);
	return 0;

}

发表于 2024-01-23 13:43:38 回复(0)
#include <stdio.h>

int min_multp(int a, int b)
{
    int tmp;
    int i = 1;
    if (b > a)
    {
        tmp = a;
        a = b;
        b = tmp;
    }
    while (1)
    {

        if ((i * a) % b == 0)
            break;
        i++;
    }
    return a * i;

    
}


int main()
{
    int a, b;
    int MinMultp;
    while (1)
    {
        scanf("%d%d", &a, &b);
        if (a >= 1 && a <= 100000 && b >= 1 && b <= 100000)
            printf("最小公倍数是:%d\n", MinMultp = min_multp(a, b));
        else
            printf("输入数值范围为:1->100000,请重新输入\n");
    }
    
    return 0;

}

编辑于 2024-01-07 16:02:41 回复(0)
int main() {
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF) {
        int i = 1;
        while(a*i % b)  //通过a与i相乘再与b相模判断最小公倍数
        {
            i++;    //若不能整除,则i+1,直到能整除b为止
        }
        printf("%d\n", a * i);    //最终a*i即为最小公倍数
    }
    return 0;
}

编辑于 2023-05-20 16:26:49 回复(0)
#include <stdio.h>
#define MAX 100000000
int main() {
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF) { // 注意 while 处理多个 case
        int max;
        if(a>=b){
            max = a;
        }else{
            max = b;
        }
        if(max%a==0 && max%b==0){
            printf("%d",max);
        }else{
            for(int i = max; i<MAX; i++){
                if(i%a==0 && i%b==0){
                    printf("%d",i);
                    break;
                }
            }
        }
        // 64 位输出请用 printf("%lld") to 
        // printf("%d\n", a + b);
    }
    return 0;
}

发表于 2023-03-28 20:17:39 回复(0)
#include<stdio.h>
int main()
{
    int a = 0, b = 0;
    scanf("%d %d", &a, &b);
    int i = 0;
    int tmp = 0;
    for (i = 1; i <= b; i++)
    {
        tmp = a * i;
        if (tmp % b == 0)
            break;
    }
    printf("%d", tmp);
    return 0;
}
发表于 2022-12-04 19:32:23 回复(0)
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int n = scan.nextInt();
        int c = m * n / sameNum(m,n);
        System.out.println(c);

    }
    public static int sameNum(int a,int b) {
        int c = a % b;
        while(c != 0) {
            a = b;
            b = c;
            c = a % b;
        }
        return b;
    }
}
发表于 2022-04-04 19:24:47 回复(0)
import java.util.*;
public class Main{
    public static int gdc(int n, int m){
         if(m == n){
            System.out.println(n);
        }
        if(n < m){
            int tmp = n;
            n = m;
            m = tmp;
        }
        int r = 0;
         //辗转相除法求最大公约数
        while((r = n % m) > 0){
            n = m;
            m = r;
        }
        return m;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
       
        int mn = gdc(n,m);
        System.out.println((n * m)/mn);
    }

}



//方法2
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a = Math.max(m,n);
        int b = Math.min(m,n);
        int c = 0;
        //辗转相除法求最大公约数
        while((c = a % b) > 0){
            a = b;
            b = c;
        }
        System.out.println((n * m)/b);
    }
 
}

编辑于 2022-03-30 15:33:59 回复(0)
#define CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>

void asr(int a, int b)
{
    int i = a>b?b:a;
    int j = sqrt(i);
    int k = 0;
    for(k = j; k > 0; k--)
    {
        if( a%k == 0 && b%k ==0)
        {
            printf("%d", a*b/k);
            break;
        }
    }
    
}

int main()
{
    int a = 0, b = 0;
    scanf("%d %d", &a, &b);
    asr(a, b);
    return 0;
}

发表于 2022-02-09 14:15:31 回复(0)
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d%d", &a, &b);
	int max = a > b ? a : b;           //先找出两个数中的最大值,并赋值给max while (1)
	{
		if ((max%a == 0) && (max%b == 0))  //判断max是否可以整除两数 {
			printf("%d\n", max);
			break;
		}
		else
			max++;   //若max不可整除两数,则令max++,最终经过有限次循环一定可以找到可以同时整除两数的最小数,且此时该数为两数的最小公倍数 }
	return 0;
}

发表于 2021-10-20 14:52:58 回复(0)
#include<stdio.h>
int main()
{
    int a = 0;
    int b = 0;

    scanf("%d %d", &a, &b);
    int A = a;
    int B = b;
    int i = 0;
    int m = 0;
    for (i = 1,m=1;; )
    {
     
        if (A < B)
        {
            A = a * i;
            i++;
        }
        else if (A > B)
        {
            B = b * m;
            m++;
        }
        else
        {
            printf("%d", A);
                break;
        }
    }
    return 0;
}

发表于 2021-09-01 13:26:43 回复(0)
/***************************************************
 * Author        : cornfieldchase
 * Blog          : cornfieldchase2014.com
 * Filename      : 求最小公倍数.cpp
 * Description   : 
 * Last modified : 2019-11-14 18:45
***************************************************/
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
int main()
{
	int m, n, i;
	cin >> m >> n;
	for (i = m;; i++)
	{
		if (i%m == 0 && i%n == 0)
			break;
	}
	cout << i;
}

编辑于 2019-11-14 18:55:32 回复(0)
def gcd(a, b):

    if(b == 0):
        return a

    return gcd(b, a%b)


def lcm(a, b):

    if(a < 1 or b < 1):
        return 0

    if(a < b):
        a = a + b
        b = a - b
        a = a - b

    return (a*b / gcd(a, b))


a, b = input().split()
c = lcm(int(a), int(b))

print(int(c))

发表于 2019-10-28 17:06:45 回复(1)