¿Código más eficiente para los primeros 10000 números primos?

Quiero imprimir los primeros 10000 números primos. ¿Alguien puede darme el código más eficiente para esto? Aclaraciones:

  1. No importa si tu código es ineficiente para n> 10000.
  2. El tamaño del código no importa.
  3. No puedes codificar los valores de ninguna manera.

El Tamiz de Atkin es probablemente lo que estás buscando, su tiempo límite de ejecución es O (N / log log N).

Si solo ejecuta los números 1 más y 1 menos que los múltiplos de 6, podría ser aún más rápido, ya que todos los números primos por encima de 3 están a 1 de distancia de un múltiplo de seis. Recurso para mi statement

Recomiendo un tamiz, ya sea el Tamiz de Eratóstenes o el Tamiz de Atkin.

El tamiz o Eratóstenes es probablemente el método más intuitivo para encontrar una lista de primos. Básicamente tú:

  1. Escriba una lista de números del 2 al límite que desee, digamos 1000.
  2. Tome el primer número que no esté tachado (para la primera iteración esto es 2) y tache todos los múltiplos de ese número de la lista.
  3. Repite el paso 2 hasta llegar al final de la lista. Todos los números que no están tachados son primos.

Obviamente hay bastantes optimizaciones que se pueden hacer para que este algoritmo funcione más rápido, pero esta es la idea básica.

El tamiz de Atkin usa un enfoque similar, pero desafortunadamente no sé lo suficiente como para explicarte. Pero sí sé que el algoritmo que he vinculado toma 8 segundos para calcular todos los números primos hasta 1000000000 en un antiguo Pentium II-350

Tamiz de Eratóstenes Código Fuente: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Código fuente de Sieve of Atkin: http://cr.yp.to/primegen.html

Esto no es estrictamente contrario a la restricción de encoding rígida, pero llega terriblemente cerca. ¿Por qué no descargar programáticamente esta lista e imprimirla?

http://primes.utm.edu/lists/small/10000.txt

GateKiller , ¿qué le parece agregar un break a eso if en el ciclo foreach ? Eso aceleraría mucho las cosas porque si como 6 es divisible por 2, no es necesario que compruebes con 3 y 5. (De todos modos, votaría tu solución si tuviera suficiente reputación 🙂 …)

 ArrayList primeNumbers = new ArrayList(); for(int i = 2; primeNumbers.Count < 10000; i++) { bool divisible = false; foreach(int number in primeNumbers) { if(i % number == 0) { divisible = true; break; } } if(divisible == false) { primeNumbers.Add(i); Console.Write(i + " "); } } 

En Haskell, podemos escribir casi palabra por palabra la definición matemática del tamiz de Eratóstenes, “los números primos son números naturales por encima de 1 sin ningún número compuesto, donde los compuestos se encuentran por enumeración de los múltiplos de cada primo “:

 primes = 2 : minus [3..] (foldr (\pr -> p*p : union [p*p+p, p*p+2*p..] r) [] primes) 

primes !! 10000 primes !! 10000 es casi instantáneo.

Referencias

  • Tamiz de Eratóstenes
  • El tamiz de Richard Bird (ver pp. 10,11)
  • menos, unión

El código anterior se ajusta fácilmente para trabajar solo en probabilidades, primes = 2 : 3 : minus [5,7..] (foldr (\pr -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)) . La complejidad del tiempo ha mejorado mucho (hasta casi un factor log por encima de lo óptimo) al plegarse en una estructura similar a un árbol, y la complejidad del espacio se mejora drásticamente mediante la producción de primos multietapa , en

 primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) ) where _Y g = g (_Y g) -- non-sharing fixpoint combinator _U ((x:xs):t) = x : (union xs . _U . pairs) t -- ~= nub.sort.concat pairs (xs:ys:t) = union xs ys : pairs t sieve ks@(x:xs) | k < x = k : sieve (k+2) s -- ~= [k,k+2..]\\s, | otherwise = sieve (k+2) xs -- when s⊂[k,k+2..] 

(En Haskell, los paréntesis se utilizan para agrupar, una llamada a función se representa simplemente por yuxtaposición, (:) es un operador contra para listas, y (.) Es un operador de composición funcional: (f . g) x = (\y -> f (gy)) x = f (gx) ).

@Matt: log (log (10000)) es ~ 2

Del artículo de wikipedia (que citó) Sieve of Atkin :

Este tamiz calcula números primos hasta N usando operaciones O(N/log log N) con solo N 1/2 + o (1) bits de memoria. Eso es un poco mejor que el tamiz de Eratóstenes que usa operaciones O(N) y O (N 1/2 (log log N) / log N) bits de memoria (AOL Atkin, DJ Bernstein, 2004) . Estas complejidades computacionales asintóticas incluyen optimizaciones simples, como la factorización de las ruedas, y la división del cálculo en bloques más pequeños.

