[C/C++] 백준 #2312 수 복원하기(수학)

소인수 분해하는 것은 어렵지 않게 할 수는 있습니다.  물론 소수를 구해서 하면 더 좋겠지만, 소수를 별도로 구하지 않아도 소인수 분해를 할 수 있습니다.

 

문제의 링크입니다.

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

2312번: 수 복원하기

 

prime factors

 

소인수 분해를 할 때에는 n의 숫자의 제곱근까지만 하면 됩니다.  예를 들어서 12를 소인수 분해하기 위해서는 2부터 시작합니다.  12의 제곱근은 3보다는 크고 4보다는 작겠죠.  즉, 3까지만 하면 됩니다.  하지만, 제 알고리즘은 그 전에 끝나게 됩니다.  12를 2로 계속 나누면, 2번 나눌 수 있고, 나머지는 3입니다.  다음엔 3을 검사하려니 3의 제곱값은 3보다 큽니다.  그러면 거기서 멈추면 됩니다.  소인수 분해하는데 시간 복잡도는 \(O(\sqrt{N})\)입니다.  웬만큼 큰 숫자가 와도 빠르게 끝낼 수 있습니다.  최악의 경우에는 소수가 들어온 경우입니다.  이 경우에도 시간 복잡도는 \(O(\sqrt{N})\) 이 됩니다.

 

다음은 제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2312
//        - by Aubrey Choi
//        - created at 2019-08-02
//------------------------------------------------
#include <stdio.h>

void sigma(int n)
{
    if(n%2==0)
    {
        int c=0;
        while(n%2==0) c++,n/=2;
        printf("2 %d\n", c);
    }
    for(int p=3; p*p <= n; p+=2)
    {
        if(n%p==0)
        {
            int c=0;
            while(n%p==0) c++,n/=p;
            printf("%d %d\n", p, c);
        }
    }
    if(n>1) printf("%d 1\n", n);
}

int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        sigma(n);
    }
    return 0;
}