관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/수리

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

막무가내막내 2020. 10. 12. 20:47
728x90

www.acmicpc.net/problem/11653

 

11653번: 소인수분해

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

www.acmicpc.net

 

 

 

백준 수학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번: 최대공약수와 최소공배수

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

www.acmicpc.net

 

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

 

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));
    }
}
728x90
Comments