(Java) 백준 11653번 - 소인수분해

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

문제

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

접근

소인수분해는 어떤 수를 소수들의 곱으로 표현하는 것이므로 주어진 수를 소수인지 판별하고 맞으면 그대로 출력, 아니면 2부터 증가하는 수로 나눠질 때까지 나누고 갱신 된 수에 이 과정을 반복해 1이 될 때 까지 한다.

문제해결

> 수가 2보다 작으면 소수가 아니므로 false를 반환하고
2보다 크고 N의 제곱수이한인 수 중 하나로 나눠지면 또 fasle를 반환하고
아니면 true를 반환해 소수라고 판정하는 메소드를 만든다.
> 어떤 수가 1보다 클 때까지 반복하는데 일단 그 수가 소수인지 본다.
> 소수라면 해당 수를 자기 자신으로 나누고 아니라면 2부터 해당 수 까지 하나씩 나누어본다.
> 나누어 떨어지면 그 수를 소인수로 가진다는 뜻이므로 출력한다.
> 이 과정을 N이 전부 나누어져 1이될 때까지 반복한다.

코드

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main
{
    //11653번 소인수분해
    static boolean prime(int n)
    {
        if(n < 2) return false;
        for(int i = 2; i * i <= n; i++) if(n % i == 0) return false;
        return true;
    }
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while(N > 1)
        {
            if(prime(N)) //소수면
            {
                sb.append(N).append('\n');
                N /= N;
                continue;
            }
            for(int i = 2; i <= N; i++)
            {
                if(N % i == 0)
                {
                    sb.append(i).append('\n');
                    N /= i;
                    break;
                }
            }
        }
        System.out.print(sb);
    }
}

후기

내 코드상 만약 2로 나누어지면 반복문을 깨고 다시 while문에서 돌아와 또 2부터 for문을 시작한다. 이 과정이 너무 비효율 적이라고 생각했고 효율적으로 할 수 있게 알아봤다.
2부터 반복하는데 만약 어떤 수로 나누어 떨어지면, while문으로 들어가 해당 수로 안나눠떨어질 때까지 계속 나누면 된다.
그럼 예를들어 72는 2로 나눠서 36이되고, 또 2로 나눠서 18이 되고, 또 2로나눠서 9가 된다. 그리고 i++로 인해 i가 3이 되어 3을 나눠 3이 되고, 또 3으로 나눠 1이 된다.
이런