The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
3797은 재미있는 속성을 가지고 있다. 자신이 소수이면서, 왼쪽에서 오른쪽으로 자릿수를 하나씩 제거할 때 각 단계에서 남는 숫자인 3797, 797, 97, 7 모두 소수이다. 비슷하게 오른쪽에서 왼쪽으로 제거하는 작업을 하면 남는 3797, 379, 37, 3도 소수이다.
왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 제거해 나갈 수 있는 11개 밖에 없는 소수의 합계를 구하시오.
주의: 2, 3, 5, 7은 절단 가능 소수(truncatable primes)로 고려하지 않는다.
--------------------------------------------------------------------------
검색해 보니 절단 가능 소수라는 말로 번역되고 있는 truncatable prime에 대한 문제이다. 소수가 여러 한계와 다양한 특성이 많아서인지 프로젝트 오일러에는 소수를 활용하는 문제가 많이 나온다.
왼쪽으로 지워나가는 것은 해당 숫자의 자릿수에 해당하는 숫자로 나눴을 때 나머지를 구하는 방법을 쓰고(3797을 1000으로 나눠 나머지인 797을 활용), 오른쪽으로 지워나가는 것은 해당 숫자를 10으로 나눠 몫을 구하는 방법을 반복해서 구했다.
그리고, 2, 3, 5, 7은 해당하지 않는다고 했으므로 11부터 시작해서 (소수가 아닌 짝수를 제외하고) 2씩 증가해가며 소수인지 확인하고, 소수인 경우에는 왼쪽, 오른쪽으로 지워나가며 소수 여부를 확인하게 구현했다. 이렇게 하면서 11개가 나오면 중단하면 된다.
2부터 시작하는 소수 리스트를 만들면서 왼쪽, 오른쪽으로 지우면서 나오는 소수를 매번 직접 판별하는 것이 아니라 소수 리스트에 있는지 확인하는 형태로 하면 속도가 조금 빨라질 수 있다.
문제를 해결하고 나서 다른 분이 해결했던 방법을 참조해 보니 속도를 더 개선할 수 있는 방법으로, 왼쪽에서 지워나갈 때 1의 자리 숫자가 소수가 아니면 결국 '절단 가능 소수'가 아닌 것으로 판별하게 되므로 이미 제거했던 짝수(0, 2, 4, 6, 8) 이외에 (1, 5, 9)가 있는 경우도 계산하지 않아도 된다. 즉, 소수 중에서 1의 자리 수가 3, 7인 경우에만 절단 가능 소수가 될 수 있으므로 이들 대상으로만 판별하면 되는 것이다.