El tamiz de Eratóstenes en Python & C++

¿Qué es el tamiz de Eratóstenes?

La criba de Eratóstenes es la criba de números primos más sencilla. Es un algoritmo que se utiliza para descubrir todos los números primos dentro de un límite dado. Existen varias cribas de números primos, como la de Eratóstenes, la de Atkin y la de Sundaram.

La palabra "tamiz” se refiere a un utensilio que filtra sustancias. En el mismo sentido, el algoritmo de tamizado en Python y otros idiomas se refiere a un método que filtra los números primos de una lista de números enteros.

Este algoritmo filtra los números primos mediante un enfoque iterativo. El proceso de filtrado comienza con el número primo más pequeño. Un número primo es un número natural mayor que 1 que solo tiene dos divisores: 1 y él mismo. Numbers Los números que no son primos se denominan números compuestos.

¿Por qué utilizar el tamiz de Eratóstenes?

En el método de la criba de Eratóstenes, primero se selecciona un número primo pequeño y se descartan todos sus múltiplos. El proceso se ejecuta en bucle a lo largo de un rango determinado, generando eficientemente todos los números primos hasta n sin realizar divisiones de prueba en cada candidato.

Esto hace que el método de cribado sea más rápido que comprobar la primalidad de un número a la vez. Se utiliza ampliamente en teoría de números, criptografía, funciones hash y programación competitiva, donde se deben generar muchos números primos rápidamente.

Por ejemplo:

Tomemos el rango de números del 2 al 10.

Tras aplicar la criba de Eratóstenes, se obtendrá la lista de números primos 2, 3, 5, 7.

Algoritmo Tamiz de Eratóstenes

Aquí está el algoritmo para la Criba de Eratóstenes:

Paso 1) Crea una lista de números desde 2 hasta el rango n dado. Comenzamos con 2 porque es el número primo más pequeño y el primero.

Paso 2) Seleccione el número más pequeño de la lista, x (inicialmente x es igual a 2), recorra la lista y filtre los números compuestos correspondientes marcando todos los múltiplos del número seleccionado.

Paso 3) Luego elija el siguiente número primo o el número sin marcar más pequeño de la lista y repita el paso 2.

Paso 4) Repita el paso anterior hasta que el valor de x sea menor o igual a la raíz cuadrada de n (x<=).

Nota: El razonamiento matemático es bastante simple. El rango numérico n se puede factorizar como:

n = a * b

De nuevo, norte = *

= (factor menor que ) * (factor mayor que )

Entonces al menos uno de los factores primos o ambos deben ser <= Por lo tanto, recorriendo hasta será suficiente.

Paso 5) Después de esos cuatro pasos, los números restantes sin marcar serán todos los números primos en ese rango n dado.

Ejemplo resuelto

Ejemplo:

Veamos un ejemplo y cómo funciona.

Para este ejemplo, encontraremos la lista de números primos del 2 al 25. Entonces, n = 25.

Paso 1) En el primer paso, tomaremos una lista de números del 2 al 25, ya que seleccionamos n = 25.

Paso 2) Luego seleccionamos el número más pequeño de la lista, x. Inicialmente, x = 2 porque es el número primo más pequeño. A continuación, recorremos la lista y marcamos los múltiplos de 2.

Los múltiplos de 2 para el valor dado de n son: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Nota: El color azul indica el número seleccionado, y el color rosa indica los múltiplos eliminados.

Paso 3) Luego elegimos el siguiente número más pequeño sin marcar, que es 3, y repetimos el último paso marcando los múltiplos de 3.

Paso 4) Repetimos el paso 3 de la misma manera hasta que x = o 5.

Paso 5) Los números restantes que no están marcados son los números primos del 2 al 25.

Seudo-Code

El siguiente pseudocódigo captura la estructura básica de la Criba de Eratóstenes antes de traducirla a código real.

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

Tamiz de Eratóstenes C/C++ Code Ejemplo

A continuación se muestra una descripción completa C++ Implementación de la criba de Eratóstenes que imprime todos los números primos hasta un límite superior elegido.

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    }
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
}

Salida:

2 3 5 7 11 13 17 19 23

Tamiz de Eratóstenes Python Ejemplo de programa

Las siguientes Python El programa implementa el mismo algoritmo utilizando una lista booleana y un bucle while.

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

Salida:

2
3
5
7
11
13
17
19
23

Tamiz segmentado

Hemos visto que la criba de Eratóstenes recorre todo el rango de números. Por lo tanto, necesita un espacio de memoria de O(n) para almacenar los números. La situación se complica cuando intentamos encontrar números primos en un rango muy amplio, ya que no es factible asignar un bloque de memoria tan grande para un valor de n mayor.

El algoritmo se puede optimizar introduciendo algunas características nuevas. La idea es dividir el rango de números en segmentos más pequeños y calcular los números primos en esos segmentos uno por uno. Esta es una forma eficiente de reducir la complejidad espacial. Este método se denomina tamiz segmentado.

La optimización se puede lograr de la siguiente manera:

1. Utilice un tamiz simple para encontrar números primos del 2 al XNUMX. y almacenarlos en una matriz.
2. Divida el rango [0…n-1] en múltiples segmentos de tamaño como máximo .
3. Para cada segmento, itere a través del segmento y marque los múltiplos de los números primos encontrados en el paso 1. Este paso requiere O() al máximo.

El tamiz regular requiere O(n) espacio de memoria auxiliar, mientras que el tamiz segmentado requiere O(), lo que supone una mejora sustancial para un n grande. El método también tiene una desventaja, ya que no mejora la complejidad temporal.

Análisis de complejidad

Comprender la complejidad espacial y temporal ayuda a elegir entre el tamiz regular y el tamiz segmentado para un tamaño de problema determinado.

Complejidad espacial:

El algoritmo simple de la criba de Eratóstenes requiere un espacio de memoria de O(n). La criba segmentada requiere O(n).) espacio auxiliar.

Complejidad del tiempo:

La complejidad temporal de un algoritmo de criba de Eratóstenes convencional es O(n*log(log(n))). A continuación se explica el razonamiento detrás de esta complejidad.

Para un número n dado, el tiempo necesario para marcar un número compuesto (es decir, un número no primo) es constante. Por lo tanto, el número de veces que se ejecuta el bucle es igual a:

n/2 + n/3 + n/5 + n/7 + ……∞

= norte * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

La progresión armónica de la suma de los números primos se puede deducir como log(log(n)):

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))

Por lo tanto, la complejidad temporal será:

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= norte * registro (registro (norte))

Por lo tanto, la complejidad temporal es O(n * log(log(n))).

A continuación, aprenderás sobre El triángulo de Pascal.

Preguntas Frecuentes