in

Tamiz de Eratóstenes – GeeksforGeeks

gfg 200x200 min

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.

Tamiz1

Según el algoritmo marcaremos todos los números que sean divisibles por 2 y sean mayores o iguales al cuadrado del mismo.

tamiz2

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.

Tamiz de Eratóstenes3

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.

Tamiz4

Continuamos con este proceso y nuestra mesa final se verá a continuación:

Tamiz5

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>

using namespace std;

void SieveOfEratosthenes(int n)

{

    

    

    

    

    

    

    bool prime[n + 1];

    memset(prime, true, sizeof(prime));

    for (int p = 2; p * p <= n; p++)

    {

        

        

        if (prime[p] == true)

        {

            

            

            

            

            

            

            for (int i = p * p; i <= n; i += p)

                prime[i] = false;

        }

    }

    

    for (int p = 2; p <= n; p++)

        if (prime[p])

            cout << p << " ";

}

int main()

{

    int n = 30;

    cout << "Following are the prime numbers smaller "

         << " than or equal to " << n << endl;

    SieveOfEratosthenes(n);

    return 0;

}

Java

class SieveOfEratosthenes {

    void sieveOfEratosthenes(int n)

    {

        

        

        

        

        

        

        

        boolean prime[] = new boolean[n + 1];

        for (int i = 0; i <= n; i++)

            prime[i] = true;

        for (int p = 2; p * p <= n; p++)

        {

            

            

            if (prime[p] == true)

            {

                

                for (int i = p * p; i <= n; i += p)

                    prime[i] = false;

            }

        }

        

        for (int i = 2; i <= n; i++)

        {

            if (prime[i] == true)

                System.out.print(i + " ");

        }

    }

    

    public static void main(String args[])

    {

        int n = 30;

        System.out.print(

            "Following are the prime numbers ");

        System.out.println("smaller than or equal to " + n);

        SieveOfEratosthenes g = new SieveOfEratosthenes();

        g.sieveOfEratosthenes(n);

    }

}

Pitón

def SieveOfEratosthenes(n):

    

    

    

    

    

    

    prime = [True for i in range(n+1)]

    p = 2

    while (p * p <= n):

        

        

        if (prime[p] == True):

            

            for i in range(p * p, n+1, p):

                prime[i] = False

        p += 1

    

    for p in range(2, n+1):

        if prime[p]:

            print p,

if __name__ == '__main__':

    n = 30

    print "Following are the prime numbers smaller",

    print "than or equal to", n

    SieveOfEratosthenes(n)

C#

using System;

namespace prime {

public class GFG {

    public static void SieveOfEratosthenes(int n)

    {

        

        

        

        

        

        

        

        bool[] prime = new bool[n + 1];

        for (int i = 0; i < n; i++)

            prime[i] = true;

        for (int p = 2; p * p <= n; p++)

        {

            

            

            if (prime[p] == true)

            {

                

                for (int i = p * p; i <= n; i += p)

                    prime[i] = false;

            }

        }

        

        for (int i = 2; i <= n; i++)

        {

            if (prime[i] == true)

                Console.Write(i + " ");

        }

    }

    

    public static void Main()

    {

        int n = 30;

        Console.WriteLine(

            "Following are the prime numbers");

        Console.WriteLine("smaller than or equal to " + n);

        SieveOfEratosthenes(n);

    }

}

}

PHP

<?php

function SieveOfEratosthenes($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>

function sieveOfEratosthenes(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 + " ");

    }

}

var n = 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.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.

apple touch icon@2

javascript – ¿Cuál es el significado del símbolo $ en jQuery?

edit

Agave vs miel: diferencia y comparación