10 votos

La mayor suma de números primos consecutivos que se suman a un primer menos de 1.000.000

En el Proyecto de Euler problema $50,$ el objetivo es encontrar el más largo de la suma de números primos consecutivos que añadir a un primer menos de $1,000,000. $

Tengo un algoritmo eficiente para generar un conjunto de números primos entre $0$ $N.$

Mi primer algoritmo para tratar esta era la fuerza bruta, pero eso era imposible. Yo intenté crear una ventana corrediza, pero tomó mucho tiempo para empezar a cubrir el espacio del problema.

Tengo algunos primos que fueron resumidos por $100$+ consecutivos de los números primos, pero sólo había de correr $5$-$10$% el problema de espacio.

Soy autodidacta, con muy poca educación post-secundaria.

Donde puedo leer o encontrar acerca de un algoritmo para la eficiente el cálculo de estos números primos consecutivos?

No estoy buscando una respuesta, pero, de hecho, más de punteros en cuanto a lo que debe buscar y aprender sobre el fin de resolver esto a mí mismo.

4voto

Matthew Scouten Puntos 2518

La suma de los primos primero 536 es $958577$ que es primo. La suma de los primos primero 547 es $1001604$. Sale de un pequeño número de posibilidades para comprobar.

4voto

Mike Puntos 1113

A la carne hacia fuera un Comentario: la clave para acelerar este problema es que mediante el uso de $O(n)$ espacio, se pueden calcular las sumas intermedias en constante tiempo: $S_{m,n} = S_{1,n}-S_{1,(m-1)}$, para almacenar las sumas parciales de $1$ $i$ permite todas las sumas parciales ser computado fácilmente. Esto elimina un factor de $O(n)$ del tiempo en marcha y hace el problema mucho más manejable.

3voto

Robert Mastragostino Puntos 10105

Pequeña velocidad sugerencia: el primer claramente va a ser raro, así que usted puede descartar aproximadamente la mitad del potencial suma de esa manera.

Si usted está buscando el más grande tal suma, comprobar cosas como $2+3,5+7+11,\cdots$ es una pérdida de tiempo. Estructura diferente para que gastas todo tu tiempo ocuparse de cantidades mayores. Usted no necesita la mayoría del espacio de problema.

Esperemos que esto no es demasiado de una respuesta para usted.

1voto

fsmart Puntos 550

He utilizado el código de mathematica:

list = {};
Do[
 a = Sum[Prime[i], {i, k, j}];
 If[900000 < a <= 1000000 && PrimeQ[a],
  AppendTo[list, {k, j, a}]],
 {k, 1, 1000}, {j, 1, 1000}]

y, a continuación,.

Sort[list, #1[[3]] < #2[[3]] &].

Esto parece muy ineficiente, pero fue bastante rápido. He encontrado que entre las secuencias de los primeros 1000 números primos, el más grande de primer suma fue de 459 a 695, con un valor de 999749. Esto es probablemente lo que usted está buscando, ya que realmente no considerar que mathematica es la programación.

Por cierto, sería interesante preguntar cómo muchas maneras en que un número puede ser resumida como la suma de números primos consecutivos?

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X