Circular primes
Published on Saturday, August 6, 2011A 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;
}
}
}