최대 공약수와 최소 공배수

4/25/2023
36 minutes to read

수학시간에 배우는 최대공약수 (GCD, Greatest Common Divisor)와 최소공배수 (LCM, Least Common Multiple)는 두 정수의 연산에 관련된 주요 개념입니다. 이들은 여러 문제와 알고리즘에서 사용되며, C 언어를 포함한 다양한 프로그래밍 언어에서 구현할 수 있습니다.

최대공약수 (GCD): 두 개 이상의 정수의 공통 약수 중에서 가장 큰 정수를 의미합니다. 예를 들어, 12와 16의 최대공약수는 4입니다. 최대공약수를 구하는 방법 중 하나는 수작업으로 두 정수의 약수를 찾아 공통된 약수 중 가장 큰 값을 찾는 것입니다. 이 방법은 작은 수에 대해서는 직관적이고 쉽게 적용할 수 있지만, 큰 수에 대해서는 매우 비효율적입니다. 이런 경우, 유클리드 호제법이 널리 사용됩니다. 유클리드 호제법은 두 정수를 나눈 나머지를 이용해 반복적으로 최대공약수를 찾는 알고리즘입니다.
최소공배수 (LCM): 두 개 이상의 정수의 공통 배수 중에서 가장 작은 정수를 의미합니다. 예를 들어, 12와 16의 최소공배수는 48입니다. 최소공배수는 두 정수의 곱을 그들의 최대공약수로 나누는 것으로 구할 수 있습니다. 즉, LCM(a, b) = a * b / GCD(a, b).

이제 C 언어를 사용하여 최대공약수와 최소공배수를 구현해보겠습니다.

최대 공약수를 출력하는 프로그램

다음 예제는 최대 공약수를 구하는 프로그램입니다. 이 프로그램은 사용자로부터 두 개의 정수를 입력받아, 최대 공약수를 계산한 후 출력합니다.

코드: gcd.c

#define _CRT_SECURE_NO_WARNINGS // 보안 경고를 무시하는 데 필요한 전처리기 지시문
#include <stdio.h> 

// 두 정수 a와 b의 최대 공약수를 구하는 함수
int gcd(int a, int b)
{
    int c;
    // b가 0이 아닐 때까지 반복
    while (b != 0)
    {
        // a를 b로 나눈 나머지를 c에 저장
        c = a % b;
        // a에는 b 값을 대입
        a = b;
        // b에는 c 값을 대입
        b = c;
    }
    // 최대 공약수를 반환
    return a;
}

int main(void)
{
    int a, b;

    printf("두 정수를 입력하세요: ");
    scanf("%d %d", &a, &b);

    // 최대 공약수를 계산하고 출력
    printf("%d와 %d의 최대 공약수는: %d입니다.\n", a, b, gcd(a, b));

    return 0;
}

코드: GreatestCommonDivisorCalculator.cs

using System;

class GreatestCommonDivisorCalculator
{
    // 두 정수 a와 b의 최대 공약수를 구하는 함수
    static int Gcd(int a, int b)
    {
        int c;
        // b가 0이 아닐 때까지 반복
        while (b != 0)
        {
            // a를 b로 나눈 나머지를 c에 저장
            c = a % b;
            // a에는 b 값을 대입하여 b가 더 작은 값이 되도록 함
            a = b;
            // b에는 c 값을 대입하여 b를 a를 나눈 나머지로 변경함
            b = c;
        }
        // 최대 공약수를 반환
        return a;
    }

    static void Main()
    {
        int a, b;

        Console.Write("두 정수를 입력하세요: ");
        // 사용자로부터 두 정수를 입력받음
        string[] input = Console.ReadLine().Split();
        a = int.Parse(input[0]);
        b = int.Parse(input[1]);

        // 최대 공약수를 계산하고 출력
        Console.WriteLine("{0}와 {1}의 최대 공약수는: {2}입니다.", a, b, Gcd(a, b));
    }
}

코드: GCDProgram.java

import java.util.Scanner;

class GCDProgram {
    // 두 정수 a와 b의 최대 공약수를 구하는 함수
    static int gcd(int a, int b) {
        int c;
        // b가 0이 아닐 때까지 반복
        while (b != 0) {
            // a를 b로 나눈 나머지를 c에 저장
            c = a % b;
            // a에는 b 값을 대입
            a = b;
            // b에는 c 값을 대입
            b = c;
        }
        // 최대 공약수를 반환
        return a;
    }