Dadas las complejidades computacionales asintóticas a lo largo de O(N) (para Eratóstenes) y O(N/log(log(N))) (para Atkin) no podemos decir (para N=10_000 pequeño N=10_000 ) qué algoritmo, si se implementa, será más rápido.

Achim Flammenkamp escribió en El tamiz de Eratóstenes :

citado por:

@ num1

Para intervalos mayores alrededor de 10 ^ 9, seguramente para aquellos> 10 ^ 10, el Tamiz de Eratóstenes es superado por el Tamiz de Atkins y Bernstein que usa formas cuadráticas binarias irreductibles. Consulte su documento para obtener información de antecedentes, así como el párrafo 5 del Ph.D. de W. Galway. tesis.

Por lo tanto, para 10_000 Tamiz de Eratóstenes puede ser más rápido que Tamiz de Atkin.

Para responder a OP el código es prime_sieve.c (citado por num1 )

Usando GMP, uno podría escribir lo siguiente:

 #include  #include  int main() { mpz_t prime; mpz_init(prime); mpz_set_ui(prime, 1); int i; char* num = malloc(4000); for(i=0; i<10000; i++) { mpz_nextprime(prime, prime); printf("%s, ", mpz_get_str(NULL,10,prime)); } } 

En mi Macbook Pro a 2.33 GHz, se ejecuta de la siguiente manera:

 time ./a.out > /dev/null real 0m0.033s user 0m0.029s sys 0m0.003s 

Cálculo de 1,000,000 primos en la misma computadora portátil:

 time ./a.out > /dev/null real 0m14.824s user 0m14.606s sys 0m0.086s 

GMP está altamente optimizado para este tipo de cosas. A menos que realmente desee comprender los algoritmos escribiendo el suyo, se le aconsejará usar libGMP en C.

He adaptado el código encontrado en CodeProject para crear lo siguiente:

 ArrayList primeNumbers = new ArrayList(); for(int i = 2; primeNumbers.Count < 10000; i++) { bool divisible = false; foreach(int number in primeNumbers) { if(i % number == 0) { divisible = true; } } if(divisible == false) { primeNumbers.Add(i); Console.Write(i + " "); } } 

Probar esto en mi Servidor ASP.NET tomó la rountine alrededor de 1 minuto para ejecutarse.

No es eficiente en absoluto, pero puede usar una expresión regular para probar los números primos.

 /^1?$|^(11+?)\1+$/ 

Esto prueba si, para una cadena que consta de k1 ” s, k no es primo (es decir, si la cadena consta de un ” 1 ” o cualquier cantidad de ” 1 ” s que pueda expressse como un producto n- ario).

Aquí hay un Tamiz de Eratóstenes que escribí en PowerShell hace unos días. Tiene un parámetro para identificar la cantidad de números primos que se deben devolver.

 # # generate a list of primes up to a specific target using a sieve of eratosthenes # function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes param ($target,$count = 0) $sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target $sieve = @($false) * $sieveBound $crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2) for ($i = 1; $i -le $crossLimit; $i ++) { if ($sieve[$i] -eq $false) { $prime = 2 * $i + 1 write-debug "Found: $prime" for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) { $sieve[$x] = $true } } } $primes = @(2) for ($i = 1; $i -le $sieveBound; $i ++) { if($count -gt 0 -and $primes.length -ge $count) { break; } if($sieve[$i] -eq $false) { $prime = 2 * $i + 1 write-debug "Output: $prime" $primes += $prime } } return $primes } 

Sieve of Eratosthenes es el camino a seguir, debido a su simplicidad y velocidad. Mi implementación en C

 #include  #include  #include  #include  int main(void) { unsigned int lim, i, j; printf("Find primes upto: "); scanf("%d", &lim); lim += 1; bool *primes = calloc(lim, sizeof(bool)); unsigned int sqrtlim = sqrt(lim); for (i = 2; i <= sqrtlim; i++) if (!primes[i]) for (j = i * i; j < lim; j += i) primes[j] = true; printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1); for (i = 2; i < lim; i++) if (!primes[i]) printf("%d\n", i); return 0; } 

Tiempo de CPU para encontrar primos (en Pentium Dual Core E2140 1.6 GHz, utilizando un solo núcleo)

~ 4s por lim = 100,000,000

Adaptando y siguiendo de GateKiller , aquí está la versión final que he usado.

  public IEnumerable PrimeNumbers(long number) { List primes = new List(); for (int i = 2; primes.Count < number; i++) { bool divisible = false; foreach (int num in primes) { if (i % num == 0) divisible = true; if (num > Math.Sqrt(i)) break; } if (divisible == false) primes.Add(i); } return primes; } 

Es básicamente lo mismo, pero agregué la sugerencia “break on Sqrt” y cambié algunas de las variables para que me quedara mejor. (Estaba trabajando en Euler y necesitaba el primo 10001)

