Sunday 12 April 2009

PROJECT EULER #35

Link to Project Euler problem 35

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?


using System;

namespace project_euler
{
class Program
{
static void Main()
{
//Problem 35
DateTime start = DateTime.Now;
int result = 0;
for (int i = 0; i < 1000000; i++)
if (IsCircularPrime(i))
result ++;
Console.WriteLine( result );
TimeSpan time = DateTime.Now - start;
Console.WriteLine("This took {0}", time);
Console.ReadKey();
}
//check if number is circular prime
public static bool IsCircularPrime( int number )
{
if (!IsPrime(number))
return false;
string s = number.ToString();
//if the numbers 2,4,6,8,0 or 5 are in there it can't be a circular prime.
foreach (char ch in s)
if (number != 2)
if(number!=5)
if (int.Parse(ch.ToString())%2 == 0 || ch == '5')
return false;
string[] c = CircularCombinations( s );
for( int i=0; i<c.Length; i++ )
{
int n = int.Parse( c[i] );
if (!IsPrime(n))
return false;
}
return true;
}
//Make the combinations
public static string[] CircularCombinations(string number)
{
string[] c = new string[number.Length];
c[0] = number;
for (int i = 1; i < c.Length; i++)
c[i] = number.Substring(i, c.Length - i) + number.Substring(0, i);
return c;
}
//test if prime
public static bool IsPrime(int n)
{
if (n < 2)
return false;
if (n == 2)
return true;
for (long i = 2; i <= Math.Sqrt(n); i++)
if (n%i == 0)
return false;
return true;
}
}
}

No comments: