Related Tags

numbers
c++
implementation

# 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;
}

RELATED TAGS

numbers
c++
implementation