Contar números primos completos en un rango dado

Posted on by Rudeus Greyrat

Dados dos números enteros L y R , la tarea es contar el número de números primos completos que están presentes en el rango dado.

Se dice que un número es primo completo si el número en sí es primo y todos sus dígitos también son primos. 

Ejemplos: 

  • 53 es Full Prime porque es primo y todos sus dígitos (5 y 3) también son primos.
  • 13 no es primo completo porque tiene un dígito no primo (1 no es primo).

Ejemplos:

Entrada: L = 1, R = 100
Salida: 8
Explicaciones: 2 3 5 7 23 37 53 73 son los números primos completos entre 1 y 100. Por lo tanto, la cuenta es 8.

Entrada: L = 200, R = 300
Salida: 5
Explicación: 223 227 233 257 277 son los números primos completos entre 200 y 300. Por lo tanto, la cuenta es 5.

Enfoque: siga los pasos a continuación para resolver el problema:

  • Simplemente atraviese el rango de L a R .
  • Para cada número i en el rango, verifica si es divisible por cualquier número del rango [2, sqrt(i)] . Si se encuentra que es cierto, entonces no es un número primo. Continúe con el siguiente número.
  • De lo contrario, comprueba si todos sus dígitos son primos o no. Si se determina que es cierto, aumente la cuenta .
  • Finalmente, después de completar el recorrido del rango, imprima el valor de count .

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

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a
// number is prime or not
bool isPrime(int num)
{
    if (num <= 1)
        return false;
 
    for (int i = 2; i * i <= num; i++)
 
        // If a divisor of n exists
        if (num % i == 0)
            return false;
    return true;
}
 
// Function to check if a
// number is Full Prime or not
bool isFulPrime(int n)
{
    // If n is not a prime
    if (!isPrime(n))
        return false;
 
    // Otherwise
    else {
        while (n > 0) {
            // Extract digit
            int rem = n % 10;
            // If any digit of n
            // is non-prime
            if (!(rem == 2 || rem == 3
                  || rem == 5 || rem == 7))
                return false;
 
            n = n / 10;
        }
    }
    return true;
}
 
// Function to print count of
// Full Primes in a range [L, R]
int countFulPrime(int L, int R)
{
    // Stores count of full primes
    int cnt = 0;
 
    for (int i = L; i <= R; i++) {
 
        // Check if i is full prime
        if ((i % 2) != 0 && isFulPrime(i)) {
            cnt++;
        }
    }
    return cnt;
}
 
