# Circular primes

Published on 2011-08-06A circular prime, according to Project Euler, is a prime whose cyclical permutations are themselves prime:

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.

The object of Problem 35 is to find how many there are under a million. As far as I could tell, there's no way to find out if a number is a circular prime other than testing all of its cyclical permutations, so I used a sieve of Eratosthenes to construct a list of all primes below one million and checked each rotation of each prime by converting it to a string and shuffling the characters.

My big programming challenge in this one was writing a faster sieve. The LINQ-powered one-liner I had been using (`for (int i = 0; i < eratosthenes.Count(); i++){ eratosthenes.RemoveAll(x => (x != eratosthenes[i]) && (x % eratosthenes[i] == 0)); }`

) choked when I asked it to find all primes up to a million, as it required performing a modulo check on all remaining members of a list of potential primes. I replaced the list with an `bool`

array in which prime indexes would hold the value of `true`

. I found multiples of known primes using addition rather than modulo checks, which sped things up considerably.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Problem035 { class Program { static void Main(string[] args) { int ceiling = 1000000; List<int> primesUnderCeiling = sieveOfEratosthenes(ceiling); int circularPrimeCount = 0; foreach (int n in primesUnderCeiling) if (isCircularPrime(n, primesUnderCeiling)) circularPrimeCount++; Console.WriteLine(circularPrimeCount); } private static bool isCircularPrime(int n, List<int> primes) { string prime = n.ToString(); string nextPrime = ""; bool circularPrime = true; for (int i = 0; i < prime.Length; i++) { for (int j = 0; j < prime.Length; j++) { if (j == prime.Length - 1) nextPrime += prime[0]; else nextPrime += prime[j + 1]; } if (!primes.Contains(Int32.Parse(nextPrime))) { circularPrime = false; break; } prime = nextPrime; nextPrime = ""; } return circularPrime; } private static List<int> sieveOfEratosthenes(int ceil) { bool[] eratosthenes = new bool[ceil]; eratosthenes[2] = true; for (int i = 3; i < eratosthenes.Length; i += 2) eratosthenes[i] = true; for (int i = 0; i < eratosthenes.Length; i++) { if (eratosthenes[i]) { int notPrime = i * 2; while (notPrime < eratosthenes.Length) { eratosthenes[notPrime] = false; notPrime += i; } } } List<int> primes = new List<int>(); for (int i = 2; i < eratosthenes.Length; i++) if (eratosthenes[i]) primes.Add(i); return primes; } } }