037.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);
        unsigned count();
        void filter1();
        void filter2();
};

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)
{
        return x[k];
}

unsigned prime_table::count()
{
        unsigned cnt=0;
        for (unsigned i=2;i<MAX;i=next(i))
                cnt++;
        return cnt;
}
void prime_table::filter1()
{
        for (unsigned i=next(9);i<MAX;i=next(i))
                for (unsigned j=i/10;j>0;j/=10)
                        if (!has(j)) {
                                x[i]=0;
                                break;
                        }
}

unsigned order_of_magnitude(unsigned k)
{
        unsigned M;
        for (M=1;M<=k;M*=10);
        return M/10;
}
void prime_table::filter2()
{
        for (unsigned i=next(9);i<MAX;i=next(i)) {
                
                unsigned M = order_of_magnitude(i);
                for (unsigned j=i%M;j>0;M/=10,j%=M)
                        if (!has(j)) {
                                x[i]=0;
                                break;
                        }

        }
}

int main()
{
        prime_table primes_right;
        prime_table primes_left;
        
        primes_right.filter1();
        primes_left.filter2();
        
        //set intersection
        unsigned sum=0;
        for(unsigned i=primes_right.next(10);i<MAX;i=primes_right.next(i))
                if(primes_left.has(i))
                        sum+=i;
        
        cout << sum << endl;
        return 0;
}