    public static void main(String[] args) {
        int a, b;

        Scanner sc = new Scanner(System.in);
        System.out.print("두 정수를 입력하세요: ");
        a = sc.nextInt();
        b = sc.nextInt();

        // 최대 공약수를 계산하고 출력
        System.out.printf("%d와 %d의 최대 공약수는: %d입니다.\n", a, b, gcd(a, b));
    }
}

코드: gcd.py

# 두 정수 a와 b의 최대 공약수를 구하는 함수
def gcd(a, b):
    # b가 0이 아닐 때까지 반복
    while b != 0:
        # a를 b로 나눈 나머지를 c에 저장
        c = a % b
        # a에는 b 값을 대입
        a = b
        # b에는 c 값을 대입
        b = c
    # 최대 공약수를 반환
    return a

# 메인 함수
if __name__ == '__main__':
    a, b = map(int, input("두 정수를 입력하세요: ").split())
    
    # 최대 공약수를 계산하고 출력
    print("{0}와 {1}의 최대 공약수는: {2}입니다.".format(a, b, gcd(a, b)))

코드: gcd.html

<!DOCTYPE html>
<html>
<head>
    <title>GCD Program</title>
</head>
<body>
    <h1>GCD Program</h1>
    <p>두 정수를 입력하세요:</p>
    <input type="text" id="input1">
    <input type="text" id="input2">
    <button onclick="calculate()">계산</button>
    <p id="result"></p>
    <script>
        // 두 정수 a와 b의 최대 공약수를 구하는 함수
        function gcd(a, b) {
            var c;
            // b가 0이 아닐 때까지 반복
            while (b !== 0) {
                // a를 b로 나눈 나머지를 c에 저장
                c = a % b;
                // a에는 b 값을 대입
                a = b;
                // b에는 c 값을 대입
                b = c;
            }
            // 최대 공약수를 반환
            return a;
        }

        function calculate() {
            var a = parseInt(document.getElementById("input1").value);
            var b = parseInt(document.getElementById("input2").value);
            var result = gcd(a, b);
            // 최대 공약수를 계산하고 출력
            document.getElementById("result").innerHTML = a + "와 " + b + "의 최대 공약수는: " + result + "입니다.";
        }
    </script>
</body>
</html>

코드: GCDProgram.cpp

#include <iostream>
using namespace std;

// 두 정수 a와 b의 최대 공약수를 구하는 함수
int gcd(int a, int b) {
    int c;
    // b가 0이 아닐 때까지 반복
    while (b != 0) {
        // a를 b로 나눈 나머지를 c에 저장
        c = a % b;
        // a에는 b 값을 대입
        a = b;
        // b에는 c 값을 대입
        b = c;
    }
    // 최대 공약수를 반환
    return a;
}

int main() {
    int a, b;

    cout << "두 정수를 입력하세요: ";
    cin >> a >> b;

    // 최대 공약수를 계산하고 출력
    cout << a << "와 " << b << "의 최대 공약수는: " << gcd(a, b) << "입니다." << endl;

    return 0;
}

코드: GCDProgram.go

package main

import "fmt"

// 두 정수 a와 b의 최대 공약수를 구하는 함수
func gcd(a, b int) int {
    var c int
    // b가 0이 아닐 때까지 반복
    for b != 0 {
        // a를 b로 나눈 나머지를 c에 저장
        c = a % b
        // a에는 b 값을 대입
        a = b
        // b에는 c 값을 대입
        b = c
    }
    // 최대 공약수를 반환
    return a
}

func main() {
    var a, b int

    fmt.Print("두 정수를 입력하세요: ")
    fmt.Scan(&a, &b)

    // 최대 공약수를 계산하고 출력
    fmt.Printf("%d와 %d의 최대 공약수는: %d입니다.\n", a, b, gcd(a, b))
}

코드: gcd_program.rs

use std::io;

// 두 정수 a와 b의 최대 공약수를 구하는 함수
fn gcd(mut a: i32, mut b: i32) -> i32 {
    while b != 0 {
        let c = a % b;
        a = b;
        b = c;
    }
    a
}

fn main() {
    let mut input = String::new();
    let a: i32;
    let b: i32;

    println!("두 정수를 입력하세요: ");
    io::stdin()
        .read_line(&mut input)
        .expect("Failed to read input.");
    let numbers: Vec<i32> = input
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();
    a = numbers[0];
    b = numbers[1];

    // 최대 공약수를 계산하고 출력
    println!("{0}와 {1}의 최대 공약수는: {2}입니다.", a, b, gcd(a, b));
}

코드: gcdProgram.ts

