문제: 600851475143의 소인수 중 가장 큰 값을 구하시오.
소수를 찾는 가장 간단하고 무식한 방법은 2에서 자기자신까지 1씩 더하면서 나눠보고 확인하는 방법이다. 따라서 소인수를 찾으려면 1)나눠 떨어지는지 검사, 2) 그 수가 소수인지 검사를 하면 된다.
그래서 저 숫자의 가장 큰 소인수를 그런 무식한 방법으로 계산하려한다면…. 아마 컴퓨터가 한 동안 말이 없어질 건데, 꽤 오랜 시간동안 말이 없을 거다. 아, 물론 저 수에서 거꾸로 내려가면서 계산을 해보면 어떻겠냐고? 조금은 빠를 거 같은데 해보시라…
조금 더 계산 횟수를 단축 시키기 위해서 사용한 방법은 다음과 같다.
- A라는 수로 나눠떨어졌다면 A가 소수인지 확인해본다. 그리고 그 몫 역시 인수이다. 이걸 B라 하자.
- B가 소수인지 확인한다. 만약 A가 작은 숫자에서 출발했다면, A보다는 B가 훨씬 크겠지. 그리고 B가 소수라면 고맙겠다. 아닌 경우에는 B의 (양의) 제곱근이 자연수인지 본다. 그리고 이게 소수인지 확인해 본다 (이 걸 반복)
- 1~2의 과정은 A < B 인 경우만 검사해보면 된다. 그 이후에는 같은 결과의 반복이니까.
그리고 나온 코드. 1초가 안 걸려서 답을 구한 이유는 집에있는 아이맥에서 돌렸기 때문은 아니겠지.