035.cpp

#include <iostream>
using namespace std;

const unsigned MAX = 1000000;
class prime_table
{
        bool x[MAX];
public:
        prime_table();
        bool has(unsigned k);
        unsigned next(unsigned n);
};

prime_table::prime_table()
{
        //assume all except 0,1 are prime
        x[0]=x[1]=0;
        for (bool* p=x+2;p-x<MAX;p++)*p=1;

        for (unsigned n = 2; n < MAX;n = next(n)) {
                unsigned idx=n+n;
                while (idx < MAX) {
                        x[idx]=0;
                        idx+=n;
                }
        }
}

unsigned prime_table::next(unsigned n)
{
        if (n>=MAX)return MAX;
        bool* p = x+n;
        do {
                p++;
                if (*p)return (p-x);
        } while (p-x < MAX);
        return MAX;
}

bool prime_table::has(unsigned k)
{
        if (k>=MAX) {
                cerr << "Error: overflow";
                return 0;
        }
        return x[k];
}

unsigned pow10(unsigned p)
{
        unsigned prod=1;
        for (unsigned i=1;i<=p;i++)
                prod*=10;
        return prod;
}

unsigned num_length(unsigned x)
{
        unsigned len=0;
        for (;x>0;x/=10)
                len++;
        return len;
}

inline unsigned circulate(unsigned y,unsigned len)
{
        return y/10+(y%10)*pow10(len-1);        //shift the right-most digit to left
}

class lookup_table
{
        bool x[MAX];
public:
        lookup_table() {
                for (unsigned i=0;i<MAX;i++)
                        x[i]=0;
        }
        void mark(unsigned k) {
                x[k]=1;
        }
        unsigned count() {
                unsigned cnt=0;
                for (unsigned i=0;i<MAX;i++)
                        if (x[i])
                                cnt++;
                return cnt;
        }
        bool has(unsigned k) {
                if (k>=MAX) {
                        cerr << "Error: overflow";
                        return 0;
                }
                return x[k];
        }
};



int main()
{
        prime_table primes;
        lookup_table circular_primes;

        unsigned count=0;
        for (unsigned p=2;p<MAX;p=primes.next(p)) {
                //if p is already a circular prime, skip it
                if (circular_primes.has(p))continue;

                //check if p is circular
                unsigned len=num_length(p);
                unsigned y=p;
                bool flag=1;
                for (unsigned count=1;count<=len;count++) {
                        y = circulate(y,len);
                        if (!primes.has(y)) {
                                flag=0;
                                break;
                        }
                }
                //record all circular primes
                if (flag)
                        for (unsigned count=1;count<=len;count++) {
                                y = circulate(y,len);
                                circular_primes.mark(y);
                                //cout << y << '\t';
                        }
        }
        cout << circular_primes.count() << endl;
        return 0;
}