백준 - 11653번 - 소인수분해

11653번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static boolean[] prime;

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int A = Integer.parseInt(bf.readLine());

		if (A == 1) {
			System.out.println();
		} else {
			makePrime(A);
			while (isPrime(A) == false) {
				for (int i = 2; i<prime.length; i++) {
					if (prime[i] == false) {
						if (A % i == 0) {
							A = A / i;
							System.out.println(i);
							break;
						}
					}
				}
			}
			System.out.println(A);
		}
	}

	static boolean[] makePrime(int B) {

		prime = new boolean[B+1];

		prime[0] = true;
		prime[1] = true;

		for (int i = 2; i<=Math.sqrt(B); i++) {
			if (prime[i]) {
				continue;
			}

			for (int j = i * i; j<B+1; j=j+i) {
				prime[j] = true;
			}
		}
		return prime;
	}

	static boolean isPrime(int N) {

		if (N == 1) {
			return false;
		}

		for (int i = 2; i<=Math.sqrt(N); i++) {
			if (N % i == 0) {
				return false;
			}
		}

		return true;
	}
}

풀이

---

입력받은 수가 1이면 아무것도 출력하지않고 1보다 큰수면 소인수분해해서 나온수를 한줄씩 출력하는 문제다.

문제의 핵심은 가장작은 소수부터 나눠보기 시작해야하고 그렇게 나온 몫이 소수이면 그만 두는것이다.

그래서 에라토스테네스의 채로 입력받은수보다 작은 소수를 판별했고 해당 수가 소수인지 판별하는 메서드를 만들었다.

for (int i = 2; i<prime.length; i++) {
					if (prime[i] == false) {
						if (A % i == 0) {
							A = A / i;
							System.out.println(i);
							break;
						}
					}
				}

위의 코드에서 제일작은 소수로 나누었다면 다시 제일 작은 소수로 나누기위해 for문을 빠져나가는 break를 사용했다.

다른풀이

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
 
		for (int i = 2; i <= Math.sqrt(N); i++) {
			while (N % i == 0) {
				sb.append(i).append('\n');
				N /= i;
			}
		}
		if (N != 1) {
			sb.append(N);
		}
		System.out.println(sb);
	}
}

입력받은 수가 소수인지 판별할 필요는 없었다. 그냥 소수로 더이상 나누어지지 않을때까지 나누면 됐다.

그리고 내 코드에서 사용한 for문과 break도 위 while로 대체하면 훨씬 효율적일거라 생각한다...