// Driver Code
int main()
{
    int L = 1, R = 100;
 
    // Stores count of full primes
    int ans = 0;
 
    if (L < 3)
        ans++;
    cout << ans + countFulPrime(L, R);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
 
class GFG{
  
// Function to check if a
// number is prime or not
static boolean isPrime(int num)
{
    if (num <= 1)
        return false;
  
    for(int i = 2; i * i <= num; i++)
     
        // If a divisor of n exists
        if (num % i == 0)
            return false;
             
    return true;
}
  
// Function to check if a
// number is Full Prime or not
static boolean isFulPrime(int n)
{
     
    // If n is not a prime
    if (!isPrime(n))
        return false;
  
    // Otherwise
    else
    {
        while (n > 0)
        {
             
            // Extract digit
            int rem = n % 10;
             
            // If any digit of n
            // is non-prime
            if (!(rem == 2 || rem == 3 ||
                  rem == 5 || rem == 7))
                return false;
  
            n = n / 10;
        }
    }
    return true;
}
  
// Function to print count of
// Full Primes in a range [L, R]
static int countFulPrime(int L, int R)
{
     
    // Stores count of full primes
    int cnt = 0;
  
    for(int i = L; i <= R; i++)
    {
         
        // Check if i is full prime
        if ((i % 2) != 0 && isFulPrime(i))
        {
            cnt++;
        }
    }
    return cnt;
}
  
// Driver Code
public static void main (String[] args)
{
    int L = 1, R = 100;
  
    // Stores count of full primes
    int ans = 0;
  
    if (L < 3)
        ans++;
         
    System.out.println(ans + countFulPrime(L, R));
}
}
 
// This code is contributed by sanjoy_62

Python3

# Python3 program to implement
# the above approach
 
# Function to check if a
# number is prime or not
def isPrime(num):
     
    if (num <= 1):
        return False
 
    for i in range(2, num + 1):
        if i * i > num:
            break
 
        # If a divisor of n exists
        if (num % i == 0):
            return False
             
    return True
 
# Function to check if a
# number is Full Prime or not
def isFulPrime(n):
     
    # If n is not a prime
    if (not isPrime(n)):
        return False
 
    # Otherwise
    else:
        while (n > 0):
             
            # Extract digit
            rem = n % 10
             
            # If any digit of n
            # is non-prime
            if (not (rem == 2 or rem == 3 or
                     rem == 5 or rem == 7)):
                return False
 
            n = n // 10
             
    return True
 
# Function to print count of
# Full Primes in a range [L, R]
def countFulPrime(L, R):
     
    # Stores count of full primes
    cnt = 0
 
    for i in range(L, R + 1):
         
        # Check if i is full prime
        if ((i % 2) != 0 and isFulPrime(i)):
            cnt += 1
             
    return cnt
 
# Driver Code
if __name__ == '__main__':
     
    L = 1
    R = 100
 
    # Stores count of full primes
    ans = 0
 
    if (L < 3):
        ans += 1
         
    print(ans + countFulPrime(L, R))
 
# This code is contributed by mohit kumar 29

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
  
// Function to check if a
// number is prime or not
static bool isPrime(int num)
{
    if (num <= 1)
        return false;
  
    for(int i = 2; i * i <= num; i++)
     
        // If a divisor of n exists
        if (num % i == 0)
            return false;
             
    return true;
}
  
// Function to check if a
// number is Full Prime or not
static bool isFulPrime(int n)
{
     
    // If n is not a prime
    if (!isPrime(n))
        return false;
  
    // Otherwise
    else
    {
        while (n > 0)
        {
             
            // Extract digit
            int rem = n % 10;
             
            // If any digit of n
            // is non-prime
            if (!(rem == 2 || rem == 3 ||
                  rem == 5 || rem == 7))
                return false;
  
            n = n / 10;
        }
    }
    return true;
}
  
// Function to print count of
// Full Primes in a range [L, R]
static int countFulPrime(int L, int R)
{
     
    // Stores count of full primes
    int cnt = 0;
  
    for(int i = L; i <= R; i++)
    {
         
        // Check if i is full prime
        if ((i % 2) != 0 && isFulPrime(i))
        {
            cnt++;
        }
    }
    return cnt;
}
  
// Driver Code
public static void Main (String[] args)
{
    int L = 1, R = 100;
  
    // Stores count of full primes
    int ans = 0;
  
    if (L < 3)
        ans++;
         
    Console.WriteLine(ans + countFulPrime(L, R));
}
}
 
// This code is contributed by math_lover

Javascript

<script>
 
// Javascript Program to implement
// the above approach
 
// Function to check if a
// number is prime or not
function isPrime(num)
{
    if (num <= 1)
        return false;
   
    for(let i = 2; i * i <= num; i++)
      
        // If a divisor of n exists
        if (num % i == 0)
            return false;
              
    return true;
}
   
// Function to check if a
// number is Full Prime or not
function isFulPrime(n)
{
     
    // If n is not a prime
    if (!isPrime(n))
        return false;
   
    // Otherwise
    else
    {
        while (n > 0)
        {
              
            // Extract digit
            let rem = n % 10;
              
            // If any digit of n
            // is non-prime
            if (!(rem == 2 || rem == 3 ||
                  rem == 5 || rem == 7))
                return false;
   
            n = Math.floor(n / 10);
        }
    }
    return true;
}
   
// Function to print count of
// Full Primes in a range [L, R]
function countFulPrime(L, R)
{
      
    // Stores count of full primes
    let cnt = 0;
   
    for(let i = L; i <= R; i++)
    {
          
        // Check if i is full prime
        if ((i % 2) != 0 && isFulPrime(i))
        {
            cnt++;
        }
    }
    return cnt;
}
 
// Driver code
let L = 1, R = 100;
 
// Stores count of full primes
let ans = 0;
 
if (L < 3)
    ans++;
      
document.write(ans + countFulPrime(L, R));
 
// This code is contributed by splevel62
 
</script>
Producción: 

8

 

Complejidad de Tiempo: O(N 3/2 )
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por dhanajitkapali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *