가장 큰 소인수를 구하라.
이번 문제 역시 6008억 정도로 숫자가 작으므로 특별한 방법을 필요로 하지 않는다.
기본적인 방법을 두가지 생각해보면
- 방법 1 : 숫자의 제곱근에서 시작해 소수의 목록을 얻은 뒤 가장 큰 소수부터 나누어 떨어지는지 살펴본다.
- 방법 2 : 2부터 시작해 소수로 더 이상 나누어 떨어지지 않을 때까지 나누고 몫이 1이 되면 그 소수의 값을 반환한다.
만약 64비트 정수를 지원하지 않는 플랫폼이라면 직접 만들어 주고 쓸 연산자로 오버로드 하겠지만 .. 있는데 굳이 사서 고생할 필요는 없겠다.
방법 1의 경우 2~숫자의 제곱근까지 체를 쓰든 뭘 하든 소수 목록을 얻는다. 방법 2에서 2 이후의 숫자가 소수인지 확인하는 것은 하지 않아도 되지만 본능적으로 소수인지 확인하고 싶어지는 것은 어쩔 수 없다. 둘다 소수 목록으로 해결한다고 해도, 운에 의한 1보다는 2에 눈이 간다. 하지만 특정 소인수를 많이 포함하는 경우에는 나눗셈 연산을 여러번 하게되니 어차피 도찐 개찐. 숫자가 매우 커서 사용자 정의형을 사용하는 경우라면 클래식 자료형 이하로 숫자가 줄어드는 편이 오버헤드 줄이기에 좋을테니 또 모르겠다.