Original

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を切り詰め可能な素数とは考えない.

当てにならないソースコード(C#)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using System;

namespace ProjectEuler {
    class Problem37 : Problem{
        int[] digits = {1, 3, 5, 7, 9};
        Primes primes = new Primes();

        public Problem37(){
            //primes.MakeUnder(1000000);
            long answer = 0, cnt = 0;
            for (int i = 4;cnt<11;i++ ) {
                if (IsTrimmablePrime(primes[i])) {
                    Console.WriteLine("found " + primes[i]);
                    answer += primes[i];
                    ++cnt;
                }
            }
            Console.WriteLine("> " + answer);
        }

        bool IsTrimmablePrime(long prime) {
            long p = prime;
           
            long last = p % 10;
            if (last != 3 && last != 7) {
                return false;
            }
            while ((p /= 10) > 0) {
                if (!primes.IsPrime(p)) {
                    return false;
                }
            }
            for (long i=10;p<prime;i*=10) {
                p = prime % i;
                if (!primes.IsPrime(p)) {
                    return false;
                }
            }
            return true;
        }
    }
}