What are truncatable primes?

A prime number is a number that is only divisible by 1 and itself. Truncatable primes are built on this concept.

1 is NOT a prime number

A number is a truncatable prime if successively removing digits (until only one digit remains) forms another prime number. If these digits are removed from the left side, the number is a left-truncatable prime; if they’re removed from the right side, the number is right-truncatable.

2, 3, 5 and 7 are NOT truncatable primes.

Left-Truncatable

1 of 8

Implementation

A C++ std::vector has been used in the implementation below. It’s size can be efficiently extended compared to an array.

#include <iostream>
#include<vector>
#include<cmath>
using namespace std;
// Get digits of the integer in reverse order:
void getDigits(int n, vector<int> &digits){
  while(n != 0){
    digits.push_back(n % 10);
    n = n / 10;
  }
}
// Check if the number is prime:
bool isPrime(int n){
  if(n <= 1)
    return false;
  for(int i = 2; i <= n / 2; ++i){
    if(n % i == 0)
      return false;
  }
  return true;
}
bool isLeftTruncatable(int n, vector<int> digits){
  if(n < 10)
    return false;
    
  int total = digits.size();
  do{
    if(!isPrime(n))
      return false;
    digits.pop_back();
    --total;
    n = 0;
    for(int i = 0; i < total; ++i){
      n += pow(10, i) * digits[i];
    }
  } while(n != 0);
  return true;
}
int main() {
  vector<int> digits;
  int n = 617;
  
  // Get digits of the integer separately:
  getDigits(n, digits);
  
  if(isLeftTruncatable(n, digits))
    cout << n << " is left-truncatable";
  else
    cout << n << " is NOT left-truncatable";
  
  return 0;
}

Right-Truncatable

1 of 8

Implementation

#include <iostream>
using namespace std;
bool isPrime(int n){
  if(n <= 1)
    return false;
  for(int i = 2; i <= n / 2; ++i){
    if(n % i == 0)
      return false;
  }
  return true;
}
bool isRightTruncatable(int n){
  if(n < 10)
    return false;
  do {
    if(!isPrime(n))
      return false;
    n = n / 10;
  } while(n != 0);
  return true;
}
int main() {
  int n = 593;
  
  if(isRightTruncatable(n))
    cout << n << " is right-truncatable";
  else
    cout << n << " is NOT right-truncatable";
  return 0;
}

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved