백준 11653 C#) 소인수분해

소인수분해 자체는 어렵지 않지만 이를 얼마나 빠르게 처리할 수 있는지가 관건이다.

 

int n = int.Parse(Console.ReadLine());
int n_sqrt = (int)Math.Sqrt(n);
int m = 2;

while (n != 1)
{
    if (n % m == 0)
    {
        Console.WriteLine(m);
        n /= m;
        n_sqrt = (int)Math.Sqrt(n);
        continue;
    }

    m++;

    if (m > n_sqrt)
    {
        Console.WriteLine(n);
        break;
    }    
}

 

정수 n이 주어지면 이를 m으로 계속 나눠보면 된다.

그러다 더 이상 m으로 나누어떨어지지 않으면 m을 1 증가시키고 다시 시도한다.

(도중에 m이 합성수가 될 수도 있지만 어차피 나누어떨어지지 않으므로 상관 없다)

 

여기까지는 기본적인 소인수분해 알고리즘이다.

그러나 아직 성능을 향상시킬 수 있는 여지가 남아 있다.

 

예를 들어 9999998을 소인수분해 한다고 하자.

m이 2일 때는 나누어떨어지므로 일단은 2 x 4999999로 표현할 수 있다.

그러나 4999999는 소수이므로 m이 2, 3, 4 ... 4999998일 때는 나누어떨어지지 않고 자기 자신인 4999999가 되어서야 비로소 나누어 떨어진다.

 

시간이 많이 소모되는 부분인데, 사실은 4999999까지 일일이 검사할 필요가 없다.

4999999의 제곱근 까지만 검사해도 무방하다.

 

이유는 간단하다. 약수들은 제곱근을 기준으로 대칭을 이루기 때문이다.

36을 예로 들어보자.

 

위 수열을 보면 제곱근인 6을 기준으로 약수들이 대칭을 이루고 있음을 알 수 있다. (1 x 36 = 36, 2 x 18 = 36 ...)

만약 36의 약수를 구하고자 한다면 1, 2, 3, 4, 6까지만 구해도 나머지는 대칭이므로 굳이 구할 필요가 없는 것이다.

 

소수를 판별할 때도 이를 응용하면 된다. 제곱근까지만 검사해도 그 너머의 수들은 알아서 검사가 된다.

반복문을 돌리면서 혹시나 m이 n의 제곱근보다 커진다면 n은 소수라는 뜻이므로 가차없이 반복문을 중지시켜도 된다는 뜻이다.