Project Euler Problem 35 Solution

Project Euler Problem 35 Solution

Problem Description :

     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?

Solution :

  Approach 1 :

     First I have generated all primes between 1 and 10^6 using sieve. Then using these primes I have calculated the number of circular primes bellow 1 million.

C++ implementation of the solution.

#include <cstdio>
#include <iostream>

using namespace std;

#define sz 1000001
#define mx 1001

bool p[sz];
int primeTable[78500],nPrime = 0;

void sieve(){
 int i,j;
 
 p[0] = p[1] = true;
 for( i = 4; i <= sz; i += 2 )
  p[i] = true;

 primeTable[nPrime++] = 2;

 for( i = 3; i <= mx; i += 2 ){
  if(!p[i]){
   primeTable[nPrime++] = i;
   for( j = i * i; j <= sz; j += i )
    p[j] = true;
  }
 }

 for( i = mx + 2; i <= sz; i += 2 ){
  if(!p[i]){
   primeTable[nPrime++] = i;
  }
 }
}

bool isCircularPrime(long n){
 long pow = 1,j;

 if( n < 10)
  return true;

 while( pow <= n )
  pow *= 10;
 pow /= 10;

 j = n ;
 while(1){
  j = (j%pow)*10 + j/pow;
  if(p[j])
   return false;
  if(j == n)
   break;
 }

 return true;
}


int main(){
 long i,cnt = 0;

 sieve();

 printf("Number of primes bellow 1 million is %ld\n",nPrime);

 for( i = 0; i < nPrime; i++){
  if( isCircularPrime(primeTable[i]) )
   cnt++;
 }

 printf("Number of circular primes bellow 1 million is %ld\n",cnt);


 return 0;
}

Output :

Number of primes bellow 1 million is 78498
Number of circular prime bellow 1 million is 55


Process returned 0 (0x0)   execution time : 0.025 s
Press any key to continue.