[백준 11653] 소인수분해

 

0. 소인수분해 정의

임의의 자연수 N을  마지막 나머지가 '1'이 나올 때 까지 '소수'로 나누어 곱으로 표현한 것.

 

EX)120이란 수를 소인수분해 한다면?

 

임의의 자연수 N, 몫 i 라고 두면

 

N이란 숫자를 몫 i로 나누어 떨어지는지 검사하고 나누어 떨어지면 

떨어지는 동안 계속 나누기/ 나누어 떨어지지 않으면 i + 1

 

N의 나머지가 1이될 때까지 (그림에서는 5에서 멈춤)

 

 

 

1. 문제

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

11653번: 소인수분해

2. 핵심 IDEA

Q. i(몫)의 범위?

저번 포스팅에서 

소수를 검사하는 아이디어에서 '에라토스테네스의 Idea'에서 살펴 보았듯이

임의의 자연수 N이 제곱근 이하에서 소수로 나누어지면 N은 소수가 아니다.

제곱근을 기점으로 좌우 곱이 대칭된다.

 8 = 1 * 8  2 * 4 4 * 2 8 * 1  << 8의 제곱근 보다 작거나 같은 수까지 검사하고 나머지는 대칭을 이룸.

 

∴ i는 <= sqrt(N) 까지 검사하면 된다. 대신 나머지 숫자가 1개 발생 할 수 있다.

ex) 6 => 2 * 3 (but 6의 제곱근 = 2.xxx 따라서 i가 3까지 증가시키지 않고 나머지가 3이 남음)

 

[Case 1  i<= N 검사]

=> 시간복잡도 O(N) 

 

[Case 2 i<= sqrt(N) 검사]

=> 시간복잡도

 

 

 

 

 

 

3. Mistake

i의 검사를 sqrt(N)까지 한다는 아이디어는 떠올렸는데

나머지가 1이상 발생할 수 있는 경우에 대해 고려하지 못해

6같은 케이스를 자꾸 '2'만 출력했었다.

 

 

4. 소스코드

#include <iostream>
#include <math.h>
using namespace std;
 
int main(void)
{
    int N;
    cin >> N;
    if(N == 1)
    return 0;
    
    for(int i = 2; i <= sqrt(N); i++) //i의 범위 sqrt(N)이해하기 (에라토스테네스의 체)
    {
        if(N % i==0)
        {
            N /= i; //이부분은 '몫'만 출력 
            cout << i << '\n';
            i--; // 나누어 떨어진 경우 숫자 그대로 맞춰주기 위함
        }
    }
    if(N > 1) cout << N << '\n'; // 1이상의 나머지 검사하여 출력
    
    return 0;
}