Original

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

和訳

197は巡回素数と呼ばれる.
桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.

100未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である.
100万未満の巡回素数は何個か?

当てにならないソースコード(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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
using System;
using System.Collections.Generic;

namespace ProjectEuler {
    class Problem35 : Problem{
        const int max = 1000000;
        public Problem35() {
            int answer = 1;
            SortedList<long, bool> sorted = new SortedList<long, bool>();
            Primes primes = new Primes();
            primes.MakeUnder((long)Math.Sqrt(max));
            for (int i = 3; i < max; ) {
                bool isPrime = true;
                for (int j = 0; j<primes.Count;j++ ) {
                    if (i <= primes[j]) {
                        break;
                    }
                    if (i % primes[j] == 0) {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime) {
                    sorted.Add(i, true);
                }
                i += 2;
                List<int> digits = Numerics.MakeDigits(i);
                digits.Reverse();
                for (int j = 1; j<digits.Count; j++) {
                    if (digits[j] % 2 == 0) {
                        i += (int)Math.Pow(10, j);
                    }
                }
            }
            foreach(var v in sorted){
                bool circular = true;
                List<long> rotated = Rotated(v.Key);
                foreach (var r in rotated) {
                    if (!sorted.ContainsKey(r)) {
                        circular = false;
                        break;
                    }
                }
                if (circular) {
                    //Console.WriteLine(v.Key);
                    ++answer;
                }
            }
            Console.WriteLine("> " + answer);
        }

        List<long> Rotated(long n) {
            List<long> ret = new List<long>();
            List<int> digits = Numerics.MakeDigits(n);
            int tmp;
            for (int i = 1; i < digits.Count; i++) {
                tmp = digits[0];
                digits.RemoveAt(0);
                digits.Add(tmp);
                ret.Add(Numerics.FromDigits(digits));
            }
            return ret;
        }
    }
}


総当たりでも解けるので簡単といえば簡単な問題です。
でも、かなり時間がかかるはず。
偶数か5である桁が含まれている場合は除外できるので、
それだけでも十分な枝刈りになります。
数字を文字列的に扱えるスクリプト言語ならもっと簡単に解けそうです。