문제 번호 11653번 : 소인수분해 - JAVA [자바]

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

11653번: 소인수분해

 

문제 설명

 

주어진 수를 소수인수분해 한 후에 소인수 분해 한 수를 출력하는 문제입니다.

 

문제 풀이

소인수분해란 해당 수를 가장 작은 수로 분해하는 것을 말합니다.

예를 들어 18이란 숫자를 소인수분해 한다고 하면 가장 작은 수인 2로 나누면 9가 되고 9는 2로는 나눠지지 않으니 다음 큰 수인 3으로 나눠 2*3*3 = 9 라는 식을 만드는 것이 소인수분해 입니다. 여기서 저 곱들이 모두 소수여서 소인수분해라고 하는 것이죠. 

그럼 이것을 어떻게 로직으로 만들지 생각해 봅시다.

소인수분해는 가장 작은 순서대로 나눠 곱으로 만든다.

이것을 로직으로 만들 겁니다. 변수를 2부터(1은 당연히 분해할 수 없음으로 빼야합니다.) 해당 수까지 돌려서 그 수로 나누어 떨어지면 계속 그 수로 나눠보고 그 수로 나눠 떨어지 않게 되면 다음 수로 증가해 나누기를 진행합니다. 4로 나눠 떨어진다면 2로 이미 나눠졌을 것이고 6으로 나눠떨어진다면 이미 3으로 나눠 떨어졌을 테니깐요. 그래서 같은 수로 계속 나누는 과정이 필요합니다. 4로 나눠지거나 6으로 나눠지면 안되기 때문입니다.

여기서 조금 심하로 가자면 어떤 수(n)가 인수*인수가 된다면 즉 소수로 나눠진다면 그 소수는 √n 보다 같거나 작은 수입니다.(정확한 원리는 모르나 소인수분해의 정의에 나와있습니다.) 그래서 루트 만큼만 반복문을 돌리면 됩니다. 속도가 굉장히 빨라질 겁니다.

 

정답

import java.util.*;
import java.math.*;

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

코드에서 보시면 while문을 통해 해당 소수로 계속해서 나눠 그 소수로 이루어진 더 큰 수로 나눌 수 없도록 만들었습니다.

마지막에 n이 1이 아니면 해당 수를 출력하는 조건은 마지막 수가 깔끔하게 소수로 나눠지지 않을경우 남는 수를 출력하기 위해 만든 조건입니다.

 

감사합니다.