JArchive 프로그래밍 일기

문제

소인수분해 백준 11653번

리뷰

가장 작은 소수 2부터 루트 N까지 나눠보면서 소인수분해 한다.

루트 N까지 나누는 이유는 에라토스테네스의 체를 풀어보면 알 수 있다.

미리 N까지의 모든 소수를 구해놓지 않고서도 반복문만으로 풀 수 있는 문제다.

for(int i = 2; i*i <= N; i++){  // 나누어 떨어지지 않는다면 i 증가 

    while( N % i == 0){ // 나누어 떨어진다면 출력 
        printf("%d\n", i);
        N /= i;
    }
}

예를 들어, N=12 인 경우

12는 2로 나누어 떨어지므로. 2 출력. N == 6

6은 2로 나누어 떨어지므로 2 출력. N == 3

이 때, 루트 N은 3과 4 사이의 값이다. 이미 N을 초과해버린다. 그래서 N이 3인채로 반복문이 종료된다.

따라서 for문이 끝나고 나서 N이 1 초과인 경우에 N을 출력 해줘야 한다.

    for(int i = 2; i*i <= N; i++){  // 나누어 떨어지지 않는다면 i 증가 

        while( N % i == 0){ // 나누어 떨어진다면 출력 
            printf("%d\n", i);
            N /= i;
        }
    }

    if(N > 1) cout << N;  // 위의 반복문이 i*i <= N 까지 동작하기 때문.

맞은 코드 1

#include <iostream> 
using namespace std;

int main(void){

     int N = 0;
    int i = 2; 

    cin >> N;

    if(N == 1) return 0; // 1은 소수가 아니다 

    for(int i = 2; i*i <= N; i++){  // 나누어 떨어지지 않는다면 i 증가 

        while( N % i == 0){ // 나누어 떨어진다면 출력 
            printf("%d\n", i);
            N /= i;
        }
    }

    if(N > 1) cout << N;  // 위의 반복문이 i*i <= N 까지 동작하기 때문.

    return 0;    
} 

맞은 코드 2

N이 더 이상 나눠지지 않을 때 까지 i로 나눈다

#include <iostream> 
using namespace std;

// 소인수분해 11653 

int main(void){

     int N = 0;

    cin >> N;

    if(N == 1) return 0;

    int i = 2; 

    while( N>1 ){

        if( N % i == 0){
            printf("%d\n", i);
            N /= i;
        }else{
            i++;
        }
    }
    return 0;    
}