Project Euler Problem 35

Problem 35

17 January 2003

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?

Answer: 55

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.IO;

namespace Euler {
    class Program {
        /// <summary>
        /// Returns primes under limit using sieve.
        /// </summary>
        /// <param name="limit">An integer to limit.</param>
        /// <returns>Primes under limit.</returns>
        static HashSet<int> primesUnder(int limit) {
            var p = new bool[limit];
            if (limit >= 3) p[2] = true;
            for (int i = 3; i < limit; i+=2) p[i] = true;            
            for (int i = 3; i * i < limit; i+=2) {
                if (!p[i]) continue;
                for (int j = i + i; j < limit; j += i)
                    p[j] = false;
            }
            var r = new HashSet<int>();            
            for (int i = 2; i < limit; i++)
                if (p[i]) r.Add(i);
            return r;
        }

        static string rotateLeft(string value) {
            if (value.Length <= 1) return value;
            return value.Substring(1) + value[0];
        }

        static void Main(string[] args) {
            int count = 0;
            var primes = primesUnder(1000000);                        
            foreach (var x in primes) {                
                string strX = x.ToString();
                for (int i = 1; i <= strX.Length - 1; i++) {
                    strX = rotateLeft(strX);                    
                    if (!primes.Contains(Convert.ToInt32(strX))) goto Next;
                }
                count++;
            Next: ;
            }
            Console.WriteLine(count);
        }
    }
}