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 notbool prime[N];// Sieve of Eratosthenes// function to find all prime numbersvoid 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 nint 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 codeint main(){ int n = 25; sieve(); cout << sumTruncatablePrimes(n); return 0;} |
Java
// Java implementation of the approachimport 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 notprime = [True for i in range(N)]# Sieve of Eratosthenes# function to find all prime numbersdef 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 ndef 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 coden = 25sieve()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 numbersfunction 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 nfunction 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 approachlet N = 1000005;// To check if a number is prime or notlet prime = new Array(N); // Sieve of Eratosthenes// function to find all prime numbersfunction 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 nfunction 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 codelet n = 25;sieve();document.write(sumTruncatablePrimes(n));// This code is contributed by unknown2108</script> |
Output:
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
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
