Dado un número n, imprima todos los números primos menores o iguales an. También se da que n es un número pequeño.
Ejemplo:
Aporte : n = 10 Producción : 2 3 5 7
Aporte : n = 20 Producción: 2 3 5 7 11 13 17 19
El tamiz de Eratóstenes es una de las formas más eficientes de encontrar todos los números primos menores que n cuando n es menor que 10 millones aproximadamente (Ref. Wiki).
A continuación se muestra el algoritmo para encontrar todos los números primos menores o iguales a un entero dado norte por el método de Eratósteno: Cuando el algoritmo termina, todos los números de la lista que no están marcados son primos.
Explicación con ejemplo: Tomemos un ejemplo cuando n = 50. Entonces, necesitamos imprimir todos los números primos menores o iguales que 50. Creamos una lista de todos los números del 2 al 50.
Según el algoritmo marcaremos todos los números que sean divisibles por 2 y sean mayores o iguales al cuadrado del mismo.
Ahora pasamos a nuestro próximo número 3 sin marcar y marcamos todos los números que son múltiplos de 3 y son mayores o iguales que su cuadrado.
Pasamos al siguiente número sin marcar 5 y marcamos todos los múltiplos de 5 y son mayores o iguales al cuadrado del mismo.
Continuamos con este proceso y nuestra mesa final se verá a continuación:
Entonces, los números primos son los que no están marcados: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. Gracias a Krishan Kumar por proporcionar la explicación anterior. Implementación: A continuación se muestra la implementación del algoritmo anterior. En la siguiente implementación, una matriz booleana arr[] de tamaño n se utiliza para marcar múltiplos de números primos.
C ++
#include <bits/stdc++.h>
usingnamespacestd;
voidSieveOfEratosthenes(intn)
{
boolprime[n + 1];
memset(prime, true, sizeof(prime));
for(intp = 2; p * p <= n; p++)
{
if(prime[p] == true)
{
for(inti = p * p; i <= n; i += p)
prime[i] = false;
}
}
for(intp = 2; p <= n; p++)
if(prime[p])
cout << p << " ";
}
intmain()
{
intn = 30;
cout << "Following are the prime numbers smaller "
<< " than or equal to "<< n << endl;
SieveOfEratosthenes(n);
return0;
}
Java
classSieveOfEratosthenes {
voidsieveOfEratosthenes(intn)
{
booleanprime[] = newboolean[n + 1];
for(inti = 0; i <= n; i++)
prime[i] = true;
for(intp = 2; p * p <= n; p++)
{
if(prime[p] == true)
{
for(inti = p * p; i <= n; i += p)
prime[i] = false;
}
}
for(inti = 2; i <= n; i++)
{
if(prime[i] == true)
System.out.print(i + " ");
}
}
publicstaticvoidmain(String args[])
{
intn = 30;
System.out.print(
"Following are the prime numbers ");
System.out.println("smaller than or equal to "+ n);
SieveOfEratosthenes g = newSieveOfEratosthenes();
g.sieveOfEratosthenes(n);
}
}
Pitón
defSieveOfEratosthenes(n):
prime =[Truefori inrange(n+1)]
p =2
while(p *p <=n):
if(prime[p] ==True):
fori inrange(p *p, n+1, p):
prime[i] =False
p +=1
forp inrange(2, n+1):
ifprime[p]:
printp,
if__name__ =='__main__':
n =30
print"Following are the prime numbers smaller",
print"than or equal to", n
SieveOfEratosthenes(n)
C#
usingSystem;
namespaceprime {
publicclassGFG {
publicstaticvoidSieveOfEratosthenes(intn)
{
bool[] prime = newbool[n + 1];
for(inti = 0; i < n; i++)
prime[i] = true;
for(intp = 2; p * p <= n; p++)
{
if(prime[p] == true)
{
for(inti = p * p; i <= n; i += p)
prime[i] = false;
}
}
for(inti = 2; i <= n; i++)
{
if(prime[i] == true)
Console.Write(i + " ");
}
}
publicstaticvoidMain()
{
intn = 30;
Console.WriteLine(
"Following are the prime numbers");
Console.WriteLine("smaller than or equal to "+ n);
SieveOfEratosthenes(n);
}
}
}
PHP
<?php
functionSieveOfEratosthenes($n)
{
$prime= array_fill(0, $n+1, true);
for($p= 2; $p*$p<= $n; $p++)
{
if($prime[$p] == verdadero)
{
for($i= $p*$p; $i<= $n; $i+= $p)
$prime[$i] = falso;
}
}
for($p= 2; $p<= $n; $p++)
if($prime[$p])
echo$p." ";
}
$n= 30;
echo"Following are the prime numbers "
."smaller than or equal to ".$n."n";
SieveOfEratosthenes($n);
?>
Javascript
<script>
functionsieveOfEratosthenes(n)
{
prime = Array.from({length: n+1}, (_, i) => true);
for(p = 2; p * p <= n; p++)
{
if(prime[p] == true)
{
for(i = p * p; i <= n; i += p)
prime[i] = false;
}
}
for(i = 2; i <= n; i++)
{
if(prime[i] == true)
document.write(i + " ");
}
}
varn = 30;
document.write(
"Following are the prime numbers ");
document.write("smaller than or equal to "+ n+"<br>");
sieveOfEratosthenes(n);
</script>
Producción
Following are the prime numbers smaller than or equal to 30
2 3 5 7 11 13 17 19 23 29
Complejidad del tiempo: O (n * log (log (n)))
También te puede interesar ver:
¡Atención lector! No dejes de aprender ahora. Obtenga todos los conceptos importantes de DSA con el Curso autodidacta de DSA a un precio asequible para los estudiantes y prepárese para la industria. Para completar su preparación desde el aprendizaje de un idioma hasta DS Algo y muchos más, consulte Curso completo de preparación para entrevistas.
En caso de que desee asistir clases en vivo con expertos, consulte Clases en vivo de DSA para profesionales que trabajan y Programación competitiva en vivo para estudiantes.
