找出 N 以下所有可截短的素数之和

Question

给定一个整数N ，任务是找到N以下所有可截断的素数之和。可截断的质数是一个可左截断的质数(如果连续删除前导( 左 ) 数字，则所有结果数均为质数) 以及可右截断的质数(如果最后一个( 右 ) 数为依次删除，则所有生成的数字均为质数)。

例如，3797 是左截短的素数，因为 797、97 和 7 是素数。而且，3797 也是右截数素数，因为 379、37 和 3 是素数。因此 3797 是可截短的素数。

Input: N = 25
Output: 40
2, 3, 5, 7 and 23 are the only truncatable primes below 25.
2 + 3 + 5 + 7 + 23 = 40

Input: N = 40
Output: 77

方法：一种有效的方法是使用 Eratosthenes 筛子查找所有质数，对于N以下的每个数字，检查其是否为可截断质数。如果是，则将累加到运行总和中。

下面是上述方法的实现：

C++

// C++ implementation of the approach
#include 
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