Problem 37
using System;
using System.Collections.Generic;
using System.Linq;
class PE037 {
static List<int> MakePrimes(int n) {
var primes = new List<int>();
primes.Add(2);
var table = new bool[n+1];
for (int i = 3; i <= n; i += 2) {
if (!table[i]) {
primes.Add(i);
for (int j = i+i; j <= n; j += i)
table[j] = true;
}
}
return primes;
}
static IEnumerable<int> Shifts(int n) {
string s = n.ToString();
for (int i = 0; i < s.Length; i++) {
yield return int.Parse(s.Substring(i));
}
}
static int Calc(int n) {
int m = (int)Math.Pow(10, n);
var primes = MakePrimes(m);
var q = new Queue<int>(primes.TakeWhile(e => e < 10));
var truncatablePrimes = new List<int>();
while (q.Count > 0) {
int x = q.Dequeue();
if (x > 10 && Shifts(x).All(e => 0 <= primes.BinarySearch(e))) {
Console.WriteLine("add {0}", x);
truncatablePrimes.Add(x);
if (truncatablePrimes.Count == 11) {
return truncatablePrimes.Sum();
}
}
for (int i = 1; i < 10; i += 2) {
int t = 10*x + i;
if (0 <= primes.BinarySearch(t)) {
q.Enqueue(t);
}
}
}
return -1;
}
static void Main() {
for (int i = 1; i < 10; i++) {
Console.WriteLine("i = {0}", i);
int ret = Calc(i);
if (ret != -1) {
Console.WriteLine(ret);
break;
}
}
}
}