Given an integer N, the task is to find the sum of all Truncatable primes below N. Truncatable prime is a number which is left-truncatable prime (if the leading (“left”) digit is successively removed, then all resulting numbers are prime) as well as right-truncatable prime (if the last (“right”) digit is successively removed, then all the resulting numbers are prime).
For example, 3797 is left-truncatable prime because 797, 97 and 7 are primes. And, 3797 is also right-truncatable prime as 379, 37, and 3 are primes. Hence 3797 is a truncatable prime.
Examples:
Input: N = 25
Output: 40
2, 3, 5, 7 and 23 are the only truncatable primes below 25.
2 + 3 + 5 + 7 + 23 = 40Input: N = 40
Output: 77
Approach: An efficient approach is to find all the prime numbers using Sieve of Eratosthenes and for every number below N check whether it is Truncatable prime or not. If yes then add is to the running sum.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define N 1000005 // To check if a number is prime or not bool prime[N]; // Sieve of Eratosthenes // function to find all prime numbers void sieve() { memset (prime, true , sizeof prime); prime[1] = false ; prime[0] = false ; for ( int i = 2; i < N; i++) if (prime[i]) for ( int j = i * 2; j < N; j += i) prime[j] = false ; } // Function to return the sum of // all truncatable primes below n int sumTruncatablePrimes( int n) { // To store the required sum int sum = 0; // Check every number below n for ( int i = 2; i < n; i++) { int num = i; bool flag = true ; // Check from right to left while (num) { // If number is not prime at any stage if (!prime[num]) { flag = false ; break ; } num /= 10; } num = i; int power = 10; // Check from left to right while (num / power) { // If number is not prime at any stage if (!prime[num % power]) { flag = false ; break ; } power *= 10; } // If flag is still true if (flag) sum += i; } // Return the required sum return sum; } // Driver code int main() { int n = 25; sieve(); cout << sumTruncatablePrimes(n); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { static final int N = 1000005 ; // To check if a number is prime or not static boolean prime[] = new boolean [N]; // Sieve of Eratosthenes // function to find all prime numbers static void sieve() { Arrays.fill(prime, true ); prime[ 1 ] = false ; prime[ 0 ] = false ; for ( int i = 2 ; i < N; i++) { if (prime[i]) { for ( int j = i * 2 ; j < N; j += i) { prime[j] = false ; } } } } // Function to return the sum of // all truncatable primes below n static int sumTruncatablePrimes( int n) { // To store the required sum int sum = 0 ; // Check every number below n for ( int i = 2 ; i < n; i++) { int num = i; boolean flag = true ; // Check from right to left while (num > 0 ) { // If number is not prime at any stage if (!prime[num]) { flag = false ; break ; } num /= 10 ; } num = i; int power = 10 ; // Check from left to right while (num / power > 0 ) { // If number is not prime at any stage if (!prime[num % power]) { flag = false ; break ; } power *= 10 ; } // If flag is still true if (flag) { sum += i; } } // Return the required sum return sum; } // Driver code public static void main(String[] args) { int n = 25 ; sieve(); System.out.println(sumTruncatablePrimes(n)); } } // This code contributed by Rajput-Ji |
Python3
# Python3 implementation of the # above approach N = 1000005 # To check if a number is prime or not prime = [ True for i in range (N)] # Sieve of Eratosthenes # function to find all prime numbers def sieve(): prime[ 1 ] = False prime[ 0 ] = False for i in range ( 2 , N): if (prime[i] = = True ): for j in range (i * 2 , N, i): prime[j] = False # Function to return the sum of # all truncatable primes below n def sumTruncatablePrimes(n): # To store the required sum sum = 0 # Check every number below n for i in range ( 2 , n): num = i flag = True # Check from right to left while (num): # If number is not prime at any stage if (prime[num] = = False ): flag = False break num / / = 10 num = i power = 10 # Check from left to right while (num / / power): # If number is not prime at any stage if (prime[num % power] = = False ): flag = False break power * = 10 # If flag is still true if (flag = = True ): sum + = i # Return the required sum return sum # Driver code n = 25 sieve() print (sumTruncatablePrimes(n)) # This code is contributed by mohit kumar |
C#
// C# implementation of the above approach. using System; using System.Collections.Generic; class GFG { static int N = 1000005; // To check if a number is prime or not static Boolean []prime = new Boolean[N]; // Sieve of Eratosthenes // function to find all prime numbers static void sieve() { Array.Fill(prime, true ); prime[1] = false ; prime[0] = false ; for ( int i = 2; i < N; i++) { if (prime[i]) { for ( int j = i * 2; j < N; j += i) { prime[j] = false ; } } } } // Function to return the sum of // all truncatable primes below n static int sumTruncatablePrimes( int n) { // To store the required sum int sum = 0; // Check every number below n for ( int i = 2; i < n; i++) { int num = i; Boolean flag = true ; // Check from right to left while (num > 0) { // If number is not prime at any stage if (!prime[num]) { flag = false ; break ; } num /= 10; } num = i; int power = 10; // Check from left to right while (num / power > 0) { // If number is not prime at any stage if (!prime[num % power]) { flag = false ; break ; } power *= 10; } // If flag is still true if (flag) { sum += i; } } // Return the required sum return sum; } // Driver code public static void Main(String []args) { int n = 25; sieve(); Console.WriteLine(sumTruncatablePrimes(n)); } } // This code has been contributed by Arnab Kundu |
PHP
<?php // PHP implementation of the approach $N = 10005; // To check if a number is prime or not $prime = array_fill (0, $N , true); // Sieve of Eratosthenes // function to find all prime numbers function sieve() { global $prime , $N ; $prime [1] = false; $prime [0] = false; for ( $i = 2; $i < $N ; $i ++) if ( $prime [ $i ]) for ( $j = $i * 2; $j < $N ; $j += $i ) $prime [ $j ] = false; } // Function to return the sum of // all truncatable primes below n function sumTruncatablePrimes( $n ) { global $prime , $N ; // To store the required sum $sum = 0; // Check every number below n for ( $i = 2; $i < $n ; $i ++) { $num = $i ; $flag = true; // Check from right to left while ( $num ) { // If number is not prime at any stage if (! $prime [ $num ]) { $flag = false; break ; } $num = (int)( $num / 10); } $num = $i ; $power = 10; // Check from left to right while ((int)( $num / $power )) { // If number is not prime at any stage if (! $prime [ $num % $power ]) { $flag = false; break ; } $power *= 10; } // If flag is still true if ( $flag ) $sum += $i ; } // Return the required sum return $sum ; } // Driver code $n = 25; sieve(); echo sumTruncatablePrimes( $n ); // This code is contributed by mits ?> |
Javascript
<script> // Javascript implementation of the approach let N = 1000005; // To check if a number is prime or not let prime = new Array(N); // Sieve of Eratosthenes // function to find all prime numbers function sieve() { for (let i = 0; i < prime.length; i++) { prime[i] = true ; } prime[1] = false ; prime[0] = false ; for (let i = 2; i < N; i++) { if (prime[i]) { for (let j = i * 2; j < N; j += i) { prime[j] = false ; } } } } // Function to return the sum of // all truncatable primes below n function sumTruncatablePrimes(n) { // To store the required sum let sum = 0; // Check every number below n for (let i = 2; i < n; i++) { let num = i; let flag = true ; // Check from right to left while (num > 0) { // If number is not prime at any stage if (!prime[num]) { flag = false ; break ; } num = Math.floor(num / 10); } num = i; let power = 10; // Check from left to right while (num / power > 0) { // If number is not prime at any stage if (!prime[num % power]) { flag = false ; break ; } power *= 10; } // If flag is still true if (flag) { sum += i; } } // Return the required sum return sum; } // Driver code let n = 25; sieve(); document.write(sumTruncatablePrimes(n)); // This code is contributed by unknown2108 </script> |
40
Time Complexity: O(n*log(log(n))), time used for running sieve function
Auxiliary Space: O(N), extra space of size n used to create an array prime
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!