Encuentra el dígito más alto que aparece en números primos en un rango

Dado un rango de L a R , la tarea es encontrar el dígito más alto que aparece en los números primos que se encuentran entre L y R (ambos inclusive). Si varios dígitos tienen la misma frecuencia más alta, imprima el mayor de ellos. Si no aparece ningún número primo entre L y R, genera -1.
Ejemplos: 
 

Input : L = 1 and R = 20.
Output : 1
Prime number between 1 and 20 are 2, 3, 5, 7, 11, 13, 17, 19.
1 occur maximum i.e 5 times among 0 to 9.

La idea es empezar de L a R, comprobar si el número es primo o no. Si es primo, incremente la frecuencia de los dígitos (usando una array) presentes en el número primo. Para comprobar si el número es primo o no podemos utilizar la Criba de Eratóstenes .
A continuación se muestra la implementación de este enfoque:
 

C++

// C++ program to find the highest occurring digit
// in prime numbers in a range L to R.
#include<bits/stdc++.h>
using namespace std;
 
// Sieve of Eratosthenes
void sieve(bool prime[], int n)
{
      prime[0] = prime[1] = true;
    for (int p = 2; p * p  <= n; p++)
    {
        if (prime[p] == false)
            for (int i = p*2; i <= n; i+=p)
                prime[i] = true;
    }
}
 
// Returns maximum occurring digits in primes
// from l to r.
int maxDigitInPrimes(int L, int R)
{
    bool prime[R+1];
    memset(prime, 0, sizeof(prime));
 
    // Finding the prime number up to R.
    sieve(prime, R);
 
    // Initialise frequency of all digit to 0.
    int freq[10] = { 0 };
    int val;
 
    // For all number between L to R, check if prime
    // or not. If prime, incrementing the frequency
    // of digits present in the prime number.
    for (int i = L; i <= R; i++)
    {
        if (!prime[i])
        {
            int p = i; // If i is prime
            while (p)
            {
                freq[p%10]++;
                p /= 10;
            }
        }
    }
 
    // Finding digit with highest frequency.
    int max = freq[0], ans = 0;
    for (int j = 1; j < 10; j++)
    {
        if (max <= freq[j])
        {
            max = freq[j];
            ans = j;
        }
    }
 
    return (max != 0)? ans: -1;
}
 
// Driven Program
int main()
{
    int L = 1, R = 20;
 
    cout << maxDigitInPrimes(L, R) << endl;
    return 0;
}

Java

// Java program to find the highest occurring digit
// in prime numbers in a range L to R.
import java.util.Arrays;
 
class GFG {
     
    // Sieve of Eratosthenes
    static void sieve(boolean prime[], int n) {
 
        for (int p = 2; p * p <= n; p++) {
            if (prime[p] == false)
                for (int i = p * 2; i <= n; i += p)
                    prime[i] = true;
        }
    }
     
    // Returns maximum occurring digits in primes
    // from l to r.
    static int maxDigitInPrimes(int L, int R) {
 
        boolean prime[] = new boolean[R + 1];
        Arrays.fill(prime, false);
     
        // Finding the prime number up to R.
        sieve(prime, R);
     
        // Initialise frequency of all digit to 0.
        int freq[] = new int[10];
        int val;
     
        // For all number between L to R, check if
        // prime or not. If prime, incrementing
        // the frequency of digits present in the
        // prime number.
        for (int i = L; i <= R; i++) {
 
            if (!prime[i]) {
                int p = i; // If i is prime
 
                while (p > 0) {
                freq[p % 10]++;
                p /= 10;
                }
            }
        }
     
        // Finding digit with highest frequency.
        int max = freq[0], ans = 0;
 
        for (int j = 1; j < 10; j++) {
            if (max <= freq[j]) {
                max = freq[j];
                ans = j;
            }
        }
     
        return (max != 0) ? ans : -1;
    }
     
    // Driver code
    public static void main(String[] args) {
        int L = 1, R = 20;
        System.out.println(maxDigitInPrimes(L, R));
    }
}
 
// This code is contributed by Anant Agarwal.

Python 3

# Python 3 program to find the highest
# occurring digit in prime numbers
# in a range L to R.
 
# Sieve of Eratosthenes
def sieve(prime, n):
    p = 2
    while p * p <= n :
        if (prime[p] == False):
            for i in range(p * 2, n, p):
                prime[i] = True
                 
        p += 1
 
# Returns maximum occurring digits
# in primes from l to r.
def maxDigitInPrimes(L, R):
 
    prime = [0] * (R + 1)
 
    # Finding the prime number up to R.
    sieve(prime, R)
 
    # Initialise frequency of all
    # digit to 0.
    freq = [0] * 10
 
    # For all number between L to R,
    # check if prime or not. If prime,
    # incrementing the frequency
    # of digits present in the prime number.
    for i in range(L, R + 1):
        if (not prime[i]):
            p = i # If i is prime
            while (p):
                freq[p % 10] += 1
                p //= 10
 
    # Finding digit with highest frequency.
    max = freq[0]
    ans = 0
    for j in range(1, 10):
        if (max <= freq[j]):
            max = freq[j]
            ans = j
    if max == 0
    return -1
    return ans
 