// 두 정수 a와 b의 최대 공약수를 구하는 함수
function gcd(a: number, b: number): number {
    let c: number;
    // b가 0이 아닐 때까지 반복
    while (b !== 0) {
        // a를 b로 나눈 나머지를 c에 저장
        c = a % b;
        // a에는 b 값을 대입
        a = b;
        // b에는 c 값을 대입
        b = c;
    }
    // 최대 공약수를 반환
    return a;
}

function main(): void {
    let a: number;
    let b: number;

    const readline = require('readline').createInterface({
        input: process.stdin,
        output: process.stdout
    });

    readline.question('두 정수를 입력하세요: ', (input: string) => {
        const inputs = input.split(' ');
        a = parseInt(inputs[0]);
        b = parseInt(inputs[1]);
        // 최대 공약수를 계산하고 출력
        console.log(`${a}와 ${b}의 최대 공약수는: ${gcd(a, b)}입니다.`);
        readline.close();
    });
}

main();

코드: GCDProgram.kt

import java.util.Scanner

// 두 정수 a와 b의 최대 공약수를 구하는 함수
fun gcd(a: Int, b: Int): Int {
    var c: Int
    // b가 0이 아닐 때까지 반복
    while (b != 0) {
        // a를 b로 나눈 나머지를 c에 저장
        c = a % b
        // a에는 b 값을 대입
        val temp = b
        a = temp
        // b에는 c 값을 대입
        b = c
    }
    // 최대 공약수를 반환
    return a
}

fun main() {
    var a: Int
    var b: Int

    val scanner = Scanner(System.`in`)
    print("두 정수를 입력하세요: ")
    a = scanner.nextInt()
    b = scanner.nextInt()

    // 최대 공약수를 계산하고 출력
    println("$a와 $b의 최대 공약수는: ${gcd(a, b)}입니다.")
}

서로소(공약수가 1인 경우)인 경우와 서로소가 아닌 경우에 대한 실행 결과는 다음과 같습니다.

서로소인 경우:

두 정수 7과 5를 입력하면 최대 공약수는 1입니다.

두 정수를 입력하세요: 7 5
7와 5의 최대 공약수는: 1입니다.

서로소가 아닌 경우:

두 정수 12와 8을 입력하면 최대 공약수는 4입니다.

두 정수를 입력하세요: 12 8
12와 8의 최대 공약수는: 4입니다.

위의 코드를 실행하면, 사용자로부터 두 개의 정수를 입력받아 최대 공약수를 구하여 출력합니다.

최소 공배수를 출력하는 프로그램

다음은 최소 공배수를 구하는 예제입니다. 이 프로그램은 두 정수의 최대 공약수를 먼저 계산한 후, 최소 공배수를 구하여 출력합니다. 여기서 최대 공약수를 구하는 함수는 유클리드 호제법을 사용하여 구현되어 있습니다.

유클리드 호제법은 두 정수의 최대공약수를 구하는 알고리즘으로, 두 수가 서로 상대방 수를 나누어 가며 나머지를 구하는 과정을 반복하다가 나머지가 0이 되는 시점의 나누는 수가 최대공약수입니다.

C 언어로 gcd 함수의 구현은 다음과 같습니다.

//
int gcd(int a, int b)
{
    // b가 0이면 a가 최대 공약수이므로 반환
    if (b == 0)
    {
        return a;
    }
    // b가 0이 아닌 경우, 재귀적으로 최대 공약수를 찾음
    return gcd(b, a % b);
}

b가 0이 될 때까지 a와 b의 값을 바꾸고, a를 b로 나눈 나머지를 다시 b로 넘기는 재귀적인 과정을 거치면서 최대공약수를 찾게 됩니다. 이렇게 재귀적으로 호출하며 계산하는 과정이 바로 유클리드 호제법입니다.

코드: lcm.c

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <stdlib.h>

// 두 정수 a와 b의 최대 공약수를 구하는 함수(재귀 함수 사용) 
int gcd(int a, int b)
{
    // b가 0이면 a가 최대 공약수이므로 반환
    if (b == 0)
    {
        return a;
    }
    // b가 0이 아닌 경우, 재귀적으로 최대 공약수를 찾음
    return gcd(b, a % b);
}

// 두 정수 a와 b의 최소 공배수를 구하는 함수
int lcm(int a, int b)
{
    // 최소 공배수 공식: a * b / gcd(a, b)
    return a * b / gcd(a, b);
}

