[알고리즘] 백준 11653 소인수분해, 2609 최대공약수와 최소공배수 -수학3- 자바

www.acmicpc.net/problem/11653

11653번: 소인수분해

 

 

 

백준 수학3 의 단계별풀기를 하고 있는데 소인수분해와 최대공약수 최소공배수  관련 문제가 나와 기록으로 남깁니다.

 

먼저 소인수분해문제입니다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                System.out.println(i);
                n /= i;
            }
        }
        if (n > 1) {
            System.out.println(n);
        }
    }
}

 

 

 

 

 

www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

두번째로 최대공약수 최소공배수 문제입니다.

 

import java.util.Scanner;

public class Main {

    // 최대공약수
    public static int gcd(int x, int y) {
        while (y > 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }

    // 최소공배수
    public static int lcm(int x, int y) {
        return (x * y) / gcd(x, y);
    }

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