A125001

gistfile1.txt

class PrimeSieve
{
public:
   PrimeSieve( int64_t n )
   {
      m.resize( n, true );
      m[0] = m[1] = false;
      for ( int64_t i = 2; i * i < n; i++ ) if ( isPrime( i ) )
         for ( int64_t j = i*2; j < n; j += i )
            m[j] = false;
   }
   bool isPrime( int i ) const { return m[i]; }

public:
   std::vector<bool> m;
};

void main()
{   
   vector<int64_t> powersOfTen = { 1 };
   while ( powersOfTen.size() < 15 )
      powersOfTen.push_back( powersOfTen.back() * 10 );

   int NUM_DIGITS = 7; // maximum number of digits in solution

   int64_t N = powersOfTen[NUM_DIGITS+1];
   PrimeSieve sieve( N );

   vector<bool> overEncumbered( powersOfTen[NUM_DIGITS], true );

   for ( int64_t prime = 11; prime < N; prime++ ) if ( sieve.isPrime( prime ) )
   {
      int digitsInPrime = (int) ceil( log10( prime ) );
      for ( int digitIndex = 0; digitIndex < digitsInPrime; digitIndex++ )
      {
         int p_withDigitIndexRemoved = prime / powersOfTen[digitIndex+1] * powersOfTen[digitIndex] + prime % powersOfTen[digitIndex];
         if ( p_withDigitIndexRemoved*10 < powersOfTen[digitsInPrime-1] )
            continue; // e.g. deleting '5' from '500369293' should not sieve out 369293
         overEncumbered[p_withDigitIndexRemoved] = false;
      }
   }

   for ( int64_t i = 1; i < (int64_t) overEncumbered.size(); i++ ) if ( sieve.isPrime( i ) )
      if ( overEncumbered[i] )
         cout << i << endl;
}