[C/C++] Project Euler #35 - Circular Primes

Project Euler’s Problem #35 deals with “circular primes.”  A circular prime is defined as a prime number such that every rotation of its digits is also a prime.  For example, consider 197: if you rotate its digits, you get 197, 971, and 719—all of which are prime. Therefore, 197 is a circular prime. The question asks how many such circular primes exist below 1,000,000. For reference, there are 13 circular primes below 100.  Hence, the task is to find out how many circular primes there are below 1,000,000.

 

A prime like 197 remains a prime even when its digits are rotated one by one.  That is, 197 itself is a prime, and 971 and 719 are also primes.

 

The problem essentially boils down to finding all these primes.  In the end, you generate all primes up to the limit and then check each one to see whether it remains prime upon all rotations. Perhaps that’s why the difficulty is listed as 5%.

 

The implementation is quite simple.  You generate every prime up to the limit, then check each prime to determine if it is “circular.”

 

You can just code it directly, but in my case, I used a flag-like approach instead of storing prime values in an array.  The number 2 is an exception, since it’s the only even prime. Handling it separately is fine. Also, every digit except for 2 must be odd, right? If an even digit (other than 2) appears, there’s no way that rotating it will result in a prime every time.

 

circular primes

Here is the source code I wrote.  Please treat it as a reference only.

//------------------------------------------------
//    Project Euler #35 - Circular Primes
//        - by Aubrey Choi
//        - created at 2015-02-26
//------------------------------------------------
#include <stdio.h>

unsigned char primes[1000000/2];

int main()
{
    int ans = 1;
    int n = 1000000;
    for( int i = 3 ; i < n ; i+=2 )
    {
        if( primes[i/2] ) continue;
        for( int j = i+i+i ; j < n ; j += i+i ) primes[j/2] = 1;
    }
    int digit = 1, k = 0;
    for( int i = 3 ; i < n ; i+=2 )
    {
        if( primes[i/2] ) continue;
        if( i > digit*10 ) { digit *= 10; k++; }
        bool flag = true;
        for( int j = 0, s = i ; j < k ; j++ )
        {
            int last = s%10;
            s /= 10;
            s += digit*last;
            if( s%2 == 0 || primes[s/2] ) { flag = false; break; }
        }
        if( flag ) ans++;
    }
    printf("Ans = %d\n", ans);
}