[백준 알고리즘] 11653번 / 소인수분해

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

 

입력

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

 

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

 

입출력 예제

입력	출력
72	2 2 2 3
3	3
6	2 3
2	2
9991	97 103

 

 

📢 문제는 아주 간단하지만 괜히 복잡하게 생각해서 한 번 틀린 문제였다.

소인수분해라길래 소수를 통해 판별하려고 괜히 (쓸데없이) 에라스토테네스의 체를 사용하였다.

 

https://mozzioi.tistory.com/127

[백준 알고리즘] 2960번 / 에라토스테네스의 체

 

 

하지만 결국은 런타임 에러! 😭

import java.util.Scanner;

public class No11653_Factorization {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		
		// N이 1인 경우 아무것도 출력 X
		if (n == 1)
			return;
		
		/* START: 1부터 n까지 소수 판별 */
		boolean[] primeNum = new boolean[n+1];
		
		for (int i = 2; i <= n; i++) {
			primeNum[i] = true;
		}
		
		for (int i = 2; i <= n; i++) {
			for (int j = i*i; j <= n; j+= i) {
				primeNum[j] = false;
			}
		}
		/* END: 1부터 n까지 소수 판별 */
		
		int i = 0;
		while (n > 1) {
			if (primeNum[i]) {
				if (n % i == 0) {
					System.out.println(i);
					n /= i;
				} else {
					i++;
				}
			} else {
				i++;
			}
		}
	}
}

 

입력 받을 수 있는 N의 최대 범위는 10000000 까지고,

10000000 입력 시 ArrayIndexOutOfBoundsException 을 맞고 말았다.

 

 

가장 좋은 알고리즘은 쉽고, 알아보기 편한데 효율적인 코드라고 생각한다.

좀 더 단순하게 하지만 효율적으로 생각해내는 연습이 매우 많이 필요한 것 같다 😳🥺

 

🌈 문제 풀이

import java.util.Scanner;
 
public class No11653_Factorization2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();
        
        // N이 1인 경우 아무것도 출력 X
        if (n == 1)
            return;
        
        int i = 2;
        while (n >= i) {
            if (n % i == 0) {
                System.out.println(i);
                n /= i;
            } else {
                i++;
            }
        }
        
        
    }
}
 

 

👩‍💻 풀어보기 👨‍💻 https://www.acmicpc.net/problem/11653

11653번: 소인수분해