El tamiz parece ser la respuesta incorrecta. El tamiz te da los números primos hasta un número N , no los primeros N primos. Ejecute @Imran o @Andrew Szeto, y obtendrá los números primos hasta N.

El tamiz podría ser útil si sigues probando tamices para números cada vez más grandes hasta que scopes un determinado tamaño de tu conjunto de resultados, y utilizas un poco de almacenamiento en caché de los números ya obtenidos, pero creo que todavía no sería más rápido que una solución como @ Pat’s .

En Python

 import gmpy p=1 for i in range(10000): p=gmpy.next_prime(p) print p 

El algoritmo de cribado de deque mencionado por BenGoldberg merece una mirada más cercana, no solo porque es muy elegante sino también porque a veces puede ser útil en la práctica (a diferencia del Tamiz de Atkin, que es un ejercicio puramente académico).

La idea básica detrás del algoritmo de siega de tamiz es usar un pequeño tamiz deslizante que sea lo suficientemente grande como para contener al menos un múltiplo separado para cada uno de los factores primos actualmente activos, es decir, aquellos números primos cuyo cuadrado no exceda el número más bajo actualmente representado por el tamiz móvil. Otra diferencia con el SoE es que el filtro deque almacena los factores reales en las ranuras de los composites, no booleanos.

El algoritmo amplía el tamaño de la ventana del tamiz según sea necesario, lo que resulta en un rendimiento bastante uniforme en un amplio rango hasta que el tamiz comienza a exceder la capacidad de la memoria caché L1 de la CPU de manera apreciable. El último primo que cabe por completo es 25,237,523 (el primo 1,579,791), que da una cifra de estadio aproximado para el rango operativo razonable del algoritmo.