# Driver Code
if __name__=="__main__":
     
    L = 1
    R = 20
 
    print(maxDigitInPrimes(L, R))
 
# This code is contributed by ita_c

C#

// C# program to find the highest
// occurring digit in prime numbers
// in a range L to R.
using System;
 
class GFG {
     
    // Sieve of Eratosthenes
    static void sieve(bool []prime, int n)
    {
        for (int p = 2; p * p <= n; p++)
        {
            if (prime[p] == false)
                for (int i = p * 2; i <= n; i += p)
                    prime[i] = true;
        }
    }
     
    // Returns maximum occurring digits
    // in primes from l to r.
    static int maxDigitInPrimes(int L, int R) {
 
        bool []prime = new bool[R + 1];
        for(int i = 0; i < R+1; i++)
        prime[i] = false;
 
        // Finding the prime number up to R.
        sieve(prime, R);
     
        // Initialise frequency of all digit to 0.
        int []freq = new int[10];
     
     
        // For all number between L to R, check if
        // prime or not. If prime, incrementing
        // the frequency of digits present in the
        // prime number.
        for (int i = L; i <= R; i++) {
 
            if (!prime[i])
            {
                int p = i; // If i is prime
 
                while (p > 0) {
                freq[p % 10]++;
                p /= 10;
                }
            }
        }
     
        // Finding digit with highest frequency.
        int max = freq[0], ans = 0;
 
        for (int j = 1; j < 10; j++)
        {
            if (max <= freq[j]) {
                max = freq[j];
                ans = j;
            }
        }
        return (max != 0) ? ans : -1;
    }
     
    // Driver code
    public static void Main()
    {
        int L = 1, R = 20;
        Console.Write(maxDigitInPrimes(L, R));
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to find the highest occurring
// digit in prime numbers in a range L to R.
 
// Sieve of Eratosthenes
function sieve(&$prime, $n)
{
    for ($p = 2; $p * $p <= $n; $p++)
    {
        if ($prime[$p] == false)
            for ($i = $p * 2;
                 $i <= $n; $i += $p)
                $prime[$i] = true;
    }
}
 
// Returns maximum occurring digits
// in primes from l to r.
function maxDigitInPrimes($L, $R)
{
    $prime = array_fill(0, $R + 1, false);
 
    // Finding the prime number up to R.
    sieve($prime, $R);
 
    // Initialise frequency of all digit to 0.
    $freq = array_fill(0, 10, 0);
 
    // For all number between L to R, check
    // if prime or not. If prime, incrementing
    // the frequency of digits present in the
    // prime number.
    for ($i = $L; $i <= $R; $i++)
    {
        if (!$prime[$i])
        {
            $p = $i; // If i is prime
            while ($p)
            {
                $freq[$p % 10]++;
                $p = (int)($p / 10);
            }
        }
    }
 
    // Finding digit with highest frequency.
    $max = $freq[0];
    $ans = 0;
    for ($j = 1; $j < 10; $j++)
    {
        if ($max <= $freq[$j])
        {
            $max = $freq[$j];
            $ans = $j;
        }
    }
 
    return $ans;
}
 
// Driver Code
$L = 1;
$R = 20;
 
echo maxDigitInPrimes($L, $R);
 
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript program to find
// the highest occurring digit
// in prime numbers in a range L to R.
     
    // Sieve of Eratosthenes
    function sieve(prime,n)
    {
        for (let p = 2; p * p <= n; p++) {
            if (prime[p] == false)
                for (let i = p * 2; i <= n; i += p)
                    prime[i] = true;
        }
    }
     
     // Returns maximum occurring digits in primes
    // from l to r.
    function maxDigitInPrimes(L,R)
    {
        let prime=new Array(R+1);
        for(let i=0;i<R+1;i++)
        {
            prime[i]=false;
        }
        // Finding the prime number up to R.
        sieve(prime, R);
         
        let freq=new Array(10);
        for(let i=0;i<10;i++)
        {
            freq[i]=0;
        }
        let val;
        // For all number between L to R, check if
        // prime or not. If prime, incrementing
        // the frequency of digits present in the
        // prime number.
        for (let i = L; i <= R; i++) {
   
            if (!prime[i]) {
                let p = i; // If i is prime
   
                while (p > 0) {
                freq[p % 10]++;
                p = Math.floor(p/10);
                }
            }
        }
       
        // Finding digit with highest frequency.
        let max = freq[0], ans = 0;
   
        for (let j = 1; j < 10; j++) {
            if (max <= freq[j]) {
                max = freq[j];
                ans = j;
            }
        }
       
        return ans;
    }
     
    // Driver code
    let  L = 1, R = 20;
    document.write(maxDigitInPrimes(L, R));
     
    // This code is contributed by avanitrachhadiya2155
     
</script>

Producción: 

1

Este artículo es una contribución de >Anuj Chauhan(anuj0503) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *