Dado un número n , imprima los factores primos mínimos de todos los números del 1 al n. El menor factor primo de un entero n es el número primo más pequeño que divide al número. El menor factor primo de todos los números pares es 2. Un número primo es su propio factor primo menor (así como su propio factor primo mayor).
Nota: Necesitamos imprimir 1 por 1.
Ejemplo:
Input : 6
Output : Least Prime factor of 1: 1
Least Prime factor of 2: 2
Least Prime factor of 3: 3
Least Prime factor of 4: 2
Least Prime factor of 5: 5
Least Prime factor of 6: 2
Podemos usar una variación del tamiz de Eratóstenes para resolver el problema anterior.
- Cree una lista de enteros consecutivos del 2 al n: (2, 3, 4, …, n).
- Inicialmente, sea i igual a 2, el número primo más pequeño.
- Enumere los múltiplos de i contando hasta n desde 2i en incrementos de i, y márquelos como si tuvieran el menor factor primo como i (si aún no están marcados). También marque i como el menor factor primo de i (yo mismo es un número primo).
- Encuentra el primer número mayor que i en la lista que no está marcado. Si no hubiera tal número, deténgase. De lo contrario, igualemos ahora este nuevo número (que es el próximo primo) y repitamos desde el paso 3.
A continuación se muestra la implementación del algoritmo, donde less_prime[] guarda el valor del menor factor primo correspondiente al índice respectivo.
C++
// C++ program to print the least prime factors
// of numbers less than or equal to
// n using modified Sieve of Eratosthenes
#include<bits/stdc++.h>
using namespace std;
void leastPrimeFactor(int n)
{
// Create a vector to store least primes.
// Initialize all entries as 0.
vector<int> least_prime(n+1, 0);
// We need to print 1 for 1.
least_prime[1] = 1;
for (int i = 2; i <= n; i++)
{
// least_prime[i] == 0
// means it i is prime
if (least_prime[i] == 0)
{
// marking the prime number
// as its own lpf
least_prime[i] = i;
// mark it as a divisor for all its
// multiples if not already marked
for (int j = i*i; j <= n; j += i)
if (least_prime[j] == 0)
least_prime[j] = i;
}
}
// print least prime factor of
// of numbers till n
for (int i = 1; i <= n; i++)
cout << "Least Prime factor of "
<< i << ": " << least_prime[i] << "\n";
}
// Driver program to test above function
int main()
{
int n = 10;
leastPrimeFactor(n);
return 0;
}
Java
// Java program to print the least prime factors
// of numbers less than or equal to
// n using modified Sieve of Eratosthenes
import java.io.*;
import java.util.*;
class GFG
{
public static void leastPrimeFactor(int n)
{
// Create a vector to store least primes.
// Initialize all entries as 0.
int[] least_prime = new int[n+1];
// We need to print 1 for 1.
least_prime[1] = 1;
for (int i = 2; i <= n; i++)
{
// least_prime[i] == 0
// means it i is prime
if (least_prime[i] == 0)
{
// marking the prime number
// as its own lpf
least_prime[i] = i;
// mark it as a divisor for all its
// multiples if not already marked
for (int j = i*i; j <= n; j += i)
if (least_prime[j] == 0)
least_prime[j] = i;
}
}
// print least prime factor of
// of numbers till n
for (int i = 1; i <= n; i++)
System.out.println("Least Prime factor of " +
+ i + ": " + least_prime[i]);
}
public static void main (String[] args)
{
int n = 10;
leastPrimeFactor(n);
}
}
// Code Contributed by Mohit Gupta_OMG <(0_o)>
Python 3
# Python 3 program to print the
# least prime factors of numbers
# less than or equal to n using
# modified Sieve of Eratosthenes
def leastPrimeFactor(n) :
# Create a vector to store least primes.
# Initialize all entries as 0.
least_prime = [0] * (n + 1)
# We need to print 1 for 1.
least_prime[1] = 1
for i in range(2, n + 1) :
# least_prime[i] == 0
# means it i is prime
if (least_prime[i] == 0) :
# marking the prime number
# as its own lpf
least_prime[i] = i
# mark it as a divisor for all its
# multiples if not already marked
for j in range(i * i, n + 1, i) :
if (least_prime[j] == 0) :
least_prime[j] = i
# print least prime factor
# of numbers till n
for i in range(1, n + 1) :
print("Least Prime factor of "
,i , ": " , least_prime[i] )
# Driver program
n = 10
leastPrimeFactor(n)
# This code is contributed
# by Nikita Tiwari.
C#
// C# program to print the least prime factors
// of numbers less than or equal to
// n using modified Sieve of Eratosthenes
using System;
class GFG
{
public static void leastPrimeFactor(int n)
{
// Create a vector to store least primes.
// Initialize all entries as 0.
int []least_prime = new int[n+1];
// We need to print 1 for 1.
least_prime[1] = 1;
for (int i = 2; i <= n; i++)
{
// least_prime[i] == 0
// means it i is prime
if (least_prime[i] == 0)
{
// marking the prime number
// as its own lpf
least_prime[i] = i;
// mark it as a divisor for all its
// multiples if not already marked
for (int j = i*i; j <= n; j += i)
if (least_prime[j] == 0)
least_prime[j] = i;
}
}
// print least prime factor of
// of numbers till n
for (int i = 1; i <= n; i++)
Console.WriteLine("Least Prime factor of " +
i + ": " + least_prime[i]);
}
// Driver code
public static void Main ()
{
int n = 10;
// Function calling
leastPrimeFactor(n);
}
}
// This code is contributed by Nitin Mittal
PHP
<?php
// PHP program to print the
// least prime factors of
// numbers less than or equal
// to n using modified Sieve
// of Eratosthenes
function leastPrimeFactor($n)
{
// Create a vector to
// store least primes.
// Initialize all entries
// as 0.
$least_prime = array($n + 1);
for ($i = 0;
$i <= $n; $i++)
$least_prime[$i] = 0;
// We need to
// print 1 for 1.
$least_prime[1] = 1;
for ($i = 2; $i <= $n; $i++)
{
// least_prime[i] == 0
// means it i is prime
if ($least_prime[$i] == 0)
{
// marking the prime
// number as its own lpf
$least_prime[$i] = $i;
// mark it as a divisor
// for all its multiples
// if not already marked
for ($j = $i * $i;
$j <= $n; $j += $i)
if ($least_prime[$j] == 0)
$least_prime[$j] = $i;
}
}
// print least prime
// factor of numbers
// till n
for ($i = 1; $i <= $n; $i++)
echo "Least Prime factor of " .
$i . ": " .
$least_prime[$i] . "\n";
}
// Driver Code
$n = 10;
leastPrimeFactor($n);
// This code is contributed
// by Sam007
?>
Javascript
<script>
// javascript program to print the least prime factors
// of numbers less than or equal to
// n using modified Sieve of Eratosthenes
function leastPrimeFactor( n)
{
// Create a vector to store least primes.
// Initialize all entries as 0.
let least_prime = Array(n+1).fill(0);
// We need to print 1 for 1.
least_prime[1] = 1;
for (let i = 2; i <= n; i++)
{
// least_prime[i] == 0
// means it i is prime
if (least_prime[i] == 0)
{
// marking the prime number
// as its own lpf
least_prime[i] = i;
// mark it as a divisor for all its
// multiples if not already marked
for (let j = i*i; j <= n; j += i)
if (least_prime[j] == 0)
least_prime[j] = i;
}
}
// print least prime factor of
// of numbers till n
for (let i = 1; i <= n; i++)
document.write( "Least Prime factor of "
+ i + ": " + least_prime[i] + "<br/>");
}
// Driver program to test above function
let n = 10;
leastPrimeFactor(n);
// This code is contributed by Rajput-Ji
</script>
Producción
Least Prime factor of 1: 1 Least Prime factor of 2: 2 Least Prime factor of 3: 3 Least Prime factor of 4: 2 Least Prime factor of 5: 5 Least Prime factor of 6: 2 Least Prime factor of 7: 7 Least Prime factor of 8: 2 Least Prime factor of 9: 3 Least Prime factor of 10: 2
Complejidad de tiempo: O(nloglog(n))
Espacio auxiliar: O(n)
Referencias:
1. https://www.geeksforgeeks.org/sieve-of-eratosthenes/
2. https://en.wikipedia.org/wiki /Sieve_of_Eratosthenes
3. https://oeis.org/wiki/Least_prime_factor_of_n
Ejercicio:
¿Podemos extender este algoritmo o usar less_prime[] para encontrar todos los factores primos para números hasta n?
Este artículo es una contribución de Ayush Khanduri . 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