[11653] 소인수분해

11653 문제 링크

📌 문제

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

---

📌 입력

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

---

📌 출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다.

---

💡 풀이

문제는 정말 쉬운 문제였는데 나는 그저 에라토스테네스의 체에만 꽂혀서
소수 판별 배열을 만든 후 입력 숫자를 2부터 나눠가며 소인수를 찾도록 했다.
2부터 N을 계속 나눠주기만 하면 2의 배수로는 당연히 나눠지지 않기 때문에 소수를 판별할 필요가 없다!!

📎 처음 코드

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int[] prime;
    static int N;

    public static void main(String[] args) throws Exception {
        prime = new int[10000000];

        prime[0] = 1;
        prime[1] = 1;
        for (int i = 2; i < 10000000; i++) {
            if (prime[i] == 1) continue;
            for (int j = 2 * i; j < 10000000; j += i) {
                prime[j] = 1;
            }
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());


        find(N,2);

        System.out.println(sb);
    }

    private static void find(int n,int prime) {

        if(prime==-1) return;
        if(n==0) return;

        while (true) {

            if(n%prime==0){
                sb.append(prime).append("\n");
                n /= prime;
            }
            else{
                find(n,nextPrime(prime));
                return;
            }
            if(n==1) return;
        }

    }

    private static int nextPrime(int p) {

        for (int i = p+1; i <= N; i++) {
            if(prime[i]==0) return i;
        }

        return -1;
    }
}

📎 코드2

public class Main {

	public static void main(String[] args) throws Exception {
    
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        for (int i = 2; i <= Math.sqrt(N); i++) { 
        	//제일 작은 소수인 2부터 N을 나눠질 때 까지 나눈다.
        	while ( N % i == 0) { //나머지가 0일 때까지
            	System.out.println(i);
                N /= i;
            }
        }
        
        /* for문을 돌았는데도 N이 1이 아니라는 건?
        인수분해가 완료되지 않았다는 뜻!
        */
        if (N != 1) System.out.println(N); 
     }
}

이렇게 간단한 문제를 너무 어렵게 풀었다...ㅎㅎ.. 쉽게 생각 하자~