int main(void)
{
    int a, b;
    // 두 정수를 입력받는 부분
    printf("두 숫자를 입력하세요: ");
    scanf("%d %d", &a, &b);
    // 최소 공배수를 계산하고 출력하는 부분
    printf("%d와 %d의 최소공배수는 %d입니다.\n", a, b, lcm(a, b));
    return 0;
}

코드: LeastCommonMultipleCalculator.cs

using System;

class LeastCommonMultipleCalculator
{
    // 두 정수 a와 b의 최대 공약수를 구하는 메서드(재귀 메서드 사용) 
    static int Gcd(int a, int b)
    {
        // b가 0이면 a가 최대 공약수이므로 반환
        if (b == 0)
        {
            return a;
        }
        // b가 0이 아닌 경우, 재귀적으로 최대 공약수를 찾음
        return Gcd(b, a % b);
    }

    // 두 정수 a와 b의 최소 공배수를 구하는 메서드
    static int Lcm(int a, int b)
    {
        // 최소 공배수 공식: a * b / gcd(a, b)
        return a * b / Gcd(a, b);
    }

    static void Main()
    {
        int a, b;

        Console.Write("두 숫자를 입력하세요: ");
        string input = Console.ReadLine();
        string[] inputs = input.Split();
        a = int.Parse(inputs[0]);
        b = int.Parse(inputs[1]);

        // 최소 공배수를 계산하고 출력하는 부분
        Console.WriteLine("{0}와 {1}의 최소공배수는 {2}입니다.", a, b, Lcm(a, b));
    }
}

코드: LCMProgram.java

import java.util.Scanner;

class LCMProgram {
    // 두 정수 a와 b의 최대 공약수를 구하는 함수(재귀 함수 사용) 
    static int gcd(int a, int b) {
        // b가 0이면 a가 최대 공약수이므로 반환
        if (b == 0) {
            return a;
        }
        // b가 0이 아닌 경우, 재귀적으로 최대 공약수를 찾음
        return gcd(b, a % b);
    }

    // 두 정수 a와 b의 최소 공배수를 구하는 함수
    static int lcm(int a, int b) {
        // 최소 공배수 공식: a * b / gcd(a, b)
        return a * b / gcd(a, b);
    }

    public static void main(String[] args) {
        int a, b;

        Scanner scanner = new Scanner(System.in);
        System.out.print("두 숫자를 입력하세요: ");
        a = scanner.nextInt();
        b = scanner.nextInt();

        // 최소 공배수를 계산하고 출력하는 부분
        System.out.printf("%d와 %d의 최소공배수는 %d입니다.\n", a, b, lcm(a, b));
    }
}

코드: LCMProgram.py

# 두 정수 a와 b의 최대 공약수를 구하는 함수(재귀 함수 사용)
def gcd(a, b):
    # b가 0이면 a가 최대 공약수이므로 반환
    if b == 0:
        return a
    # b가 0이 아닌 경우, 재귀적으로 최대 공약수를 찾음
    return gcd(b, a % b)

# 두 정수 a와 b의 최소 공배수를 구하는 함수
def lcm(a, b):
    # 최소 공배수 공식: a * b / gcd(a, b)
    return a * b // gcd(a, b)

a, b = map(int, input("두 숫자를 입력하세요: ").split())

# 최소 공배수를 계산하고 출력하는 부분
print("{0}와 {1}의 최소공배수는 {2}입니다.".format(a, b, lcm(a, b)))

코드: LCMProgram.html

<!DOCTYPE html>
<html>

<head>
    <meta charset="UTF-8">
    <title>LCM Program</title>
    <script>
        // 두 정수 a와 b의 최대 공약수를 구하는 함수(재귀 함수 사용)
        function gcd(a, b) {
            // b가 0이면 a가 최대 공약수이므로 반환
            if (b == 0) {
                return a;
            }
            // b가 0이 아닌 경우, 재귀적으로 최대 공약수를 찾음
            return gcd(b, a % b);
        }

        // 두 정수 a와 b의 최소 공배수를 구하는 함수
        function lcm(a, b) {
            // 최소 공배수 공식: a * b / gcd(a, b)
            return a * b / gcd(a, b);
        }

        function calculate() {
            // 입력한 두 숫자를 가져와서 최소 공배수를 계산하고 출력
            let a = parseInt(document.getElementById("num1").value);
            let b = parseInt(document.getElementById("num2").value);
            let result = lcm(a, b);
            document.getElementById("result").innerHTML = `${a}와 ${b}의 최소공배수는 ${result}입니다.`;
        }
    </script>
</head>

