Algoritmo de la criba de Eratóstenes: Python, C++ Ejemplo

La criba de Eratóstenes es la criba de números primos más sencilla. Es un algoritmo de números primos que busca todos los números primos en un límite determinado. Existen varias cribas de números primos, como por ejemplo la criba de Eratóstenes, la criba de Atkin, la criba de Sundaram, etc.

La palabra "tamiz”significa un utensilio que filtra sustancias. Por lo tanto, el algoritmo de tamiz en Python y otros idiomas se refieren a un algoritmo para filtrar números primos.

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

En el tamiz del método de Eratóstenes, primero se selecciona un número primo pequeño y se filtran todos sus múltiplos. El proceso se ejecuta en un bucle en un rango determinado.

Por ejemplo:

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

Después de aplicar la Criba de Eratóstenes, producirá 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 dado n. Comenzamos con 2, ya que es el primer número primo y el más pequeño.

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 de los números seleccionados.

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 de números 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 <=. Así, atravesando a será suficiente.

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

Ejemplo:

Tomemos un ejemplo y veamos 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 ya que es el número primo más pequeño. Luego 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 forma hasta x= o 5.

Paso 5) Los números restantes no marcados serían los números primos del 2 al 25.

Pseudocódigo

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++ código de ejemplo

#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

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 se requiere el Tamiz de Eratóstenes para ejecutar un bucle a través de todo el rango de números. Por lo tanto, necesita O(n) espacio de memoria para almacenar los números. La situación se complica cuando intentamos encontrar números primos en un rango enorme. No es factible asignar un espacio de memoria tan grande para un 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, repita el segmento y marque el múltiplo 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 gran mejora para una n grande. El método también tiene una desventaja porque no mejora la complejidad temporal.

Análisis de complejidad

Complejidad espacial:

El algoritmo de criba simple de Eratóstenes requiere O(n) espacio de memoria. Y el tamiz segmentado requiere
O() espacio auxiliar.

Complejidad del tiempo:

La complejidad temporal de un algoritmo de criba de Eratóstenes regular es O(n*log(log(n))). El razonamiento que sustenta esta complejidad se analiza a continuación.

Para un número dado n, el tiempo necesario para marcar un número compuesto (es decir, números no primos) es constante. Por lo tanto, la cantidad 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))

Entonces, 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á sobre El triángulo de Pascal

Resumen

• La criba de Eratóstenes filtra los números primos en un límite superior dado.
• El filtrado de un número primo comienza desde el número primo más pequeño, "2". Esto se hace de forma iterativa.
• La iteración se realiza hasta la raíz cuadrada de n, donde n es el rango numérico dado.
• Después de estas iteraciones, los números que quedan son los números primos.