백준 16563 - 어려운 소인수분해

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

16563번: 어려운 소인수분해

소수 찾기나 소인수분해는 이중 반복문을 사용해 어렵지 않게 구현할 수 있다. 문제는 시간초과를 피하는 것이다. 자연수의 최댓값이 500만이라고 소수를 500만까지 찾아야할까?

 

자연수 N은 sqrt(N) 이하의 소수들만으로도 소인수분해를 할 수 있다.

 

간단한 증명

1) 자연수 N이 어떤 수 k의 제곱이라고 하자. k가 소수든 합성수든, N은 일단 2개의 sqrt(N)으로 분해된다.

 

2) 자연수 N이 제곱수는 아니지만 소수 a와 b (a < b, a > 1, b < N)의 곱으로 이루어진 합성수라고 하자. 만약 a > sqrt(N)이라면 a * b > N이므로 a < sqrt(N)이다. 따라서 sqrt(N)보다 작은 a로 N을 분해할 수 있다.

 

3) N이 소수일 경우, 1), 2)를 통해 sqrt(N) 이하의 소수들로 나눠지지 않으면 N이 소수임을 확인할 수 있다.

따라서 sqrt(N)까지의 소수만 미리 계산해놓고 이를 바탕으로 입력받은 자연수들을 하나씩 소인수분해하면 된다.

 

자연수를 sqrt(N) 이하의 소수에 대하여 나눠질 때까지 계속 나누고 이를 출력한다. 그리고 계속 나눈 후 1이 아닌 다른 값이 남았을 경우, 이를 출력해야 한다. 다음과 같은 값을 생각해보자. sqrt(N) = 100, ki = 97*101 = 9797

 

9797은 100보다 작은 소수 X 100보다 큰 소수 꼴이기 때문에 100 이하의 소수로 아무리 나눠도 101은 소인수분해되지 않는다. 따라서 반복문이 끝난 후 1이 아닌 다른 값이 남았을 경우 이 수 역시 소수이므로 함께 출력하면 된다.