¿Qué es un algoritmo eficiente para encontrar los primeros cinco números primos de diez dígitos?

El primer algoritmo que viene a la mente es The Sieve of Eratosthenes . Es un algoritmo bastante famoso, no solo por su utilidad, sino por su historia que se remonta hasta el siglo III a. C. ¡Guay!

El algoritmo

1. Haga una tabla una entrada para cada número 2 ≤ n≤ límite
2. Comenzando en 2, tache todos los múltiplos de 2, sin contar 2 en sí.
3. Avanzar al siguiente número que no ha sido tachado
4. Repita los pasos 2-3 hasta [math] \ sqrt n [/ math]

Se puede demostrar que el Tamiz de Eratóstenes tiene una complejidad temporal de [matemática] \ matemática {O} (n \ log \ log {n}) [/ matemática]

Visualmente podemos representar cada ciclo eliminando valores de la lista
de números reales hasta que todo lo que queda son los primos.

Cada arco es un bucle

Implementación de Python:

def sieve(n):
"""Sieve away and only primes are left."""
primes = set(range(2, n+1))
for i in range(2,int(n**0.5+1)):
if i in primes:
primes -= set(range(i*i, n+1, i))
return primes

Implementación rápida de Python

Esto corre aproximadamente 2-3 veces más lento que la versión compilada de C ++.

import numpy as np

def np_sieve (n):
“” “Tamiz con sus tripas intercambiadas con ndarray numpy” “”
primos = np.ones (n + 1, dtype = np.bool)
para i en np.arange (2, n ** 0.5 + 1, dtype = np.uint32):
si primos [i]:
primos [i * i :: i] = falso
return np.nonzero (primos) [0] [2:]

Generalmente, el código CPython normal es lento, pero Python tiene muchas herramientas para hacerlo rápido cuando sea necesario.

Esto le da al programador la libertad de un lenguaje dinámico / interpretado, y la posibilidad de optimización de una manera vinculante tardía.

Ejecútalo tú mismo:

Ejecutar código

Juega un poco con él, usé el set la estructura de datos porque es más fácil de visualizar, pero puede intentar implementar array , list , incluso dict .

Visualízalo

Visualiza la ejecución del programa

¿Ves cómo comienzas con cada número de 0 a n?

Esta es probablemente una de las desventajas de los tamices, ya que requiere una tabla de cada número hasta el último entero en la memoria, la complejidad del espacio generalmente crece en el orden de [math] \ mathcal {O} (n) [/ math ]

Compruebe usted mismo

def all_primes(primes):
for prime in primes:
if any(prime % n == 0 for n in range(2, int(prime))):
return False
return True

#include

int main ()
{
int n, i = 3, cuenta, c;

printf (“Ingrese el número de números primos requeridos \ n”);
scanf (“% d”, & n);

si (n> = 1)
{
printf (“Los primeros números primos% d son: \ n”, n);
printf (“2 \ n”);
}

para (cuenta = 1000000000; cuenta <= 9999999999;)
{
para (c = 2; c <= i - 1; c ++)
{
si (i% c == 0)
descanso;
}
si (c == i)
{
printf (“% d \ n”, i);
recuento ++;
}
i ++;
}

devuelve 0;
}

Aquí hay otra versión en Java con la función integrada isprobablePrime ()

import java.io. *;
import java.math. *;

clase Prime_
{
public static void main (String [] args) arroja java.lang.Exception
{

BigInteger N = nuevo BigInteger (“10000000000”);
para (int i = 1; i <= 100; i ++)
{

N = N.nextProbablePrime ();
System.out.println (N);
}
}
}

10000000019
10000000033
10000000061
10000000069
10000000097
10000000103
10000000121

La división de prueba sin calcular previamente los números primos también es lo suficientemente rápida (como máximo 32k divisiones por número).

remains, current = 5, 10**9
while remains > 0:
current += 1
prime = True
for n in range(2,current):
if current%n == 0: prime = False
if (not prime) or (n*n>current): break
if prime:
print(current)
remains -= 1


Y para los flojos siempre hay magia de bash shell:

$ bc <<< "10 ^ 9; 10 ^ 9 + 90" | xargs seq | factor | grep -v '. *'
1000000007: 1000000007
1000000009: 1000000009
1000000021: 1000000021
1000000033: 1000000033
1000000087: 1000000087