Dado un número N, encuentre el número máximo de factores primos únicos que cualquier número puede tener en el rango [1, N].
Ejemplos:
Input : N = 500 Output : 4 The maximum number of prime factors for any number in [1, 500] is 4. A number in range that has 4 prime factors is 210 (2 x 3 x 5 x 7) Input : N = 3 Output : 1 Input : N = 5000 Output : 5
Método 1 (fuerza bruta):
para cada número entero de 1 a N, encuentre el número de factores primos de cada número entero y encuentre el número máximo de factores primos únicos.
Método 2 (mejor enfoque):
use el método de tamiz para contar una cantidad de factores primos de cada número menor que N. Y encuentre el número mínimo que tenga la cuenta máxima.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to find maximum number of prime
// factors for a number in range [1, N]
#include <bits/stdc++.h>
using namespace std;
// Return smallest number having maximum
// prime factors.
int maxPrimefactorNum(int N)
{
// Sieve of eratosthenes method to count
// number of unique prime factors.
int arr[N + 1];
memset(arr, 0, sizeof(arr));
for (int i = 2; i * i <= N; i++) {
if (!arr[i])
for (int j = 2 * i; j <= N; j += i)
arr[j]++;
arr[i] = 1;
}
// Return maximum element in arr[]
return *max_element(arr, arr+N);
}
// Driven Program
int main()
{
int N = 40;
cout << maxPrimefactorNum(N) << endl;
return 0;
}
Java
// Java program to find maximum
// number of prime factors for
// a number in range [1, N]
class GFG
{
static int getMax(int[] Arr)
{
int max = Arr[0];
for(int i = 1; i < Arr.length; i++)
if(Arr[i] > max)
max = Arr[i];
return max;
}
// Return smallest number
// having maximum prime factors.
static int maxPrimefactorNum(int N)
{
// Sieve of eratosthenes method
// to count number of unique
// prime factors.
int[] arr = new int[N + 1];
for (int i = 2; i * i <= N; i++)
{
if (arr[i] == 0)
for (int j = 2 * i; j <= N; j += i)
arr[j]++;
arr[i] = 1;
}
// Return maximum element in arr[]
return getMax(arr);
}
// Driver Code
public static void main(String[] args)
{
int N = 40;
System.out.println(maxPrimefactorNum(N));
}
}
// This code is contributed by mits
Python3
# Python3 program to find maximum number # of prime factors for a number in range [1, N] # Return smallest number having maximum # prime factors. def maxPrimefactorNum(N): # Sieve of eratosthenes method to count # number of unique prime factors. arr = [0] * (N + 1); i = 2; while (i * i <= N): if (arr[i] > 0): for j in range(2 * i, N + 1, i): arr[j] += 1; i += 1; arr[i] = 1; # Return maximum element in arr[] return max(arr); # Driver Code N = 40; print(maxPrimefactorNum(N)); # This code is contributed by mits
C#
// C# program to find maximum
// number of prime factors for
// a number in range [1, N]
using System;
class GFG
{
static int getMax(int[] Arr)
{
int max = Arr[0];
for(int i = 1; i < Arr.Length; i++)
if(Arr[i] > max)
max = Arr[i];
return max;
}
// Return smallest number
// having maximum prime factors.
static int maxPrimefactorNum(int N)
{
// Sieve of eratosthenes method
// to count number of unique
// prime factors.
int[] arr = new int[N + 1];
for (int i = 2; i * i <= N; i++)
{
if (arr[i] == 0)
for (int j = 2 * i;
j <= N; j += i)
arr[j]++;
arr[i] = 1;
}
// Return maximum
// element in arr[]
return getMax(arr);
}
// Driver Code
public static void Main()
{
int N = 40;
Console.WriteLine(maxPrimefactorNum(N));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
// PHP program to find maximum number of prime
// factors for a number in range [1, N]
// Return smallest number having maximum
// prime factors.
function maxPrimefactorNum($N)
{
// Sieve of eratosthenes method to count
// number of unique prime factors.
$arr = array_fill(0, $N + 1, 0);
for ($i = 2; $i * $i <= $N; $i++)
{
if (!$arr[$i])
for ($j = 2 * $i; $j <= $N; $j += $i)
$arr[$j]++;
$arr[$i] = 1;
}
// Return maximum element in arr[]
return max($arr);
}
// Driver Code
$N = 40;
echo maxPrimefactorNum($N);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find maximum
// number of prime factors for
// a number in range [1, N]
function getMax(Arr)
{
let max = Arr[0];
for(let i = 1; i < Arr.length; i++)
if(Arr[i] > max)
max = Arr[i];
return max;
}
// Return smallest number
// having maximum prime factors.
function maxPrimefactorNum(N)
{
// Sieve of eratosthenes method
// to count number of unique
// prime factors.
let arr = new Array(N+1).fill(0);
for (let i = 2; i * i <= N; i++)
{
if (arr[i] == 0)
for (let j = 2 * i; j <= N; j += i)
arr[j]++;
arr[i] = 1;
}
// Return maximum element in arr[]
return getMax(arr);
}
// driver program
let N = 40;
document.write(maxPrimefactorNum(N));
</script>
Producción:
3
Complejidad de tiempo: O(n log(log(n)))
Espacio auxiliar: O(n)
Método 3 (enfoque eficiente):
Genere todos los números primos antes de N usando Sieve . Ahora, multiplique números primos consecutivos (comenzando desde el primer número primo) uno tras otro hasta que el producto sea menor que N. La idea se basa en el simple hecho de que el primer conjunto de números primos puede causar un máximo de factores primos únicos.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to find maximum number of prime
// factors in first N natural numbers
#include <bits/stdc++.h>
using namespace std;
// Return maximum number of prime factors for
// any number in [1, N]
int maxPrimefactorNum(int N)
{
if (N < 2)
return 0;
// Based on Sieve of Eratosthenes
// https://www.geeksforgeeks.org/sieve-of-eratosthenes/
bool arr[N+1];
memset(arr, true, sizeof(arr));
int prod = 1, res = 0;
for (int p=2; p*p<=N; p++)
{
// If p is prime
if (arr[p] == true)
{
for (int i=p*2; i<=N; i += p)
arr[i] = false;
// We simply multiply first set
// of prime numbers while the
// product is smaller than N.
prod *= p;
if (prod > N)
return res;
res++;
}
}
return res;
}
// Driven Program
int main()
{
int N = 500;
cout << maxPrimefactorNum(N) << endl;
return 0;
}
Java
// Java program to find maximum
// number of prime factors in
// first N natural numbers
class GFG
{
// Return maximum number
// of prime factors for
// any number in [1, N]
static int maxPrimefactorNum(int N)
{
if (N < 2)
return 0;
// Based on Sieve of Eratosthenes
// https://www.geeksforgeeks.org/sieve-of-eratosthenes/
boolean[] arr = new boolean[N + 1];
int prod = 1, res = 0;
for (int p = 2; p * p <= N; p++)
{
// If p is prime
if (arr[p] == false)
{
for (int i = p * 2;
i <= N; i += p)
arr[i] = true;
// We simply multiply first set
// of prime numbers while the
// product is smaller than N.
prod *= p;
if (prod > N)
return res;
res++;
}
}
return res;
}
// Driver Code
public static void main(String[] args)
{
int N = 500;
System.out.println(maxPrimefactorNum(N));
}
}
// This code is contributed by mits
Python3
# Python3 program to find maximum number # of prime factors in first N natural numbers # Return maximum number of prime factors # for any number in [1, N] def maxPrimefactorNum(N): if (N < 2): return 0; arr = [True] * (N + 1); prod = 1; res = 0; p = 2; while (p * p <= N): # If p is prime if (arr[p] == True): for i in range(p * 2, N + 1, p): arr[i] = False; # We simply multiply first set # of prime numbers while the # product is smaller than N. prod *= p; if (prod > N): return res; res += 1; p += 1; return res; # Driver Code N = 500; print(maxPrimefactorNum(N)); # This code is contributed by mits
C#
// C# program to find maximum number of
// prime factors in first N natural numbers
using System;
class GFG
{
// Return maximum number of prime
// factors for any number in [1, N]
static int maxPrimefactorNum(int N)
{
if (N < 2)
return 0;
// Based on Sieve of Eratosthenes
// https://www.geeksforgeeks.org/sieve-of-eratosthenes/
bool[] arr = new bool[N + 1];
int prod = 1, res = 0;
for (int p = 2; p * p <= N; p++)
{
// If p is prime
if (arr[p] == false)
{
for (int i = p * 2;
i <= N; i += p)
arr[i] = true;
// We simply multiply first set
// of prime numbers while the
// product is smaller than N.
prod *= p;
if (prod > N)
return res;
res++;
}
}
return res;
}
// Driver Code
public static void Main()
{
int N = 500;
Console.WriteLine(maxPrimefactorNum(N));
}
}
// This code is contributed
// by 29AjayKumar
PHP
<?php
// PHP program to find maximum
// number of prime factors in
// first N natural numbers
// Return maximum number of
// prime factors for any
// number in [1, N]
function maxPrimefactorNum($N)
{
if ($N < 2)
return 0;
$arr = array_fill(0, ($N + 1), true);
$prod = 1;
$res = 0;
for ($p = 2;
$p * $p <= $N; $p++)
{
// If p is prime
if ($arr[$p] == true)
{
for ($i = $p * 2;
$i <= $N; $i += $p)
$arr[$i] = false;
// We simply multiply first set
// of prime numbers while the
// product is smaller than N.
$prod *= $p;
if ($prod > $N)
return $res;
$res++;
}
}
return $res;
}
// Driver Code
$N = 500;
echo maxPrimefactorNum($N) . "\n";
// This code is contributed by mits
?>
Javascript
<script>
// javascript program to find maximum
// number of prime factors in
// first N natural numbers
// Return maximum number
// of prime factors for
// any number in [1, N]
function maxPrimefactorNum(N)
{
if (N < 2)
return 0;
// Based on Sieve of Eratosthenes
// https://www.geeksforgeeks.org/sieve-of-eratosthenes/
arr = Array.from({length: N + 1}, (_, i) => false);
var prod = 1, res = 0;
for (var p = 2; p * p <= N; p++)
{
// If p is prime
if (arr[p] == false)
{
for (var i = p * 2;
i <= N; i += p)
arr[i] = true;
// We simply multiply first set
// of prime numbers while the
// product is smaller than N.
prod *= p;
if (prod > N)
return res;
res++;
}
}
return res;
}
// Driver Code
var N = 500;
document.write(maxPrimefactorNum(N));
// This code is contributed by 29AjayKumar
</script>
Producción:
4
Complejidad de tiempo: O(n log(log n))
Espacio auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi y Mohak Agrawal . 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