-
소인수분해(Prime Factorization)란 어떠한 수를 1보다 큰 자연수인 소인수(소수인 인수)들만의 곱으로 표현하는 것을 말한다.
-
x를 소인수분해하려면 2 ~ \sqrt x 에 해당하는 값으로 나눠주면 된다.
-
단, \sqrt x에 해당하는 값을 구하기 힘들다는 점을 유의
- 2부터 계속 올라가는 방향으로 while문을 쓴다.
- 2 ~ x-1까지 for문을 쓴다.
-
이때 if문을 넣어서 x를 2 \sim \sqrt x 중 아무 수로 나눴을 때
나머지가 0인지를 확인해 주면 더 속도가 빨라진다.