Project Euler 35

Problem 35

• 1000000 までの素数を求める(エラトステネスのふるいで素数を求める)
• 求めたそれぞれの素数に対して、各桁の数値を回転させた数を作成し、素数かどうか調べる

using System;
using System.Collections.Generic;
using System.Linq;

class PE035 {
    static HashSet<int> Sieve(int n) {
        var xs = new bool[n+1]; // 全ては合成数ではないとする

        for (int i = 3; i <= n; i++) {
            if (!xs[i]) { // 
                for (int j = i*2; j <= n; j += i) {
                    xs[j] = true; // 合成数である
                }
            }
        }

        var primeSet = new HashSet<int>();
        primeSet.Add(2);
        for (int i = 3; i <= n; i += 2) {
            if (!xs[i]) primeSet.Add(i);
        }
        return primeSet;
    }

    static List<int> Rotations(int n) {
        var digits = n.ToString().Select(e => e - '0').ToArray();
        var xs = new List<int>();
        for (int i = 0; i < digits.Length; i++) {
            int x = 0;
            int p = i;
            for (int j = 0; j < digits.Length; j++) {
                x = 10*x + digits[p];
                if (++p == digits.Length) p = 0;
            }
            xs.Add(x);
        }
        return xs;
    }

    static void Main() {
        const int N = 1000000;
        var primes = Sieve(N);

        var circularPrimeSet = new HashSet<int>();
        foreach (int prime in primes) {
            if (circularPrimeSet.Contains(prime)) continue;

            var xs = Rotations(prime);
            bool isCircularPrime = true;
            foreach (int x in xs) {
                if (!primes.Contains(x)) {
                    isCircularPrime = false;
                    break;
                }
            }

            if (isCircularPrime) {
                foreach (int x in xs)
                    circularPrimeSet.Add(x);
            }
        }

        Console.WriteLine(circularPrimeSet.Count);
    }
}

プログラムを書き終わってから、Project Euler 35（1） - 桃の天然水 を見ました。

• 任意の桁の数値が偶数ならば、回転素数にはならないので、探索する必要はありませんでした(気づきませんでした)。
• 197, 971, 719 で重複して回転素数を探索しないように、見つかった回転素数は、HashSet<int> に格納するようにして、チェックの重複を避けるようにしました。