Contar números primos en el rango [L, R] cuya suma de un solo dígito también es primo

Dados dos enteros L y R . La tarea es contar los números primos en el rango [L, R] , cuya suma única también es un número primo. 
Una sola suma se obtiene sumando los dígitos de un número hasta que quede un solo dígito.

Ejemplos

Entrada: L = 5, R = 20 
Salida: 3
Explicación: Los números primos en el rango L = 5 a R = 20 son {5, 7, 11, 13, 17, 19}
Su «suma única» de dígitos es {5 , 7, 2, 4, 8, 1}.  
Solo {5, 7, 2} son primos. Por lo tanto la respuesta es 3.

Entrada: L = 1, R = 10  
Salida: 4
Explicación: Los números primos en el rango L = 1 a R = 10 son {2, 3, 5, 7}.  
Su «suma única» de dígitos es {2, 3, 5, 7}.  
Como todos los números son primos, la respuesta es 4.

Enfoque:   el enfoque ingenuo es iterar para cada número en el rango [L, R] y verificar si el número es primo o no. Si el número es primo, encuentre la suma única de sus dígitos y verifique nuevamente si la suma única es prima o no. Si la suma única es prima, incremente el contador e imprima el elemento actual en el rango [L, R] .

A continuación se muestra la implementación del enfoque anterior.

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether number
// is prime or not
bool isPrime(int n)
{
    // Corner case
    if (n <= 1)
        return false;
 
    // Check from 2 to square root of n
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return false;
 
    return true;
}
 
// Function to find single digit sum
int SingleDigitSum(int& n)
{
    if (n <= 9)
        return n;
    return (n % 9 == 0) ? 9 : n % 9;
}
 
// Function to find single digit primes
int countSingleDigitPrimes(int l, int r)
{
    int count = 0, i;
 
    for (i = l; i <= r; i++) {
        if (isPrime(i)
            && isPrime(SingleDigitSum(i))) {
            count++;
        }
    }
    return count;
}
 
// Driver Code
int main()
{
    // Input range
    int L = 1, R = 10;
 
    // Function Call
    cout << countSingleDigitPrimes(L, R);
 
    return 0;
}

// Java program to implement
// the above approach
class GFG
{
 
  // Function to check whether number
  // is prime or not
  static boolean isPrime(int n)
  {
 
    // Corner case
    if (n <= 1)
      return false;
 
    // Check from 2 to square root of n
    for (int i = 2; i <= Math.sqrt(n); i++)
      if (n % i == 0)
        return false;
 
    return true;
  }
 
  // Function to find single digit sum
  static int SingleDigitSum(int n)
  {
    if (n <= 9)
      return n;
    return (n % 9 == 0) ? 9 : n % 9;
  }
 
  // Function to find single digit primes
  static int countSingleDigitPrimes(int l, int r)
  {
    int count = 0, i;
 
    for (i = l; i <= r; i++) {
      if (isPrime(i)
          && isPrime(SingleDigitSum(i))) {
        count++;
      }
    }
    return count;
  }
 
  // Driver Code
  public static void main(String args[])
  {
 
    // Input range
    int L = 1, R = 10;
 
    // Function Call
    System.out.println(countSingleDigitPrimes(L, R));
 
  }
}
 
// This code is contributed by gfgking

# Python program for above approach
import math
 
# Function to check whether number
# is prime or not
def isPrime(n):
   
    # Corner case
    if n <= 1:
        return False
 
    # Check from 2 to square root of n
    for i in range(2, math.floor(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
 
    return True
 
# Function to find single digit sum
def SingleDigitSum(n):
    if n <= 9:
        return n
    return 9 if (n % 9 == 0) else n % 9
 
# Function to find single digit primes
def countSingleDigitPrimes(l, r):
    count = 0
    i = None
 
    for i in range(l, r + 1):
        if isPrime(i) and isPrime(SingleDigitSum(i)):
            count += 1
    return count
 
# Driver Code
 
# Input range
L = 1
R = 10
 
# Function Call
print(countSingleDigitPrimes(L, R))
 
# This code is contributed by gfgking

// C# program to implement
// the above approach
using System;
class GFG
{
 
  // Function to check whether number
  // is prime or not
  static bool isPrime(int n)
  {
 
    // Corner case
    if (n <= 1)
      return false;
 
    // Check from 2 to square root of n
    for (int i = 2; i <= Math.Sqrt(n); i++)
      if (n % i == 0)
        return false;
 
    return true;
  }
 
  // Function to find single digit sum
  static int SingleDigitSum(int n)
  {
    if (n <= 9)
      return n;
    return (n % 9 == 0) ? 9 : n % 9;
  }
 
  // Function to find single digit primes
  static int countSingleDigitPrimes(int l, int r)
  {
    int count = 0, i;
 
    for (i = l; i <= r; i++) {
      if (isPrime(i)
          && isPrime(SingleDigitSum(i))) {
        count++;
      }
    }
    return count;
  }
 
  // Driver Code
  public static void Main()
  {
 
    // Input range
    int L = 1, R = 10;
 
    // Function Call
    Console.Write(countSingleDigitPrimes(L, R));
 
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript program for above approach
 
    // Function to check whether number
    // is prime or not
    const isPrime = (n) => {
        // Corner case
        if (n <= 1)
            return false;
 
        // Check from 2 to square root of n
        for (let i = 2; i <= Math.sqrt(n); i++)
            if (n % i == 0)
                return false;
 
        return true;
    }
 
    // Function to find single digit sum
    const SingleDigitSum = (n) => {
        if (n <= 9)
            return n;
        return (n % 9 == 0) ? 9 : n % 9;
    }
 
    // Function to find single digit primes
    const countSingleDigitPrimes = (l, r) => {
        let count = 0, i;
 
        for (i = l; i <= r; i++) {
            if (isPrime(i)
                && isPrime(SingleDigitSum(i))) {
                count++;
            }
        }
        return count;
    }
 
    // Driver Code
 
    // Input range
    let L = 1, R = 10;
 
    // Function Call
    document.write(countSingleDigitPrimes(L, R));
 
// This code is contributed by rakeshsahni
 
</script>

4

 
Complejidad de tiempo: O((R – L)*N^(1/2)) donde N es el número primo en el rango [L, R]. 
Espacio Auxiliar: O(1)