<body>
    <h1>LCM Program</h1>
    <p>
        두 숫자를 입력하세요:
        <input type="number" id="num1" />
        <input type="number" id="num2" />
        <button onclick="calculate()">계산</button>
    </p>
    <p id="result"></p>
</body>

</html>

코드: LCMProgram.cpp

#include <iostream>

// 두 정수 a와 b의 최대 공약수를 구하는 함수(재귀 함수 사용)
int gcd(int a, int b) {
    // b가 0이면 a가 최대 공약수이므로 반환
    if (b == 0) {
        return a;
    }
    // b가 0이 아닌 경우, 재귀적으로 최대 공약수를 찾음
    return gcd(b, a % b);
}

// 두 정수 a와 b의 최소 공배수를 구하는 함수
int lcm(int a, int b) {
    // 최소 공배수 공식: a * b / gcd(a, b)
    return a * b / gcd(a, b);
}

int main() {
    int a, b;

    std::cout << "두 숫자를 입력하세요: ";
    std::cin >> a >> b;

    // 최소 공배수를 계산하고 출력하는 부분
    std::cout << a << "와 " << b << "의 최소공배수는 " << lcm(a, b) << "입니다." << std::endl;

    return 0;
}

코드: LCMProgram.go

package main

import "fmt"

// 두 정수 a와 b의 최대 공약수를 구하는 함수(재귀 함수 사용)
func gcd(a int, b int) int {
    // b가 0이면 a가 최대 공약수이므로 반환
    if b == 0 {
        return a
    }
    // b가 0이 아닌 경우, 재귀적으로 최대 공약수를 찾음
    return gcd(b, a%b)
}

// 두 정수 a와 b의 최소 공배수를 구하는 함수
func lcm(a int, b int) int {
    // 최소 공배수 공식: a * b / gcd(a, b)
    return a * b / gcd(a, b)
}

func main() {
    var a, b int

    fmt.Print("두 숫자를 입력하세요: ")
    fmt.Scanf("%d %d", &a, &b)

    // 최소 공배수를 계산하고 출력하는 부분
    fmt.Printf("%d와 %d의 최소공배수는 %d입니다.\n", a, b, lcm(a, b))
}

코드: lcm_program.rs

use std::io;

// 두 정수 a와 b의 최대 공약수를 구하는 함수(재귀 함수 사용)
fn gcd(a: i32, b: i32) -> i32 {
    // b가 0이면 a가 최대 공약수이므로 반환
    if b == 0 {
        return a;
    }
    // b가 0이 아닌 경우, 재귀적으로 최대 공약수를 찾음
    return gcd(b, a % b);
}

// 두 정수 a와 b의 최소 공배수를 구하는 함수
fn lcm(a: i32, b: i32) -> i32 {
    // 최소 공배수 공식: a * b / gcd(a, b)
    return a * b / gcd(a, b);
}

fn main() {
    let mut a = String::new();
    let mut b = String::new();

    println!("두 숫자를 입력하세요:");
    io::stdin().read_line(&mut a).expect("입력 에러");
    io::stdin().read_line(&mut b).expect("입력 에러");

    let a: i32 = a.trim().parse().expect("정수를 입력해주세요.");
    let b: i32 = b.trim().parse().expect("정수를 입력해주세요.");

    // 최소 공배수를 계산하고 출력하는 부분
    println!("{}와 {}의 최소공배수는 {}입니다.", a, b, lcm(a, b));
}

코드: LCMProgram.ts

// 두 정수 a와 b의 최대 공약수를 구하는 함수(재귀 함수 사용)
function gcd(a: number, b: number): number {
    // b가 0이면 a가 최대 공약수이므로 반환
    if (b == 0) {
        return a;
    }
    // b가 0이 아닌 경우, 재귀적으로 최대 공약수를 찾음
    return gcd(b, a % b);
}

// 두 정수 a와 b의 최소 공배수를 구하는 함수
function lcm(a: number, b: number): number {
    // 최소 공배수 공식: a * b / gcd(a, b)
    return a * b / gcd(a, b);
}

let a: number = parseInt(prompt("첫 번째 숫자를 입력하세요."));
let b: number = parseInt(prompt("두 번째 숫자를 입력하세요."));

// 최소 공배수를 계산하고 출력하는 부분
console.log(`${a}와 ${b}의 최소공배수는 ${lcm(a, b)}입니다.`);

코드: LCMProgram.kt

import java.util.*

// 두 정수 a와 b의 최대 공약수를 구하는 함수(재귀 함수 사용)
fun gcd(a: Int, b: Int): Int {
    // b가 0이면 a가 최대 공약수이므로 반환
    if (b == 0) {
        return a;
    }
    // b가 0이 아닌 경우, 재귀적으로 최대 공약수를 찾음
    return gcd(b, a % b);
}

