Generador de números primos, cómo hacer

Question

¿Alguien puede señalarme un algoritmo para generar números primos? Conozco algunos (Mersenne, Euclides, etc.) pero no generan muchos primos ...

El objetivo es: dado un primer primo, genera los 'n' siguientes primos. Pero gracias por el enlace ;-)

 for example : primes( 17, 50 ) -> Generate 50 consecutive primes starting at 17
 

y no falle ningún primo en este 50 ... ¡sin agujeros!

Answer 1

"El objetivo es: dado un primer prime, generar la $n$ el próximo de los números primos."

Esto es equivalente a que, "dado un número entero $N$, encontrar los primos más pequeños que exceda $N$."

La gente hace esto todo el tiempo, por ejemplo, aquí es una tabulación de los primos más pequeños que exceda $10^m$ para los distintos valores de $m$. Pero no especialmente inteligente manera de hacerlo. En efecto, al $N+1,N+2,N+3,\dots$ hasta encontrar un alojamiento. Usted puede ahorrar algo de trabajo por tamizado, pero usted ya lo sabe. Si usted quiere encontrar, digamos, los primeros 50 números primos después de $10^{100}$, no hay duda de que iba a ahorrar un montón de trabajo por hacer algunos de cribado, pero en la final, habría un montón de números que conseguir a través de la criba, y usted tendría que caer de nuevo en el estándar de pruebas de primalidad para ver cuáles son realmente privilegiada.

Supongo que la otra cosa que puedes hacer es usar el Primer Número de el Teorema de estimación de la distancia al tamiz para tener una buena oportunidad de la captura de los próximos 50 números primos. A grandes rasgos, un número en cada $\log N$ va a ser la mejor, así que si usted sale a $N+100\log N$ usted debe tener una oportunidad excelente de la captura de los próximos 50 números primos.

Answer 2

El teorema fundamental de la aritmética como una recurrencia da todos los números primos. Pero, por supuesto, se trata de un montón de 1:s que no son primos, y también es un 2-dimensiones de la matriz.

La recurrencia en el Europeo de punto coma inglés Excel para ser introducido en la celda A1, es:

=IF(COLUMN()=1;1;IF(ROW()=COLUMN();ROW()/PRODUCT(INDIRECT(ADDRESS(ROW();1)
&":"&ADDRESS(ROW();COLUMN()-1)));IF(ROW()>COLUMN();INDIRECT(ADDRESS(ROW()
-COLUMN();COLUMN()));"")))

que las salidas:

donde la secuencia en la diagonal es la exponentiated von Mangoldt función.

---

Editar 29.3.2013: Una más de Riemann zeta función de mesa se puede hacer con la recurrencia:

=IF(ROW()>=COLUMN();IF(AND(ROW()=1;COLUMN()=1);1;IF(COLUMN()=1;
ROW()/PRODUCT(INDIRECT(ADDRESS(ROW();2)&":"&ADDRESS(ROW();ROW())));
IF(MOD(ROW();COLUMN())=0;INDIRECT(ADDRESS(FLOOR(ROW()/COLUMN();1);
1));"")));"")

que las salidas:

donde de nuevo la exponentiated von Mangoldt función se encuentra en la primera columna. Sin embargo, esta segunda repetición se utiliza la función del suelo.

Answer 3

Aquí hay un documento que contiene una recurrencia principal definida por

ps

donde$$a_{n+1} = a_n + gcd(n,a_{n-1}),$ es la mayor función de divisor común.

Una de mis favoritas está dada por el teorema de Mills , pero dado que no podemos calcular el número directamente (¿aún ...?), No es factible generar primos con él.

Answer 4

Cuando usted ha mencionado los números primos, pensé que le gustaría bastante grandes números primos. El pensamiento de aplicaciones en ciencias de la computación, pensé que la criptografía daría una respuesta, especialmente RSA que utiliza números primos grandes.

De hecho, el crypto.SE tenía la siguiente pregunta que creo que soluciona el problema: http://crypto.stackexchange.com/questions/71/how-can-i-generate-large-prime-numbers-for-rsa

Editar:

Como usted ha mencionado, usted está interesado en la generación de la n más pequeño de los números primos que son mayores que un cierto número. Hay algunas maneras de hacer que, aunque no puedo juzgar la eficiencia de cómputo (algunos requieren un conocimiento de todos los números primos que son menores que el que se está buscando). Sugiero consultar el excelente artículo en la wikipedia http://en.wikipedia.org/wiki/Formula_for_primes , así como la relacionada con los enlaces y referencias.

Answer 5

Aquí usted ir - dar cualquier número aleatorio como una entrada, y se le dará el siguiente primo después de ella. Usted puede alimentar a su salida en sí mismo para hacer una lista. Básicamente usa de Fermat Poco Teorema de forma heurística para comprobar si cada número es un número primo, y mantiene la comprobación de los sucesivos números impares hasta llegar a algo que funciona.

Tiene una muy pequeña probabilidad de fracaso (por ejemplo. comandos nextprime(560) = 561, pero 561=3*11*17), pero si vas lo suficientemente alta como este se vuelve despreciable en la práctica.

def modexp(b,e,n):
  if e == 0: return 1
  elif e%2 == 0: return modexp(b,e/2,n)**2 % n
  else: return b*modexp(b,e/2,n)**2 % n

def nextprime(inp):
  inp += inp%2 + 1
  while modexp(2,inp,inp) != 2 or modexp(3,inp,inp) != 3: inp += 2
  return inp