/* TRUNCATABLE PRIMES [CODING CHALLENGE] A prime number without zero digits is called right truncatable if all numbers obtained by successively removing the rightmost digits are prime Example: 239 is right truncatable 239 => 23 => 2 all of them primes The first few are 2, 3, 5, 7, 23, 29, 31, 37, 53, 59, 71, 73, 79, 233, 239, 293, 311, 313, 317, 373, 379, 593, 599 A prime number without zero digits is called left truncatable when removing leftmost digits the obtained numbers are all primes Example: 167 is left truncatable 167 => 67 => 7 The first few are 2, 3, 5, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 113, 137, 167, 173 Challenge: Search right and left truncatable primes between the first 5000 primes */ #include #include #include #include #include #include using namespace std; // custom power function int P(int i) { int n=10; return i ? n*P(i -1) : 1; } // check if prime no is right shortable prime. To check it successively remove rightmost digit and check if the remaining number is prime. bool isRightShortableP(set const& primes, int n) { if(n < 10) return true; n/=10; do { if(!primes.count(n)) return false; n /= 10; } while(n > 0); return true; } // check if prime no is left shortable prime. To check it successively remove leftmost digit and check if the remaining number is prime. bool isLeftShortableP(set const& primes, int n) { if (n < 10) return true; // check if prime no has 0 digit, if yes then skip it. int ncopy{n}; while(ncopy>0){ if (!(ncopy%10)) return false; ncopy /= 10; } int d = floor(log10(n))+1; int num=0; do { num = n%P(d--); if(!primes.count(num)) return false; } while(d>0); return true; } // Standard Sieve prime generator auto Gen_primes() { set primes{2}; // arbitary number, generates 5004 primes constexpr int ub = 48650; auto sieve = make_unique((ub>>3)+1); // populate sieve with 1 memset(sieve.get(), 0xFF, ((ub>>3)+1) * sizeof(char)); for(int x = 3; x <= ub; x+=2) if(sieve[x>>3] & (0x01<< (x&7))) { primes.emplace(x); // set all multiples to zero for(int j = 3*x; j<=ub; j+=x) sieve[j>>3] &= ~(0x01 <<(j&7)); } return primes; } void checkShortable() { auto primes {Gen_primes()}; cout << "Left Truncatable Primes: \n"; for (auto n : primes){ if(isLeftShortableP(primes, n)) cout << n << " "; } cout << "\n\n"; cout << "Right Truncatable Primes: \n"; for (auto n : primes){ if(isRightShortableP(primes, n)) cout << n << " "; } cout << "\n\n"; cout << "Both Sides Truncatable Primes: \n"; for (auto n : primes){ if(isRightShortableP(primes, n) && isLeftShortableP(primes, n)) cout << n << " "; } cout << "\n\n"; } int main() { // check if prime is left, right or // full shortable checkShortable(); }

[Challenge] Truncatable_primes.cpp