// 두 정수 a와 b의 최소 공배수를 구하는 함수
fun lcm(a: Int, b: Int): Int {
    // 최소 공배수 공식: a * b / gcd(a, b)
    return a * b / gcd(a, b);
}

fun main(args: Array<String>) {
    val input = Scanner(System.`in`)
    print("두 숫자를 입력하세요: ")
    val a = input.nextInt()
    val b = input.nextInt()

    // 최소 공배수를 계산하고 출력하는 부분
    println("$a와 $b의 최소공배수는 ${lcm(a, b)}입니다.")
}

실행은 프로그래밍 언어마다 차이점이 있으나 다음과 같은 형태로 테스트하면 됩니다.

두 숫자를 입력하세요: 4 5
4와 5의 최소공배수는 20입니다.

두 숫자를 입력하세요: 6 8
6와 8의 최소공배수는 24입니다.

이 프로그램은 두 개의 함수를 사용합니다. gcd 함수는 유클리드 호제법을 이용한 재귀 호출을 사용하여 두 정수의 최대 공약수를 구하는데 사용되며, lcm 함수에서는 최소 공배수를 계산합니다. main 함수에서는 사용자로부터 두 수를 입력받고, lcm 함수를 호출하여 최소 공배수를 계산한 후 결과를 출력합니다.

위의 결과에서 볼 수 있듯이, 프로그램은 입력된 두 수에 대한 최소 공배수를 올바르게 계산하고 출력합니다. 이를 통해 서로소인 경우와 서로소가 아닌 경우에 대한 최소 공배수를 확인할 수 있습니다.

최대공약수와 최소공배수 함께 출력하기

이번 예제에서는 최대공약수와 최소공배수를 함께 구하는 프로그램을 작성합니다. 최대 공약수를 구하는 함수에서는 삼항 연산자를 사용하여 코드를 간결하게 표현해 보았습니다.

코드: gcd_lcm.c

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>

// 두 정수 a와 b의 최대 공약수를 구하는 함수 (재귀 사용)
int gcd(int a, int b)
{
    // b가 0이면 a가 최대 공약수이므로 반환, 그렇지 않으면 재귀적으로 최대 공약수 찾음
    return b == 0 ? a : gcd(b, a % b);
}

// 두 정수 a와 b의 최소 공배수를 구하는 함수
int lcm(int a, int b)
{
    // 최소 공배수 공식: a * b / gcd(a, b)
    return a * b / gcd(a, b);
}

int main(void)
{
    int a, b;

    printf("두 개의 정수 입력: ");
    scanf("%d %d", &a, &b);

    // 최대 공약수를 계산하고 출력
    printf("최대 공약수: %d\n", gcd(a, b));
    // 최소 공배수를 계산하고 출력
    printf("최소 공배수: %d\n", lcm(a, b));

    return 0;
}

코드: GCDLCMCalculator.cs

using System;

class GCDLCMCalculator
{
    // 두 정수 a와 b의 최대 공약수를 구하는 함수 (재귀 사용)
    static int GCD(int a, int b)
    {
        // b가 0이면 a가 최대 공약수이므로 반환, 그렇지 않으면 재귀적으로 최대 공약수 찾음
        return b == 0 ? a : GCD(b, a % b);
    }

    // 두 정수 a와 b의 최소 공배수를 구하는 함수
    static int LCM(int a, int b)
    {
        // 최소 공배수 공식: a * b / gcd(a, b)
        return a * b / GCD(a, b);
    }

    static void Main()
    {
        int a, b;

        Console.Write("두 개의 정수 입력: ");
        string[] input = Console.ReadLine().Split(' ');
        a = int.Parse(input[0]);
        b = int.Parse(input[1]);

        // 최대 공약수를 계산하고 출력
        Console.WriteLine("최대 공약수: {0}", GCD(a, b));
        // 최소 공배수를 계산하고 출력
        Console.WriteLine("최소 공배수: {0}", LCM(a, b));
    }
}

코드: GCDLCMProgram.java

import java.util.Scanner;

public class GCDLCMProgram {
    // 두 정수 a와 b의 최대 공약수를 구하는 함수 (재귀 사용)
    static int gcd(int a, int b) {
        // b가 0이면 a가 최대 공약수이므로 반환, 그렇지 않으면 재귀적으로 최대 공약수 찾음
        return b == 0 ? a : gcd(b, a % b);
    }

