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