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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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?