    // 두 정수 a와 b의 최소 공배수를 구하는 함수
    static int lcm(int a, int b) {
        // 최소 공배수 공식: a * b / gcd(a, b)
        return a * b / gcd(a, b);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("두 개의 정수 입력: ");
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        // 최대 공약수를 계산하고 출력
        System.out.println("최대 공약수: " + gcd(a, b));
        // 최소 공배수를 계산하고 출력
        System.out.println("최소 공배수: " + lcm(a, b));

        scanner.close();
    }
}

코드: GCDLCMProgram.py

# 두 정수 a와 b의 최대 공약수를 구하는 함수 (재귀 사용)
def gcd(a, b):
    # b가 0이면 a가 최대 공약수이므로 반환, 그렇지 않으면 재귀적으로 최대 공약수 찾음
    return a if b == 0 else gcd(b, a % b)

# 두 정수 a와 b의 최소 공배수를 구하는 함수
def lcm(a, b):
    # 최소 공배수 공식: a * b / gcd(a, b)
    return a * b // gcd(a, b)

a, b = map(int, input("두 개의 정수 입력: ").split())

# 최대 공약수를 계산하고 출력
print("최대 공약수:", gcd(a, b))
# 최소 공배수를 계산하고 출력
print("최소 공배수:", lcm(a, b))

코드: GCDLCMProgram.js

// 두 정수 a와 b의 최대 공약수를 구하는 함수 (재귀 사용)
function gcd(a, b) {
    // b가 0이면 a가 최대 공약수이므로 반환, 그렇지 않으면 재귀적으로 최대 공약수 찾음
    return b == 0 ? a : gcd(b, a % b);
}

// 두 정수 a와 b의 최소 공배수를 구하는 함수
function lcm(a, b) {
    // 최소 공배수 공식: a * b / gcd(a, b)
    return a * b / gcd(a, b);
}

let input = prompt("두 개의 정수 입력 (예: 10 20):");
let [a, b] = input.split(" ").map(Number);

// 최대 공약수를 계산하고 출력
console.log("최대 공약수: " + gcd(a, b));
// 최소 공배수를 계산하고 출력
console.log("최소 공배수: " + lcm(a, b));

코드: GCDLCMProgram.cpp

#include <iostream>

using namespace std;

// 두 정수 a와 b의 최대 공약수를 구하는 함수 (재귀 사용)
int gcd(int a, int b) {
    // b가 0이면 a가 최대 공약수이므로 반환, 그렇지 않으면 재귀적으로 최대 공약수 찾음
    return b == 0 ? a : gcd(b, a % b);
}

// 두 정수 a와 b의 최소 공배수를 구하는 함수
int lcm(int a, int b) {
    // 최소 공배수 공식: a * b / gcd(a, b)
    return a * b / gcd(a, b);
}

int main() {
    int a, b;

    cout << "두 개의 정수 입력: ";
    cin >> a >> b;

    // 최대 공약수를 계산하고 출력
    cout << "최대 공약수: " << gcd(a, b) << endl;
    // 최소 공배수를 계산하고 출력
    cout << "최소 공배수: " << lcm(a, b) << endl;

    return 0;
}

코드: GCDLCMProgram.go

package main

import (
    "fmt"
)

// 두 정수 a와 b의 최대 공약수를 구하는 함수 (재귀 사용)
func gcd(a, b int) int {
    // b가 0이면 a가 최대 공약수이므로 반환, 그렇지 않으면 재귀적으로 최대 공약수 찾음
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

// 두 정수 a와 b의 최소 공배수를 구하는 함수
func lcm(a, b int) int {
    // 최소 공배수 공식: a * b / gcd(a, b)
    return a * b / gcd(a, b)
}

func main() {
    var a, b int

    fmt.Print("두 개의 정수 입력: ")
    fmt.Scan(&a, &b)

    // 최대 공약수를 계산하고 출력
    fmt.Println("최대 공약수:", gcd(a, b))
    // 최소 공배수를 계산하고 출력
    fmt.Println("최소 공배수:", lcm(a, b))
}

코드: gcd_lcm_program.rs

use std::io;

// 두 정수 a와 b의 최대 공약수를 구하는 함수 (재귀 사용)
fn gcd(a: i32, b: i32) -> i32 {
    // b가 0이면 a가 최대 공약수이므로 반환, 그렇지 않으면 재귀적으로 최대 공약수 찾음
    if b == 0 {
        return a;
    }
    return gcd(b, a % b);
}

// 두 정수 a와 b의 최소 공배수를 구하는 함수
fn lcm(a: i32, b: i32) -> i32 {
    // 최소 공배수 공식: a * b / gcd(a, b)
    return a * b / gcd(a, b);
}

fn main() {
    let mut input = String::new();

    println!("두 개의 정수 입력:");
    io::stdin().read_line(&mut input).unwrap();
    let vec: Vec<i32> = input.split_whitespace()
                            .map(|s| s.parse().unwrap())
                            .collect();

    // 최대 공약수를 계산하고 출력
    println!("최대 공약수: {}", gcd(vec[0], vec[1]));
    // 최소 공배수를 계산하고 출력
    println!("최소 공배수: {}", lcm(vec[0], vec[1]));
}

코드: GCDLCMProgram.ts

// 두 정수 a와 b의 최대 공약수를 구하는 함수 (재귀 사용)
function gcd(a: number, b: number): number {
    // b가 0이면 a가 최대 공약수이므로 반환, 그렇지 않으면 재귀적으로 최대 공약수 찾음
    return b == 0 ? a : gcd(b, a % b);
}

// 두 정수 a와 b의 최소 공배수를 구하는 함수
function lcm(a: number, b: number): number {
    // 최소 공배수 공식: a * b / gcd(a, b)
    return a * b / gcd(a, b);
}

const readline = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});

