Java/Algorithm

[Java-Algorithm] 백준 11653 소인수 분해 풀이

Jeong Jeon
반응형

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

 

11653번: 소인수분해

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

www.acmicpc.net

 

풀이 : 

소인수분해는 어떤건지 다들 아실거라 생각한다.

간단하게 while문만으로 나눠주는 값을 하나씩 증가시키면서 나눠보려고 했는데 시간초과가 떴다...

뭐지...?

 

해당코드..

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int i = 2;
        while(N >= i) {
            if(N % i == 0) {
                System.out.println(i);
                N /= i;
            } else {
                i++;
            }
        }
    }

 

다른 방법이 또 있나 보다가 다른 사람 풀이를 조금 봤는데, 제곱수의 개념을 넣은것같다.

해당 방법으로는 통과...

뭔가 찜찜해서 내코드로 다시 돌렸는데 뭐임...

맞았습니다.... -_- 아니 장난치는것도 아니고 ㅠㅠ 속상할뻔 ㅎㅎ

public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
 
		int N = in.nextInt();
 
		StringBuilder sb = new StringBuilder();
 
		for (int i = 2; i * i <= N; i++) {
			while (N % i == 0) {
				sb.append(i).append('\n');
				N /= i;
			}
		}
		
		if (N != 1) {
			sb.append(N);
		}
		System.out.println(sb);
	}
반응형