169와 961은 모두 소수의 제곱이다. 169를 반대로 하면 961이 된다.
다음 조건을 만족하면 reversible prime square(가역 소수 제곱)이라 부른다:
- 회문(palindrome)이 아니며,
- 소수의 제곱이며,
- 반대로 한 것도 소수의 제곱이다.
169와 961은 회문이 아니며, 소수의 제곱을 반대로 한 것이다.
처음 50개 reversible prime square의 합계를 구하시오.
--------------------------------------------------------------------------
프로그램은 어렵지 않게 구성 가능한데, reversible prime square를 만족하는 숫자를 50개 찾는 것이 쉽지 않았다.
50개가 나올때까지 매번 소수를 추가로 만드는 경우 시간이 많이 소요될 것으로 보여서, 일정한 갯수의 소수와 소수의 제곱수 리스트를 먼저 만들어 놓고, 회문이 아니고, 순서를 반대로 한 것도 소수의 제곱수 리스트에 있는 것들을 따로 모으도록 구현했다.
100자리 중 2개, 1000자리 중 2개 등 생각보다 위 조건을 만족하는 숫자가 많이 나오지 않아서, 처음 소수를 만드는 갯수를 계속 키워가며 구해야 했다. 천만의 제곱까지 구해도 50개가 되지 않는다.
문제에서 요구한 조건을 만족하는 reversible prime square가 모두 홀수 자릿수의 숫자인 것은 의아했다. 확실한 이유가 생각되면 짝수 자릿수의 prime square는 검증과정을 생략하도록 해서 성능을 높을 수도 있을 것 같은데, 짝수 자릿수의 숫자가 없는 이유가 명확하게 떠오르지는 않아서 일단 모든 숫자를 대상으로 검증하게 했다.
일단 답은 구했지만 시간이 많이 걸렸다. 검색 끝에 찾은 몇가지 추가 조건은, △끝자리에 올 수 있는 수가 홀수이며 이 중 5의 배수인 5 제외, 1, 3, 7, 9의 제곱수는 1, 9이므로, 첫자리와 끝자리는 1, 9만 올 수 있으며, △첫자리에 1,9만 올 수 있으므로 제곱근은 1,3이 되고 이 경우 3자리 제곱은 5자리, 4자리 제곱은 7자리와 같이 홀수 자릿수로만 나오게 된다. 앞에서 얘기한 홀수 자릿수로만 reversible prime square가 나오는 이유를 알게 되었다.
그리고, 처음에는 소수의 제곱수 목록을 구해서(조건2) 그것을 대상으로 회문과 반대수를 구했는데(조건1,3), 제곱수를 구할 때 추가로 발견한 2가지 조건과 회문까지 판별해서 목록을 만들고(조건1,2), 반대수가 제곱수인 소수이면 정답 목록에 추가하는 방식으로 바꿔서 검증대상을 줄여봤다.
추가로 발견한 2가지 조건으로 검증대상이 500만개 이상에서 40만개 이하로 줄어 실행시간도 많이 개선되었지만, 검증대상 거의 마지막에 가서야 50개를 찾을 수 있어 실행시간은 여전히 필요했다.