readline.question("두 개의 정수 입력: ", input => {
    const [a, b] = input.split(" ").map(Number);

    // 최대 공약수를 계산하고 출력
    console.log(`최대 공약수: ${gcd(a, b)}`);
    // 최소 공배수를 계산하고 출력
    console.log(`최소 공배수: ${lcm(a, b)}`);

    readline.close();
});

코드: GCDLCMProgram.kt

import java.util.Scanner

// 두 정수 a와 b의 최대 공약수를 구하는 함수 (재귀 사용)
fun gcd(a: Int, b: Int): Int {
    // b가 0이면 a가 최대 공약수이므로 반환, 그렇지 않으면 재귀적으로 최대 공약수 찾음
    return if (b == 0) a else gcd(b, a % b)
}

// 두 정수 a와 b의 최소 공배수를 구하는 함수
fun lcm(a: Int, b: Int): Int {
    // 최소 공배수 공식: a * b / gcd(a, b)
    return a * b / gcd(a, b)
}

fun main(args: Array<String>) {
    val input = Scanner(System.`in`)

    print("두 개의 정수 입력: ")
    val a = input.nextInt()
    val b = input.nextInt()

    // 최대 공약수를 계산하고 출력
    println("최대 공약수: ${gcd(a, b)}")
    // 최소 공배수를 계산하고 출력
    println("최소 공배수: ${lcm(a, b)}")
}

두 개의 정수 입력: 12 15
최대 공약수: 3
최소 공배수: 60

이 예제 프로그램은 두 개의 정수를 입력받고, 최대공약수와 최소공배수를 계산하여 출력합니다. gcd 함수를 통해 최대공약수를 구하고, lcm 함수를 사용해 최소공배수를 계산합니다.

더 깊이 공부하고 싶다면

DevLec에서는 실무 중심의 C#, .NET, ASP.NET Core, Blazor, 데이터 액세스 강좌를 단계별로 제공합니다. 현재 수강 가능한 강좌 외에도 더 많은 과정이 준비되어 있습니다.
DevLec.com에서 자세한 커리큘럼을 확인해 보세요.

DevLec 공식 강의

C# Programming

C# 프로그래밍 입문

프로그래밍을 처음 시작하는 입문자를 위한 C# 기본기 완성 과정입니다.

ASP.NET Core 10.0

ASP.NET Core 10.0 시작하기 MVC Fundamentals Part 1 MVC Fundamentals Part 2

웹 애플리케이션의 구조와 MVC 패턴을 ASP.NET Core로 실습하며 익힐 수 있습니다.

Blazor Server

풀스택 웹개발자 과정 Part 1 풀스택 웹개발자 과정 Part 2 풀스택 웹개발자 과정 Part 3

실무에서 바로 활용 가능한 Blazor Server 기반 관리자·포털 프로젝트를 만들어 봅니다.

Data & APIs

Entity Framework Core 시작하기 ADO.NET Fundamentals Blazor Server Fundamentals Minimal APIs

데이터 액세스와 Web API를 함께 이해하면 실무 .NET 백엔드 개발에 큰 도움이 됩니다.

추천 자료: ASP.NET Core 인증 및 권한 부여

추천 자료: .NET Blazor에 대해 알아보시겠어요? .NET Blazor 알아보기를 확인해보세요!