공부하기/백준

[Java] 백준 풀기 11653 - 소인수분해

XEV 2023. 7. 24. 23:54

자바 백준 11653

브론즈 1

https://www.acmicpc.net/problem/11653

 

11653번: 소인수분해

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

www.acmicpc.net

 

 

 

 

 

문제 보기

분류: 수학, 정수론, 소수 판정

 

 

 

 

 

문제 풀기

소인수분해는 주어진 정수 N을 소수인 i로 나누며, 나눌 수 없을 때까지 반복한다. 이때, i는 2부터 제곱근까지 검사한다.

 

N이 1인 경우 바로 return 한다. for loop과 while loop을 통해 정수 N을 나누어 떨어지는 소인수 i를 모두 출력하고, 최종 남은 소인수를 출력한다.

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();

        primeFactorization(N);
    }
    
    // 소인수분해 함수
    private static void primeFactorization(int N) {
        // N이 1인 경우 아무것도 출력하지 않음
        if (N == 1) {
            return;
        }
        
        // N의 제곱근까지만 검사
        for (int i = 2; i * i <= N; i++) {
            // 정수 N을 i로 나눌 수 없을때까지 반복
            while (N % i == 0) {
                System.out.println(i);
                N = N / i;
            }
        }
        
        // 마지막 소인수 출력
        if (N > 1) {
            System.out.println(N);
        }
    }
    
}