El algoritmo es bastante simple y robusto, e incluso tiene un rendimiento en un rango mucho más amplio que un tamiz no segmentado de Eratóstenes. Este último es mucho más rápido siempre que su tamiz se ajuste completamente a la memoria caché, es decir, hasta 2 ^ 16 para un tamiz de probabilidades con bools de tamaño byte. Luego, su rendimiento disminuye más y más, aunque siempre permanece significativamente más rápido que el deque a pesar del handicap (al menos en lenguajes comstackdos como C / C ++, Pascal o Java / C #).

Aquí hay una representación del algoritmo de siega criba en C #, porque creo que ese lenguaje, a pesar de sus muchos defectos, es mucho más práctico para los algoritmos de prototipado y la experimentación que el C ++ supremamente engorroso y pedante. (Nota: estoy usando el LINQPad gratuito que permite sumergirse sin problemas en la configuración de proyectos, archivos make, directorios o cosas por el estilo, y me da el mismo grado de interactividad que el de Python).

C # no tiene un tipo explícito deque, pero la List simple List funciona lo suficientemente bien como para demostrar el algoritmo.

Nota: esta versión no usa un deque para los números primos, porque simplemente no tiene sentido sacar sqrt (n) de n primos. ¿De qué serviría eliminar 100 primos y dejar 9900? Al menos de esta manera, todos los números primos se recostackn en un vector ordenado, listo para su posterior procesamiento.

 static List deque_sieve (int n = 10000) { Trace.Assert(n >= 3); var primes = new List() { 2, 3 }; var sieve = new List() { 0, 0, 0 }; for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; ) { int base_factor = sieve[0]; if (base_factor != 0) { // the sieve base has a non-trivial factor - put that factor back into circulation mark_next_unmarked_multiple(sieve, base_factor); } else if (sieve_base < current_prime_squared) // no non-trivial factor -> found a non-composite { primes.Add(sieve_base); if (primes.Count == n) return primes; } else // sieve_base == current_prime_squared { // bring the current prime into circulation by injecting it into the sieve ... mark_next_unmarked_multiple(sieve, primes[current_prime_index]); // ... and elect a new current prime current_prime_squared = square(primes[++current_prime_index]); } // slide the sieve one step forward sieve.RemoveAt(0); sieve_base += 2; } } 

Aquí están las dos funciones de ayuda:

 static void mark_next_unmarked_multiple (List sieve, int prime) { int i = prime, e = sieve.Count; while (i < e && sieve[i] != 0) i += prime; for ( ; e <= i; ++e) // no List<>.Resize()... sieve.Add(0); sieve[i] = prime; } static int square (int n) { return n * n; } 

Probablemente la forma más fácil de entender el algoritmo es imaginarlo como un tamiz especial segmentado de Eratóstenes con un tamaño de segmento de 1, acompañado por un área de desbordamiento donde los primos se detienen cuando disparan sobre el final del segmento. Excepto que la celda individual del segmento (también conocido como sieve[0] ) ya ha sido tamizada cuando llegamos a ella, porque se atropelló mientras formaba parte del área de desbordamiento.

El número representado por sieve[0] se mantiene en sieve_base , aunque sieve_front o window_base también serían buenos nombres que permiten establecer paralelismos con el código de Ben o implementaciones de tamices segmentados / con ventana.

Si el sieve[0] contiene un valor distinto de cero, ese valor es un factor de sieve_base , que se puede reconocer como compuesto. Como la celda 0 es un múltiplo de ese factor, es fácil calcular su próximo salto, que es simplemente 0 más ese factor. Si esa celda ya está ocupada por otro factor, simplemente agregamos el factor nuevamente, y así sucesivamente hasta que encontremos un múltiplo del factor donde no hay otro factor actualmente estacionado (extendiendo el tamiz si es necesario). Esto también significa que no hay necesidad de almacenar los desplazamientos de trabajo actuales de los diversos números primos de un segmento al siguiente, como en un tamiz segmentado normal. Cada vez que encontramos un factor en el sieve[0] , su desplazamiento de trabajo actual es 0.

La prima actual entra en juego de la siguiente manera. Un primo solo puede volverse actual después de su propia aparición en la secuencia (es decir, cuando se ha detectado como primo, porque no está marcado con un factor), y permanecerá vigente hasta el momento exacto en que el sieve[0] scope su cuadrado. Todos los múltiplos inferiores de este primo deben haber sido eliminados debido a las actividades de números primos más pequeños, al igual que en un SoE normal. Pero ninguno de los números primos más pequeños puede tachar el cuadrado, ya que el único factor del cuadrado es el primo mismo y aún no está en circulación en este punto. Eso explica las acciones tomadas por el algoritmo en el caso sieve_base == current_prime_squared (que implica sieve[0] == 0 , por cierto).

Ahora el sieve[0] == 0 && sieve_base < current_prime_squared caja sieve[0] == 0 && sieve_base < current_prime_squared se explica fácilmente: significa que sieve_base no puede ser un múltiplo de ninguno de los primos más pequeños que el primo actual, de lo contrario se habría marcado como compuesto. Tampoco puedo ser un múltiplo superior del primo actual, ya que su valor es menor que el cuadrado del primo actual. Por lo tanto, debe ser un nuevo primo.

El algoritmo está obviamente inspirado en el Tamiz de Eratóstenes, pero igualmente obviamente es muy diferente. El tamiz de Eratóstenes deriva su velocidad superior de la simplicidad de sus operaciones elementales: una sola adición de índice y una tienda para cada paso de la operación es todo lo que hace durante largos períodos de tiempo.

Aquí hay un Tamiz de Eratostenes simple, no segmentado, que normalmente uso para primos de factor de tamizado en el rango de ushort, es decir, hasta 2 ^ 16. Para esta publicación lo he modificado para trabajar más allá de 2 ^ 16 sustituyendo int por ushort

 static List small_odd_primes_up_to (int n) { var result = new List(); if (n < 3) return result; int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1; var odd_composite = new bool[max_bit + 1]; for (int i = 3 >> 1; i <= sqrt_n_halved; ++i) if (!odd_composite[i]) for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p) odd_composite[j] = true; result.Add(3); // needs to be handled separately because of the mod 3 wheel // read out the sieved primes for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3) if (!odd_composite[i]) result.Add((i << 1) + 1); return result; } 

Al tamizar los primeros primos 10000, se excederá una caché L1 típica de 32 KiByte, pero la función sigue siendo muy rápida (fracción de milisegundo incluso en C #).

Si compara este código con el filtro de deque, entonces es fácil ver que las operaciones del filtro de deque son mucho más complicadas, y no puede amortizar efectivamente su sobrecarga porque siempre hace el tramo más corto posible de cruce en una fila (exactamente un solo cruce, después de omitir todos los múltiplos que ya han sido tachados).

Nota: el código C # usa int lugar de uint porque los comstackdores más nuevos tienen la costumbre de generar código inferior para uint , probablemente para empujar a la gente hacia enteros con signo ... En la versión C ++ del código anterior, utilicé unsigned todo, naturalmente; el punto de referencia tenía que estar en C ++ porque quería que se basara en un tipo de deque supuestamente adecuado ( std::deque ; no había ganancia de rendimiento al usar un unsigned short ). Aquí están los números de mi computadora portátil Haswell (VC ++ 2015 / x64):

 deque vs simple: 1.802 ms vs 0.182 ms deque vs simple: 1.836 ms vs 0.170 ms deque vs simple: 1.729 ms vs 0.173 ms 

Nota: los tiempos de C # son casi exactamente el doble de los tiempos de C ++, lo cual es bastante bueno para C # y muestra que List no se queda atrás incluso si se abusa de deque.

El código de tamiz simple todavía expulsa el deque del agua, a pesar de que ya está funcionando más allá de su rango de trabajo normal (el tamaño de caché L1 excedió en un 50%, con la acumulación de caché). La parte dominante aquí es la lectura de los primos tamizados, y esto no se ve muy afectado por el problema de la memoria caché. En cualquier caso, la función fue diseñada para tamizar los factores de factores, es decir, el nivel 0 en una jerarquía de tamices de 3 niveles, y típicamente tiene que devolver solo unos pocos cientos de factores o un número bajo de miles. De ahí su simplicidad.

El rendimiento podría mejorarse más de un orden de magnitud utilizando un tamiz segmentado y optimizando el código para extraer los primos tamizados (mod 3 escalonado y desenrollado dos veces, o mod 15 y desenrollado una vez), y aún más rendimiento podría ser exprimido de el código usando una rueda mod 16 o mod 30 con todos los recortes (es decir, desenrollado completo para todos los residuos). Algo así se explica en mi respuesta a Encontrar el número primo de posición principal en Revisión de código, donde se discutió un problema similar. Pero es difícil ver el punto de mejorar los tiempos de submilisegundos para una tarea única ...

Para poner las cosas un poco en perspectiva, aquí están los tiempos de C ++ para tamizar hasta 100,000,000:

 deque vs simple: 1895.521 ms vs 432.763 ms deque vs simple: 1847.594 ms vs 429.766 ms deque vs simple: 1859.462 ms vs 430.625 ms 

Por el contrario, un tamiz segmentado en C # con unas cuantas campanas y silbatos realiza el mismo trabajo en 95 ms (no hay tiempos de C ++ disponibles, ya que en este momento codigo desafíos solo en C #).

Las cosas pueden parecer decididamente diferentes en un lenguaje interpretado como Python, donde cada operación tiene un costo elevado y la sobrecarga del intérprete empequeñece todas las diferencias debido a twigs predecidas o mal predichas o operaciones de subciclo (cambio, sum) vs. operaciones de ciclo múltiple (multiplicación , y tal vez incluso división). Eso va a erosionar la ventaja de simplicidad de Sieve of Eratosthenes, y esto podría hacer que la solución deque sea un poco más atractiva.

Además, muchos de los tiempos registrados por otros encuestados en este tema probablemente estén dominados por el tiempo de salida . Esa es una guerra completamente diferente, donde mi arma principal es una clase simple como esta:

 class CCWriter { const int SPACE_RESERVE = 11; // UInt31 + '\n' public static System.IO.Stream BaseStream; static byte[] m_buffer = new byte[1 << 16]; // need 55k..60k for a maximum-size range static int m_write_pos = 0; public static long BytesWritten = 0; // for statistics internal static ushort[] m_double_digit_lookup = create_double_digit_lookup(); internal static ushort[] create_double_digit_lookup () { var lookup = new ushort[100]; for (int lo = 0; lo < 10; ++lo) for (int hi = 0; hi < 10; ++hi) lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo); return lookup; } public static void Flush () { if (BaseStream != null && m_write_pos > 0) BaseStream.Write(m_buffer, 0, m_write_pos); BytesWritten += m_write_pos; m_write_pos = 0; } public static void WriteLine () { if (m_buffer.Length - m_write_pos < 1) Flush(); m_buffer[m_write_pos++] = (byte)'\n'; } public static void WriteLinesSorted (int[] values, int count) { int digits = 1, max_value = 9; for (int i = 0; i < count; ++i) { int x = values[i]; if (m_buffer.Length - m_write_pos < SPACE_RESERVE) Flush(); while (x > max_value) if (++digits < 10) max_value = max_value * 10 + 9; else max_value = int.MaxValue; int n = x, p = m_write_pos + digits, e = p + 1; m_buffer[p] = (byte)'\n'; while (n >= 10) { int q = n / 100, w = m_double_digit_lookup[n - q * 100]; n = q; m_buffer[--p] = (byte)w; m_buffer[--p] = (byte)(w >> 8); } if (n != 0 || x == 0) m_buffer[--p] = (byte)((byte)'0' + n); m_write_pos = e; } } } 

Eso lleva menos de 1 ms para escribir 10000 (ordenados) números. Es una clase estática porque está destinada a la inclusión textual en la presentación de pruebas de encoding, con un mínimo de esfuerzo y cero gastos generales.

En general, encontré que es mucho más rápido si el trabajo enfocado se realiza en lotes enteros, es decir, tamizar un cierto rango, luego extraer todos los primos en un vector / matriz, luego expulsar todo el conjunto, luego tamizar el siguiente rango y así sucesivamente, en lugar de mezclar todo junto Tener funciones separadas enfocadas en tareas específicas también hace que sea más fácil mezclar y combinar, permite la reutilización y facilita el desarrollo / prueba.

Aquí está mi código VB 2008, que encuentra todos los números primos <10,000,000 en 1 minuto y 27 segundos en mi computadora portátil de trabajo. Se saltea números pares y solo busca números primos que sean

 Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click Dim TestNum As Integer Dim X As Integer Dim Z As Integer Dim TM As Single Dim TS As Single Dim TMS As Single Dim UnPrime As Boolean Dim Sentinal As Integer Button1.Text = "Thinking" Button1.Refresh() Sentinal = Val(SentinalTxt.Text) UnPrime = True Primes(0) = 2 Primes(1) = 3 Z = 1 TM = TimeOfDay.Minute TS = TimeOfDay.Second TMS = TimeOfDay.Millisecond For TestNum = 5 To Sentinal Step 2 Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then UnPrime = False End If X = X + 1 Loop If UnPrime = True Then X = X + 1 Z = Z + 1 Primes(Z) = TestNum End If UnPrime = True X = 0 Next Button1.Text = "Finished with " & Z TM = TimeOfDay.Minute - TM TS = TimeOfDay.Second - TS TMS = TimeOfDay.Millisecond - TMS ShowTime.Text = TM & ":" & TS & ":" & TMS End Sub 

El siguiente código de Mathcad calculó el primer millón de números primos en menos de 3 minutos.

Tenga en cuenta que esto usaría dobles de coma flotante para todos los números y básicamente se interpreta. Espero que la syntax sea clara.

enter image description here

Aquí hay una solución de C ++, usando una forma de SoE:

 #include  #include  typedef std::deque mydeque; void my_insert( mydeque & factors, int factor ) { int where = factor, count = factors.size(); while( where < count && factors[where] ) where += factor; if( where >= count ) factors.resize( where + 1 ); factors[ where ] = factor; } int main() { mydeque primes; mydeque factors; int a_prime = 3, a_square_prime = 9, maybe_prime = 3; int cnt = 2; factors.resize(3); std::cout << "2 3 "; while( cnt < 10000 ) { int factor = factors.front(); maybe_prime += 2; if( factor ) { my_insert( factors, factor ); } else if( maybe_prime < a_square_prime ) { std::cout << maybe_prime << " "; primes.push_back( maybe_prime ); ++cnt; } else { my_insert( factors, a_prime ); a_prime = primes.front(); primes.pop_front(); a_square_prime = a_prime * a_prime; } factors.pop_front(); } std::cout << std::endl; return 0; } 

Tenga en cuenta que esta versión de Sieve puede calcular números primos indefinidamente.

También tenga en cuenta que el deque STL toma O(1) tiempo para realizar push_back , pop_front y acceso aleatorio a través de subíndices.

La operación de cambio de resize toma O(n) tiempo, donde n es la cantidad de elementos que se agregan. Debido a cómo estamos usando esta función, podemos tratar esto como una pequeña constante.

El cuerpo del ciclo while en my_insert se ejecuta O(log log n) veces, donde n es igual a la variable maybe_prime . Esto se debe a que la expresión de condición del while se evaluará como verdadera una vez para cada factor principal de maybe_prime . Ver " Función de divisor " en Wikipedia.

Al multiplicar por el número de veces que se llama my_insert , se muestra que debe tomar O(n log log n) time para enumerar n primos ... lo cual es, como era de esperar, la complejidad de tiempo que se supone que tiene Sieve of Eratosthenes.

Sin embargo, aunque este código es eficiente, no es el más eficiente ... Sugeriría usar una biblioteca especializada para la generación de primos, como primesieve . Cualquier solución verdaderamente eficiente y bien optimizada requerirá más código de lo que cualquiera quiera escribir en Stackoverflow.

Utilizando Sieve of Eratosthenes, el cálculo es bastante más rápido que el algoritmo de números primos “conocidos”.

Al usar pseudocódigo en su wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), puedo tener la solución en C #.

 /// Get non-negative prime numbers until n using Sieve of Eratosthenes. public int[] GetPrimes(int n) { if (n <= 1) { return new int[] { }; } var mark = new bool[n]; for(var i = 2; i < n; i++) { mark[i] = true; } for (var i = 2; i < Math.Sqrt(n); i++) { if (mark[i]) { for (var j = (i * i); j < n; j += i) { mark[j] = false; } } } var primes = new List(); for(var i = 3; i < n; i++) { if (mark[i]) { primes.Add(i); } } return primes.ToArray(); } 

GetPrimes(100000000) takes 2s and 330ms.

NOTE : Value might vary depend on Hardware Specifications.

I spend some time writing a program calculating a lot of primes and this is the code I’m used to calculate a text file containing the first 1.000.000.000 primes. It’s in German, but the interesting part is the method calcPrimes() . The primes are stored in an array called Primzahlen. I recommend a 64bit CPU because the calculations are with 64bit integers.

 import java.io.*; class Primzahlengenerator { long[] Primzahlen; int LastUnknown = 2; public static void main(String[] args) { Primzahlengenerator Generator = new Primzahlengenerator(); switch(args.length) { case 0: //Wenn keine Argumente übergeben worden: Generator.printHelp(); //Hilfe ausgeben return; //Durchfallen verhindern case 1: try { Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()]; } catch (NumberFormatException e) { System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort zB \"Tausend\", sondern in Ziffern zB \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben Generator.printHelp(); //Generelle Hilfe ausgeben return; } break;//dutchfallen verhindern case 2: switch (args[1]) { case "-l": System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben Generator.printHelp(); //Generelle Hilfe ausgeben return; } break;//durchfallen verhindern case 3: try { Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()]; } catch (NumberFormatException e) { System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort zB \"Tausend\", sondern in Ziffern zB \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben Generator.printHelp(); //Generelle Hilfe ausgeben return; } switch(args[1]) { case "-l": Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist break; default: Generator.printHelp(); break; } break; default: Generator.printHelp(); return; } Generator.calcPrims(); } void printHelp() { System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen."); //Anleitung wie man das Programm mit Argumenten füttern muss System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,"); System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht."); } void loadFromFile(String File) { // System.out.println("Lese Datei namens: \"" + File + "\""); try{ int x = 0; BufferedReader in = new BufferedReader(new FileReader(File)); String line; while((line = in.readLine()) != null) { Primzahlen[x] = new Long(line).longValue(); x++; } LastUnknown = x; } catch(FileNotFoundException ex) { System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an."); } catch(IOException ex) { System.err.println(ex); } catch(ArrayIndexOutOfBoundsException ex) { System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,"); System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können."); } /* for(long prim : Primzahlen) { System.out.println("" + prim); } */ //Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden: //java Primzahlengenerator 1000 > 1000Primzahlen.txt //da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue(); //erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter. //falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal: //int[] foo = { 1, 2, 3}; //int bar = foo[4]; //dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht. } void calcPrims() { int PrimzahlNummer = LastUnknown; // System.out.println("LAstUnknown ist: " + LastUnknown); Primzahlen[0] = 2; Primzahlen[1] = 3; long AktuelleZahl = Primzahlen[PrimzahlNummer - 1]; boolean IstPrimzahl; // System.out.println("2"); // System.out.println("3"); int Limit = Primzahlen.length; while(PrimzahlNummer < Limit) { IstPrimzahl = true; double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl); for(int i = 1;i < PrimzahlNummer;i++) { if(AktuelleZahl % Primzahlen[i] == 0) { IstPrimzahl = false; break; } if(Primzahlen[i] > WurzelDerAktuellenZahl) break; } if(IstPrimzahl) { Primzahlen[PrimzahlNummer] = AktuelleZahl; PrimzahlNummer++; // System.out.println("" + AktuelleZahl); } AktuelleZahl = AktuelleZahl + 2; } for(long prim : Primzahlen) { System.out.println("" + prim); } } } 

I have written this using python, as I just started learning it, and it works perfectly fine. The 10,000th prime generate by this code as same as mentioned in http://primes.utm.edu/lists/small/10000.txt . To check if n is prime or not, divide n by the numbers from 2 to sqrt(n) . If any of this range of number perfectly divides n then it’s not prime.

 import math print ("You want prime till which number??") a = input() a = int(a) x = 0 x = int(x) count = 1 print("2 is prime number") for c in range(3,a+1): b = math.sqrt(c) b = int(b) x = 0 for b in range(2,b+1): e = c % b e = int(e) if (e == 0): x = x+1 if (x == 0): print("%d is prime number" % c) count = count + 1 print("Total number of prime till %d is %d" % (a,count)) 

I have been working on find primes for about a year. This is what I found to be the fastest:

 import static java.lang.Math.sqrt; import java.io.PrintWriter; import java.io.File; public class finder { public static void main(String[] args) { primelist primes = new primelist(); primes.insert(3); primes.insert(5); File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt"); file.getParentFile().mkdirs(); long time = System.nanoTime(); try{ PrintWriter printWriter = new PrintWriter ("file0024.txt"); int linenum = 0; printWriter.print("2"); printWriter.print (" , "); printWriter.print("3"); printWriter.print (" , "); int up; int down; for(int i =1; i<357913941;i++){// if(linenum%10000==0){ printWriter.println (""); linenum++; } down = i*6-1; if(primes.check(down)){ primes.insert(down); //System.out.println(i*6-1); printWriter.print ( down ); printWriter.print (" , "); linenum++; } up = i*6+1; if(primes.check(up)){ primes.insert(up); //System.out.println(i*6+1); printWriter.print ( up ); printWriter.print (" , "); linenum++; } } printWriter.println ("Time to execute"); printWriter.println (System.nanoTime()-time); //System.out.println(primes.length); printWriter.close (); }catch(Exception e){} } } class node{ node next; int x; public node (){ node next; x = 3; } public node(int z) { node next; x = z; } } class primelist{ node first; int length =0; node current; public void insert(int x){ node y = new node(x); if(current == null){ current = y; first = y; }else{ current.next = y; current = y; } length++; } public boolean check(int x){ int p = (int)sqrt(x); node y = first; for(int i = 0;ip){ return true; }else if(x%yx ==0){ return false; } y = y.next; } return true; } } 

1902465190909 nano seconds to get to 2147483629 starting at 2.

Here is my code which finds first 10,000 primes in 0.049655 sec on my laptop, first 1,000,000 primes in under 6 seconds and first 2,000,000 in 15 seconds
A little explanation. This method uses 2 techniques to find prime number

  1. first of all any non-prime number is a composite of multiples of prime numbers so this code test by dividing the test number by smaller prime numbers instead of any number, this decreases calculation by atleast 10 times for a 4 digit number and even more for a bigger number
  2. secondly besides dividing by prime, it only divides by prime numbers that are smaller or equal to the root of the number being tested further reducing the calculations greatly, this works because any number that is greater than root of the number will have a counterpart number that has to be smaller than root of the number but since we have tested all numbers smaller than the root already, Therefore we don’t need to bother with number greater than the root of the number being tested.

Sample output for first 10,000 prime number
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Here is the code in C language, Enter 1 and then 10,000 to print out the first 10,000 primes.
Edit: I forgot this contains math library ,if you are on windows or visual studio than that should be fine but on linux you must compile the code using -lm argument or the code may not work
Example: gcc -Wall -o “%e” “%f” -lm

 #include  #include  #include  #include  /* Finding prime numbers */ int main() { //pre-phase char d,w; int l,o; printf(" 1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value ie l or o printf(" Enter 1 or 2 to get anwser of first or second question\n"); // decision making do { printf(" -->"); scanf("%c",&d); while ((w=getchar()) != '\n' && w != EOF); if ( d == '1') { printf("\n 2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n -->"); scanf("%10d",&l); o=INT_MAX; printf(" Here we go!\n\n"); break; } else if ( d == '2' ) { printf("\n 2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n -->"); scanf("%10d",&o); l=o/log(o)*1.25; printf(" Here we go!\n\n"); break; } else printf("\n Try again\n"); }while ( d != '1' || d != '2' ); clock_t start, end; double cpu_time_used; start = clock(); /* starting the clock for time keeping */ // main program starts here int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */ int s,x; int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */ p[1]=2; p[2]=3; p[3]=5; printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */ p[i]=0; n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */ s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/ x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */ /* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */ // the main loop begins here for ( m=4,j=1,c=2; m<=l && n <= o;) /* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */ { // this will divide n by prime number in p[j] and tries to rule out non-primes if ( n%p[j]==0 ) { /* these steps execute if the number n is found to be non-prime */ ++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */ s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */ if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */ { x=p[c]; ++c; } j=1; /* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */ continue; /* and this restarts the loop for the new cycle */ } // confirmation test for the prime number candidate n else if ( n%p[j]!=0 && p[j]==x ) { /* these steps execute if the number is found to be prime */ p[m]=n; printf("%10dth:%10d\n",m,p[m]); ++n; s = sqrt(n); ++m; j=1; /* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */ continue; /* and this restarts the loop */ /* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/ } ++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */ // if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number // and therfore it will test the same number 'n' again in the next cycle with a bigger prime number } // the loops ends printf(" All done !!\n"); end = clock(); cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; printf(" Time taken : %lf sec\n",cpu_time_used); } 

Here the code that I made :


 enter code here #include  #include  #include  #include  #include  using namespace std; int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT*/ unsigned long int n; int prime(unsigned long int); scanf("%ld",&n); unsigned long int val; for(unsigned long int i=0;i 

Using the Array.prototype.find() method in Javascript. 2214.486 ms

 function isPrime (number) { function prime(element) { let start = 2; while (start <= Math.sqrt(element)) { if (element % start++ < 1) { return false; } } return element > 1; } return [number].find(prime) } function logPrimes (n) { let count = 0 let nth = n let i = 0 while (count < nth) { if (isPrime(i)) { count++ console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms if (count === nth) { console.log('while i', i) console.log('count', count) } } i++ } } console.time(logPrimes) logPrimes(10000) console.timeEnd(logPrimes) // 2214.486ms 

I can give you some tips, you have to implement it.

  1. For each number, get the half of that number. Eg for checking 21, only obtain the remainder by dividing it from range 2-10.
  2. If its an odd number, only divide by odd number, and vice versa. Such as for 21, divide with 3, 5, 7, 9 only.

Most efficient method I got up to so far.

 using System; namespace ConsoleApplication2 { class Program { static void Main(string[] args) { int n, i = 3, j, c; Console.WriteLine("Please enter your integer: "); n = Convert.ToInt32(Console.ReadLine()); if (n >= 1) { Console.WriteLine("First " + n + " Prime Numbers are"); Console.WriteLine("2"); } for(j=2;j<=n;) { for(c=2;c<=i-1;c++) { if(i%c==0) break; } if(c==i) { Console.WriteLine(i); j++; } i++; } Console.Read(); } } }