Dados dos números M y N. La tarea es imprimir el número que tiene el número máximo de factores primos distintos de números en el rango M y N. Si existen varios números, imprimir el más pequeño.
Ejemplos:
Entrada: a=4, b=10
Salida: 6
Número de factores primos distintos de 4 es 1
Número de factores primos distintos de 5 es 1
Número de factores primos distintos de 6 es 2
Número de factores primos distintos de 7 es 1
Número de Factores primos distintos de 8 es 1
Número de factores primos distintos de 9 es 1
Número de factores primos distintos de 10 es 2Entrada: a=100, b=150
Salida: 102
El enfoque es utilizar la criba de Eratóstenes . Cree una array factorCount[] para almacenar el número de factores primos distintos de un número. Mientras marca el número como primo, incremente el conteo de factores primos en sus múltiplos. Al final, obtenga el número máximo almacenado en la array factorCount[], que será la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print the
// Number which has the maximum number
// of distinct prime factors of
// numbers in range m to n
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum number
int maximumNumberDistinctPrimeRange(int m, int n)
{
// array to store the number of distinct primes
long long factorCount[n + 1];
// true if index 'i' is a prime
bool prime[n + 1];
// initializing the number of factors to 0 and
for (int i = 0; i <= n; i++) {
factorCount[i] = 0;
prime[i] = true; // Used in Sieve
}
for (int i = 2; i <= n; i++) {
// condition works only when 'i' is prime,
// hence for factors of all prime number,
// the prime status is changed to false
if (prime[i] == true) {
// Number is prime
factorCount[i] = 1;
// number of factor of a prime number is 1
for (int j = i * 2; j <= n; j += i) {
// incrementing factorCount all
// the factors of i
factorCount[j]++;
// and changing prime status to false
prime[j] = false;
}
}
}
// Initialize the max and num
int max = factorCount[m];
int num = m;
// Gets the maximum number
for (int i = m; i <= n; i++) {
// Gets the maximum number
if (factorCount[i] > max) {
max = factorCount[i];
num = i;
}
}
return num;
}
// Driver code
int main()
{
int m = 4, n = 6;
// Calling function
cout << maximumNumberDistinctPrimeRange(m, n);
return 0;
}
Java
// Java program to print the
// Number which has the maximum
// number of distinct prime
// factors of numbers in range
// m to n
import java.io.*;
class GFG
{
// Function to return
// the maximum number
static int maximumNumberDistinctPrimeRange(int m,
int n)
{
// array to store the
// number of distinct primes
long factorCount[] = new long[n + 1];
// true if index 'i'
// is a prime
boolean prime[] = new boolean[n + 1];
// initializing the number
// of factors to 0 and
for (int i = 0; i <= n; i++)
{
factorCount[i] = 0;
prime[i] = true; // Used in Sieve
}
for (int i = 2; i <= n; i++)
{
// condition works only when
// 'i' is prime, hence for
// factors of all prime number,
// the prime status is changed to false
if (prime[i] == true)
{
// Number is prime
factorCount[i] = 1;
// number of factor of
// a prime number is 1
for (int j = i * 2; j <= n; j += i)
{
// incrementing factorCount
// all the factors of i
factorCount[j]++;
// and changing prime
// status to false
prime[j] = false;
}
}
}
// Initialize the max and num
int max = (int)factorCount[m];
int num = m;
// Gets the maximum number
for (int i = m; i <= n; i++)
{
// Gets the maximum number
if (factorCount[i] > max)
{
max = (int)factorCount[i];
num = i;
}
}
return num;
}
// Driver code
public static void main (String[] args)
{
int m = 4, n = 6;
// Calling function
System.out.println(maximumNumberDistinctPrimeRange(m, n));
}
}
// This code is contributed by anuj_67.
Python3
# Python 3 program to print the # Number which has the maximum number # of distinct prime factors of # numbers in range m to n # Function to return the maximum number def maximumNumberDistinctPrimeRange(m, n): # array to store the number # of distinct primes factorCount = [0] * (n + 1) # true if index 'i' is a prime prime = [False] * (n + 1) # initializing the number of # factors to 0 and for i in range(n + 1) : factorCount[i] = 0 prime[i] = True # Used in Sieve for i in range(2, n + 1) : # condition works only when 'i' # is prime, hence for factors of # all prime number, the prime # status is changed to false if (prime[i] == True) : # Number is prime factorCount[i] = 1 # number of factor of a # prime number is 1 for j in range(i * 2, n + 1, i) : # incrementing factorCount all # the factors of i factorCount[j] += 1 # and changing prime status # to false prime[j] = False # Initialize the max and num max = factorCount[m] num = m # Gets the maximum number for i in range(m, n + 1) : # Gets the maximum number if (factorCount[i] > max) : max = factorCount[i] num = i return num # Driver code if __name__ == "__main__": m = 4 n = 6 # Calling function print(maximumNumberDistinctPrimeRange(m, n)) # This code is contributed # by ChitraNayal
C#
// C# program to print the
// Number which has the maximum
// number of distinct prime
// factors of numbers in range
// m to n
using System;
class GFG
{
// Function to return
// the maximum number
static int maximumNumberDistinctPrimeRange(int m,
int n)
{
// array to store the
// number of distinct primes
long []factorCount = new long[n + 1];
// true if index 'i'
// is a prime
bool []prime = new bool[n + 1];
// initializing the number
// of factors to 0 and
for (int i = 0; i <= n; i++)
{
factorCount[i] = 0;
prime[i] = true; // Used in Sieve
}
for (int i = 2; i <= n; i++)
{
// condition works only x
// when 'i' is prime, hence
// for factors of all prime
// number, the prime status
// is changed to false
if (prime[i] == true)
{
// Number is prime
factorCount[i] = 1;
// number of factor of
// a prime number is 1
for (int j = i * 2;
j <= n; j += i)
{
// incrementing factorCount
// all the factors of i
factorCount[j]++;
// and changing prime
// status to false
prime[j] = false;
}
}
}
// Initialize the max and num
int max = (int)factorCount[m];
int num = m;
// Gets the maximum number
for (int i = m; i <= n; i++)
{
// Gets the maximum number
if (factorCount[i] > max)
{
max = (int)factorCount[i];
num = i;
}
}
return num;
}
// Driver code
public static void Main ()
{
int m = 4, n = 6;
// Calling function
Console.WriteLine(
maximumNumberDistinctPrimeRange(m, n));
}
}
// This code is contributed
// by anuj_67.
PHP
<?php
// PHP program to print
// the Number which has
// the maximum number of
// distinct prime factors
// of numbers in range m to n
// Function to return
// the maximum number
function maximumNumberDistinctPrimeRange($m, $n)
{
// array to store the number
// of distinct primes
$factorCount = array();
// true if index
// 'i' is a prime
$prime = array();
// initializing the number
// of factors to 0 and
for ($i = 0; $i <= $n; $i++)
{
$factorCount[$i] = 0;
$prime[$i] = true; // Used in Sieve
}
for ($i = 2; $i <= $n; $i++)
{
// condition works only
// when 'i' is prime,
// hence for factors of
// all prime number,
// the prime status is
// changed to false
if ($prime[$i] == true)
{
// Number is prime
$factorCount[$i] = 1;
// number of factor of
// a prime number is 1
for ($j = $i * 2;
$j <= $n; $j += $i)
{
// incrementing factorCount
// all the factors of i
$factorCount[$j]++;
// and changing prime
// status to false
$prime[$j] = false;
}
}
}
// Initialize the
// max and num
$max = $factorCount[$m];
$num = $m;
// Gets the maximum number
for ($i = $m; $i <= $n; $i++)
{
// Gets the maximum number
if ($factorCount[$i] > $max)
{
$max = $factorCount[$i];
$num = $i;
}
}
return $num;
}
// Driver code
$m = 4; $n = 6;
// Calling function
echo maximumNumberDistinctPrimeRange($m, $n);
// This code is contributed
// by anuj_67.
?>
Javascript
<script>
// Javascript program to print the
// Number which has the maximum number
// of distinct prime factors of
// numbers in range m to n
// Function to return the maximum number
function maximumNumberDistinctPrimeRange(m, n)
{
// Array to store the number of distinct primes
let factorCount = new Array(n + 1);
// True if index 'i' is a prime
let prime = new Array(n + 1);
// Initializing the number of factors to 0 and
for(let i = 0; i <= n; i++)
{
factorCount[i] = 0;
// Used in Sieve
prime[i] = true;
}
for(let i = 2; i <= n; i++)
{
// Condition works only when 'i' is prime,
// hence for factors of all prime number,
// the prime status is changed to false
if (prime[i] == true)
{
// Number is prime
factorCount[i] = 1;
// Number of factor of a prime number is 1
for(let j = i * 2; j <= n; j += i)
{
// Incrementing factorCount all
// the factors of i
factorCount[j]++;
// And changing prime status to false
prime[j] = false;
}
}
}
// Initialize the max and num
let max = factorCount[m];
let num = m;
// Gets the maximum number
for(let i = m; i <= n; i++)
{
// Gets the maximum number
if (factorCount[i] > max)
{
max = factorCount[i];
num = i;
}
}
return num;
}
// Driver code
let m = 4, n = 6;
// Calling function
document.write(maximumNumberDistinctPrimeRange(m, n));
// This code is contributed by souravmahato348
</script>
Producción:
6
Publicación traducida automáticamente
Artículo escrito por IshitaBhuiya1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA