[문제] 백준 11653번 소인수분해

* 출처: 백준 단계별로 풀어보기 기본수학 2

www.acmicpc.net/problem/11653

11653번: 소인수분해

 

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(in.readLine());
		
		int s = 2;
		while(true) {
			if(N == 1) return;
			if(isSosu(N)) {
				System.out.println(N);
				break;
			}
			
			if(N%s == 0) {
				System.out.println(s);
				N = N/s;
			}else {
				s++;
			}
		}
		
	}
	static boolean isSosu(int n) {
		if(n==1) return false;
		if(n==2) return true;
		
		for(int i=2;i<n;i++) {
			if(n%i == 0) {
				return false;
			}
		}
		return true;
	}
}

** 다른 사람 문제 풀이

 

어떤 N이 두 개 이상 곱셈으로 나타날 수 있을 때 인수 중 한개는 반드시 N^(1/2)보다 작거나 같다!

그래서 for문에서 순회하는 값의 범위가 2~루트N 까지로 해서 시간을 줄인 듯하다.

 

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(in.readLine());
		
		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);
		}