Let \(N = 10^6\). Among all primes below \(N\), we want the one that can be written as the sum of the longest block of consecutive primes. If \(q_0 = 2, q_1 = 3, q_2 = 5, \dots\) are the primes in increasing order, then the task is to maximize the length \(L = j - i\) of a block
$$q_i + q_{i+1} + \cdots + q_{j-1}$$
subject to the sum itself being prime and still satisfying \(q_i + \cdots + q_{j-1} \lt N\).
The built-in checkpoint examples in the implementations are the standard ones: below \(100\), the winner is \(41 = 2 + 3 + 5 + 7 + 11 + 13\); below \(1000\), the winner is \(953\), obtained from \(21\) consecutive primes. The million-case is the same search problem on a larger range, so the main challenge is not exotic number theory but an efficient way to scan all relevant consecutive-prime intervals.
The prime list is ordered, and every term is positive. Those two facts are enough to turn the naive search into a manageable interval problem.
Define the prefix totals
$$P_0 = 0,\qquad P_m = \sum_{t=0}^{m-1} q_t \quad (m \ge 1).$$
Then every block of consecutive primes has the closed form
$$S(i,j) = q_i + q_{i+1} + \cdots + q_{j-1} = P_j - P_i,$$
where \(0 \le i \lt j\), and the length of the block is \(L = j - i\). This is the central mathematical object in the solution: instead of recomputing a sum term by term, each candidate interval is represented by two endpoints and evaluated by a single subtraction.
For a fixed start index \(i\), the values
$$S(i,i+1),\ S(i,i+2),\ S(i,i+3),\ \dots$$
are strictly increasing, because every step adds another positive prime. Therefore, once some end index \(j\) gives \(S(i,j) \ge N\), every later end index \(j' \gt j\) is impossible as well. No later window with the same start can come back below the bound.
This monotonicity is what justifies the early break in the search. It is not merely an optimization trick; it is a direct consequence of the fact that all primes are positive.
Suppose the best chain found so far has length \(B\). Any new interval with length at most \(B\) cannot improve the answer, even if its sum is prime, because the problem asks for the longest chain. So for a fixed start \(i\), the search only needs to consider end indices \(j\) with
$$j - i \ge B + 1.$$
Equivalently, the first relevant end index is \(j = i + B + 1\). Whenever a prime-valued interval is discovered, \(B\) is updated to that larger length, and the lower bound for all future searches becomes stricter. This is the main invariant encoded by the implementations.
Notice that this is slightly different from a brute-force "test every length from longest to shortest" strategy. The code keeps a moving threshold for admissible lengths and examines only intervals that could still set a new record.
Take any interval \((i,j)\) that could possibly be the first interval of some new record length. When the outer scan reaches the start index \(i\), the current record length \(B\) must satisfy \(B \lt j - i\); otherwise the interval would not improve anything. That means \(j\) lies inside the inner loop's search range, which begins at \(i + B + 1\).
Since the inner loop then increases \(j\) one step at a time until the sum reaches the limit, every potentially record-setting interval is examined exactly once. The algorithm therefore performs a complete search over all intervals that can still matter and discards only intervals that are mathematically incapable of beating the current record.
With \(q_0 = 2, q_1 = 3, q_2 = 5, q_3 = 7, \dots\), the \(21\)-term block
$$7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953$$
starts at \(q_3\) and ends at \(q_{23}\). In prefix-sum notation this is simply
$$S(3,24) = P_{24} - P_3 = 953.$$
The checkpoint confirms that below \(1000\) no longer consecutive-prime block gives a prime. This example shows the whole method in miniature: represent the block by its endpoints, compute the value through a prefix difference, and compare the resulting length with the current best record.
The C++, Python, and Java implementations first build a sieve up to \(N - 1\). That one table serves two purposes at once: it generates the ordered list of primes and it answers primality queries for candidate sums in constant time.
Next, the implementation constructs the prefix array \(P\). The running totals are stored in integer types wide enough to hold cumulative sums larger than the final answer bound, because prefix totals keep growing even after individual candidate windows have already exceeded \(N\).
The main search keeps two pieces of state: the best prime found so far and the best length \(B\). For each start index \(i\), the end index begins at \(i + B + 1\), so intervals that are already too short are skipped completely. Each candidate sum is computed as \(P_j - P_i\). If that value reaches the limit, the scan for that start stops immediately; if it is prime, the stored best length and best prime are updated on the spot.
The implementations also contain two sanity checkpoints, namely \(41\) for limit \(100\) and \(953\) for limit \(1000\). These checks are useful because they verify that the sieve, the prefix sums, and the record-tracking invariant all agree before the million-scale computation is run.
Building the sieve costs \(O(N \log \log N)\) time and \(O(N)\) space. Extracting the prime list and constructing the prefix totals add \(O(\pi(N))\) time and space, where \(\pi(N)\) is the prime-counting function.
In the worst case, the interval search is \(O(\pi(N)^2)\), because it is a nested scan over start and end positions in the prime list. In practice it is far better than naive quadratic work for two reasons: the sum for a fixed start grows monotonically and triggers an early break, and the current record length eliminates every interval that is too short to matter.
Sei \(N = 10^6\). Unter allen Primzahlen kleiner als \(N\) wird diejenige gesucht, die sich als Summe des laengsten Blocks aufeinanderfolgender Primzahlen schreiben laesst. Sind \(q_0 = 2, q_1 = 3, q_2 = 5, \dots\) die Primzahlen in aufsteigender Reihenfolge, dann soll die Laenge \(L = j - i\) des Blocks
$$q_i + q_{i+1} + \cdots + q_{j-1}$$
maximiert werden, wobei die Summe selbst wieder prim sein und zugleich \( \lt N\) bleiben muss.
Die in den Implementierungen eingebauten Kontrollpunkte sind die bekannten Beispiele: unter \(100\) gewinnt \(41 = 2 + 3 + 5 + 7 + 11 + 13\); unter \(1000\) gewinnt \(953\) als Summe von \(21\) aufeinanderfolgenden Primzahlen. Im Fall der Grenze \(10^6\) ist also nicht neue Zahlentheorie gefragt, sondern eine effiziente Suche durch alle relevanten Intervalle der Primzahlfolge.
Die Primzahlliste ist geordnet, und jeder Eintrag ist positiv. Genau diese beiden Tatsachen genuegen, um die naive Suche in ein kontrollierbares Intervallproblem umzuwandeln.
Definiere die Praefixsummen durch
$$P_0 = 0,\qquad P_m = \sum_{t=0}^{m-1} q_t \quad (m \ge 1).$$
Dann hat jeder Block aufeinanderfolgender Primzahlen die Form
$$S(i,j) = q_i + q_{i+1} + \cdots + q_{j-1} = P_j - P_i,$$
wobei \(0 \le i \lt j\) gilt und die Blocklaenge \(L = j - i\) ist. Das ist das zentrale mathematische Objekt der Loesung: Jeder Kandidat wird nur noch durch zwei Endpunkte beschrieben und mit einer einzigen Subtraktion ausgewertet.
Fuer festen Startindex \(i\) sind die Werte
$$S(i,i+1),\ S(i,i+2),\ S(i,i+3),\ \dots$$
streng wachsend, weil bei jedem Schritt eine weitere positive Primzahl addiert wird. Sobald also fuer ein Ende \(j\) gilt \(S(i,j) \ge N\), ist auch jedes spaetere Ende \(j' \gt j\) unmoeglich. Kein spaeteres Fenster mit demselben Start kann wieder unter die Schranke fallen.
Diese Monotonie rechtfertigt das sofortige Abbrechen der inneren Schleife. Sie ist nicht bloss ein Programmiertrick, sondern folgt direkt aus der Positivitaet der Summanden.
Angenommen, die bisher beste gefundene Kette hat Laenge \(B\). Dann kann ein neues Intervall die Antwort nur verbessern, wenn seine Laenge mindestens \(B+1\) betraegt. Fuer festen Start \(i\) muessen also nur Endpunkte \(j\) mit
$$j - i \ge B + 1$$
untersucht werden. Der erste ueberhaupt sinnvolle Endpunkt ist somit \(j = i + B + 1\). Findet man ein primwertiges Intervall, wird \(B\) auf diese neue groessere Laenge angehoben, und fuer alle spaeteren Starts wird die Mindestlaenge automatisch schaerfer.
Genau diese Invariante tragen die Implementierungen aus. Sie testen nicht blind alle moeglichen Fenster, sondern nur noch diejenigen, die den aktuellen Rekord tatsaechlich schlagen koennen.
Nimm ein Intervall \((i,j)\), das theoretisch einen neuen Rekord setzen koennte. Wenn die aeussere Schleife den Start \(i\) erreicht, muss die aktuelle Rekordlaenge \(B\) strikt kleiner als \(j-i\) sein; sonst wuerde dieses Intervall nichts verbessern. Damit liegt \(j\) automatisch im Suchbereich der inneren Schleife, die bei \(i+B+1\) beginnt.
Da die innere Schleife den Endpunkt dann schrittweise vergroessert, bis die Summe die Schranke erreicht, wird jedes potentiell rekordsetzende Intervall genau einmal geprueft. Der Algorithmus ist also keine Heuristik, sondern eine vollstaendige Suche ueber alle noch relevanten Kandidaten.
Mit \(q_0 = 2, q_1 = 3, q_2 = 5, q_3 = 7, \dots\) ist der Block aus \(21\) aufeinanderfolgenden Primzahlen
$$7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953$$
der bei \(q_3\) beginnt und bei \(q_{23}\) endet. In Praefixschreibweise ist das schlicht
$$S(3,24) = P_{24} - P_3 = 953.$$
Der Kontrollpunkt besagt, dass es unter \(1000\) keinen laengeren Block aufeinanderfolgender Primzahlen mit primem Summenwert gibt. Das Beispiel zeigt die gesamte Methode im Kleinen: Endpunkte waehlen, Praefixdifferenz bilden, Laenge mit dem aktuellen Rekord vergleichen.
Die C++-, Python- und Java-Implementierungen bauen zuerst ein Sieb bis \(N - 1\) auf. Dieselbe Tabelle erfuellt danach zwei Aufgaben zugleich: Sie erzeugt die geordnete Primzahlliste und beantwortet Primzahltests fuer Kandidatensummen in konstanter Zeit.
Anschliessend wird das Praefixarray \(P\) aufgebaut. Die laufenden Summen werden in Datentypen gespeichert, die auch deutlich groessere Werte als die Endschranke tragen koennen, denn die Praefixsummen wachsen weiter, obwohl einzelne Kandidatenfenster schon laengst ueber \(N\) liegen.
Die eigentliche Suche speichert zwei Groessen: die bisher beste Primzahl und die dazugehoerige Rekordlaenge \(B\). Fuer jeden Startindex \(i\) beginnt der Endindex bei \(i + B + 1\), sodass alle zu kurzen Intervalle von vornherein uebersprungen werden. Jede Kandidatensumme wird als \(P_j - P_i\) berechnet. Erreicht dieser Wert die Schranke, stoppt die Suche fuer diesen Start sofort; ist er prim, werden Rekordlaenge und beste Primzahl unmittelbar aktualisiert.
Zusaetzlich enthalten die Implementierungen zwei Plausibilitaetspruefungen, naemlich \(41\) fuer die Grenze \(100\) und \(953\) fuer die Grenze \(1000\). Damit wird bestaetigt, dass Sieb, Praefixsummen und Rekordinvariante korrekt zusammenspielen, bevor der Millionenlauf gestartet wird.
Der Aufbau des Siebs kostet \(O(N \log \log N)\) Zeit und \(O(N)\) Speicher. Das Extrahieren der Primzahlen und das Bilden der Praefixsummen fuegen \(O(\pi(N))\) Zeit und Speicher hinzu, wobei \(\pi(N)\) die Primzahlzaehlfunktion bezeichnet.
Im schlechtesten Fall ist die Intervallsuche \(O(\pi(N)^2)\), weil sie als verschachtelte Suche ueber Start- und Endpositionen der Primzahlliste erscheint. Praktisch ist sie deutlich schneller als naive quadratische Arbeit: Fuer festen Start wachsen die Summen monoton und erlauben fruehes Abbrechen, und die aktuelle Rekordlaenge streicht jedes Intervall, das zu kurz ist, um noch relevant zu sein.
\(N = 10^6\) olsun. \(N\)'den kucuk asallar arasinda, en uzun ardisik asal blogunun toplami olarak yazilabilen asali ariyoruz. \(q_0 = 2, q_1 = 3, q_2 = 5, \dots\) asallari artan sirada gosterirse, amac
$$q_i + q_{i+1} + \cdots + q_{j-1}$$
toplaminin hem asal hem de \(N\)'den kucuk olmasi kosuluyla, blogun uzunlugu \(L = j - i\)'yi mumkun oldugunca buyutmektir.
Uygulamalardaki yerlesik kontrol ornekleri klasik sonuclardir: \(100\)'un altinda kazanan \(41 = 2 + 3 + 5 + 7 + 11 + 13\), \(1000\)'in altinda kazanan ise \(21\) ardısık asalin toplami olan \(953\)'tur. Dolayisiyla milyon sinirindaki asil mesele yeni bir sayi kurami fikri degil, ilgili tum ardısık asal araliklarini verimli bicimde taramaktir.
Asal listesi siralidir ve listedeki her terim pozitiftir. Naif aramayi yonetilebilir hale getiren sey tam olarak bu iki ozelliktir.
Prefix toplamlarini
$$P_0 = 0,\qquad P_m = \sum_{t=0}^{m-1} q_t \quad (m \ge 1)$$
seklinde tanimlayalim. O zaman her ardısık asal blogu
$$S(i,j) = q_i + q_{i+1} + \cdots + q_{j-1} = P_j - P_i$$
formuna iner; burada \(0 \le i \lt j\) ve blogun uzunlugu \(L = j - i\)'dir. Cozumin merkezindeki nesne budur: her aday toplam artik tek tek toplanmiyor, sadece iki uc noktanin farki olarak bulunuyor.
Sabit bir baslangic indisi \(i\) icin
$$S(i,i+1),\ S(i,i+2),\ S(i,i+3),\ \dots$$
degerleri kesin olarak artar; cunku her adimda bir pozitif asal daha eklenir. Bu nedenle bir \(j\) icin \(S(i,j) \ge N\) oldugu anda, ayni baslangicla daha buyuk her \(j' \gt j\) de imkansiz hale gelir. Ayni baslangictan gelen hicbir daha uzun pencere sinirin altina geri donemez.
Ic dongudeki erken cikis dogrudan bu monotonluga dayanir. Bu, yalnizca pratik bir hizlandirma degil, toplam terimlerinin pozitif olmasindan cikan matematiksel bir sonucudur.
Su ana kadar bulunan en iyi zincirin uzunlugu \(B\) olsun. Uzunlugu \(B\) ya da daha kisa olan hicbir yeni aralik cevabi iyilestiremez; cunku soru en uzun zinciri soruyor. Bu yuzden sabit bir \(i\) icin yalnizca
$$j - i \ge B + 1$$
kosulunu saglayan bitis indisleri anlamlidir. Yani ilk kontrol edilmesi gereken bitis \(j = i + B + 1\)'dir. Prime toplam veren daha uzun bir aralik bulundugunda \(B\) hemen guncellenir ve sonraki taramalar icin alt sinir daha da yukselir.
Uygulamalarin tasidigi asil degismez budur. Kod, tum mumkun pencereleri korlemesine denemez; sadece mevcut rekoru gercekten gecebilme ihtimali olan pencerelere bakar.
Diyelim \((i,j)\) araligi teorik olarak yeni bir rekor uzunluk uretebilecek bir aday olsun. Dis dongu baslangic \(i\)'ye geldiginde mevcut rekor uzunluk \(B\), mutlaka \(j-i\)'den kucuktur; aksi halde bu aralik zaten iyilestirme saglamazdi. Dolayisiyla \(j\), ic dongunun gercekten baktigi bolgenin icindedir; cunku ic dongu \(i + B + 1\)'den baslar.
Ic dongu bitis indisini limit asılana kadar birer birer buyuttugu icin, rekor kirma ihtimali olan her aralik tam bir kez incelenir. Yani algoritma sezgisel degil, hala anlamli olan tum adaylar uzerinde tam bir taramadir.
\(q_0 = 2, q_1 = 3, q_2 = 5, q_3 = 7, \dots\) yazimina gore \(21\) terimli su blok
$$7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953$$
\(q_3\)'te baslar ve \(q_{23}\)'te biter. Prefix notasyonunda bu sadece
$$S(3,24) = P_{24} - P_3 = 953$$
demektir. Kontrol sonucu, \(1000\)'in altinda bundan daha uzun bir ardısık asal blogunun asal toplam vermedigini soyluyor. Ornek, yontemin tamamini kucuk olcekte gosterir: uclari sec, prefix farkini al, uzunlugu mevcut rekorla karsilastir.
C++, Python ve Java uygulamalari once \(N - 1\)'e kadar bir elek kurar. Bu tek tablo ayni anda iki is yapar: artan asal listesini uretir ve aday toplamlar icin sabit zamanda asallik sorgusu cevaplar.
Daha sonra uygulama prefix dizisi \(P\)'yi olusturur. Kumulatif toplamlar, cevap sinirindan daha buyuk degerleri de tasiyabilecek tamsayi turlerinde tutulur; cunku prefix toplamlar, tek tek pencereler \(N\)'yi gecse bile buyumeye devam eder.
Ana arama iki durum bilgisi tasir: simdiye kadarki en iyi asal ve buna karsilik gelen en iyi uzunluk \(B\). Her baslangic indisi \(i\) icin bitis indisi \(i + B + 1\)'den baslar; boylece zaten yetersiz olan tum kisa pencereler tamamen atlanir. Her aday toplam \(P_j - P_i\) olarak hesaplanir. Bu deger limite ulasirsa o baslangic icin arama hemen biter; asal ise en iyi uzunluk ve en iyi asal o anda guncellenir.
Uygulamalarda ayrica iki saglama noktasi bulunur: limit \(100\) icin \(41\) ve limit \(1000\) icin \(953\). Bunlar, milyonluk kosudan once eleegin, prefix toplamlarin ve rekor takibi degismezinin birbiriyle uyumlu calistigini dogrular.
Elek kurma maliyeti \(O(N \log \log N)\) zaman ve \(O(N)\) bellektir. Asal listesini cikarmak ve prefix toplamlarini olusturmak buna ek olarak \(O(\pi(N))\) zaman ve bellek gerektirir; burada \(\pi(N)\) asal sayma fonksiyonudur.
En kotu durumda aralik taramasi \(O(\pi(N)^2)\) gorunur; cunku asal listesi uzerinde ic ice baslangic ve bitis taramasi yapilir. Pratikte ise naif karesel maliyetten belirgin bicimde iyidir: sabit baslangicta toplam monoton artar ve erken durma saglar, mevcut rekor uzunlugu da artik onemsiz olan tum kisa araliklari daha dogmadan eler.
Sea \(N = 10^6\). Entre todos los primos menores que \(N\), buscamos el que puede escribirse como suma del bloque mas largo de primos consecutivos. Si \(q_0 = 2, q_1 = 3, q_2 = 5, \dots\) denota los primos en orden creciente, entonces el objetivo es maximizar la longitud \(L = j - i\) del bloque
$$q_i + q_{i+1} + \cdots + q_{j-1}$$
bajo la condicion de que la suma siga siendo prima y ademas cumpla \(q_i + \cdots + q_{j-1} \lt N\).
Los puntos de control incorporados en las implementaciones son los ejemplos clasicos: por debajo de \(100\), el ganador es \(41 = 2 + 3 + 5 + 7 + 11 + 13\); por debajo de \(1000\), el ganador es \(953\), obtenido con \(21\) primos consecutivos. En la cota de un millon el problema es el mismo, solo que a mayor escala, de modo que la dificultad real es recorrer con eficiencia los intervalos consecutivos que todavia pueden importar.
La lista de primos esta ordenada y todos sus terminos son positivos. Esas dos propiedades bastan para convertir la busqueda ingenua en un problema de intervalos manejable.
Definimos las sumas prefijo por
$$P_0 = 0,\qquad P_m = \sum_{t=0}^{m-1} q_t \quad (m \ge 1).$$
Entonces cualquier bloque de primos consecutivos puede escribirse como
$$S(i,j) = q_i + q_{i+1} + \cdots + q_{j-1} = P_j - P_i,$$
con \(0 \le i \lt j\) y longitud \(L = j - i\). Este es el objeto matematico central de la solucion: cada candidato deja de ser una suma repetida y pasa a ser una resta entre dos extremos.
Para un inicio fijo \(i\), los valores
$$S(i,i+1),\ S(i,i+2),\ S(i,i+3),\ \dots$$
crecen estrictamente, porque cada paso agrega otro primo positivo. Por tanto, en cuanto algun extremo \(j\) produce \(S(i,j) \ge N\), cualquier extremo posterior \(j' \gt j\) queda descartado de inmediato. Ninguna ventana mas larga con el mismo inicio puede volver a quedar por debajo de la cota.
Esa monotonia justifica la ruptura anticipada del barrido interno. No es una heuristica casual; es una consecuencia directa de sumar solo cantidades positivas.
Supongamos que la mejor cadena encontrada hasta ahora tiene longitud \(B\). Cualquier intervalo nuevo de longitud menor o igual que \(B\) no puede mejorar la respuesta, aunque su suma sea prima, porque el problema pide la cadena mas larga. Asi, para un inicio fijo \(i\), solo merece la pena examinar extremos \(j\) que cumplan
$$j - i \ge B + 1.$$
En otras palabras, el primer extremo relevante es \(j = i + B + 1\). Cada vez que aparece una suma prima con una longitud mayor, \(B\) se actualiza y a partir de ese momento el umbral minimo para las siguientes ventanas se vuelve mas exigente.
Esa es exactamente la invariante que usan las implementaciones. El codigo no prueba ciegamente todas las ventanas; solo recorre las que todavia pueden establecer un nuevo record.
Tome cualquier intervalo \((i,j)\) que pudiera convertirse en el primer representante de una nueva longitud record. Cuando el barrido exterior llega al inicio \(i\), la mejor longitud actual \(B\) necesariamente satisface \(B \lt j - i\); de lo contrario, ese intervalo no mejoraria nada. Por eso \(j\) queda dentro del rango real que explora el bucle interior, que comienza en \(i + B + 1\).
Como el bucle interior incrementa \(j\) paso a paso hasta que la suma alcanza la cota, todo intervalo capaz de romper el record se examina exactamente una vez. El algoritmo no es una aproximacion: es una busqueda completa sobre todos los candidatos que aun pueden cambiar la respuesta.
Con \(q_0 = 2, q_1 = 3, q_2 = 5, q_3 = 7, \dots\), el bloque de \(21\) terminos
$$7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953$$
empieza en \(q_3\) y termina en \(q_{23}\). En notacion de prefijos, esto es simplemente
$$S(3,24) = P_{24} - P_3 = 953.$$
El punto de control confirma que por debajo de \(1000\) no existe un bloque mas largo de primos consecutivos cuya suma sea prima. El ejemplo resume todo el metodo: elegir extremos, calcular una diferencia de prefijos y comparar la longitud con el mejor registro conocido.
Las implementaciones en C++, Python y Java construyen primero un tamiz hasta \(N - 1\). Esa misma tabla sirve para dos tareas a la vez: generar la lista ordenada de primos y responder en tiempo constante si una suma candidata es prima.
Despues, la implementacion forma el arreglo de prefijos \(P\). Los acumulados se guardan en tipos enteros suficientemente amplios, porque las sumas prefijo siguen creciendo mucho mas alla de \(N\), aunque las ventanas individuales ya hayan rebasado la cota y dejen de ser candidatas.
La busqueda principal mantiene dos datos: el mejor primo encontrado y la mejor longitud \(B\). Para cada indice inicial \(i\), el indice final comienza en \(i + B + 1\), con lo cual se omiten de entrada todas las ventanas que ya son demasiado cortas. Cada suma candidata se calcula como \(P_j - P_i\). Si ese valor alcanza el limite, el barrido para ese inicio se detiene; si es primo, se actualizan inmediatamente la mejor longitud y el mejor primo.
Las implementaciones incluyen ademas dos comprobaciones de cordura: \(41\) para limite \(100\) y \(953\) para limite \(1000\). No forman parte de la teoria, pero son utiles para verificar que el tamiz, los prefijos y la invariante del record estan coordinados correctamente antes de ejecutar el caso grande.
Construir el tamiz cuesta \(O(N \log \log N)\) tiempo y \(O(N)\) espacio. Extraer la lista de primos y levantar los prefijos agrega \(O(\pi(N))\) tiempo y espacio, donde \(\pi(N)\) es la funcion contadora de primos.
En el peor caso, la busqueda por intervalos es \(O(\pi(N)^2)\), porque aparece como un barrido anidado sobre posiciones iniciales y finales en la lista de primos. En la practica es bastante mejor que una exploracion cuadratica ingenua: para cada inicio fijo, la suma crece de manera monotona y produce una ruptura temprana, y la mejor longitud actual elimina todas las ventanas demasiado cortas para ser relevantes.
设 \(N = 10^6\)。在所有小于 \(N\) 的素数中，我们要找出那个可以表示成最长一段连续素数之和的素数。记按从小到大排列的素数为 \(q_0 = 2, q_1 = 3, q_2 = 5, \dots\)，那么问题就是在满足和仍然是素数且
$$q_i + q_{i+1} + \cdots + q_{j-1} \lt N$$
的前提下，使连续区间
$$q_i + q_{i+1} + \cdots + q_{j-1}$$
的长度 \(L = j - i\) 尽可能大。
实现中自带的两个检查例子正是题目里最经典的结果：在 \(100\) 以下，最优值是 \(41 = 2 + 3 + 5 + 7 + 11 + 13\)；在 \(1000\) 以下，最优值是 \(953\)，它来自 \(21\) 个连续素数的和。到了 \(10^6\) 这一规模，问题本质并没有改变，真正需要解决的是如何高效地扫描所有仍然可能成为答案的连续素数区间。
素数表是有序的，而且每一项都是正数。正是这两个事实，使得原本看似暴力的枚举可以化为一个可控的区间问题。
定义前缀和
$$P_0 = 0,\qquad P_m = \sum_{t=0}^{m-1} q_t \quad (m \ge 1).$$
于是任意一段连续素数都可以写成
$$S(i,j) = q_i + q_{i+1} + \cdots + q_{j-1} = P_j - P_i,$$
其中 \(0 \le i \lt j\)，区间长度就是 \(L = j - i\)。这就是整个解法的核心数学对象。没有前缀和时，每个候选区间都要重新逐项相加；有了前缀和以后，候选值只需要做一次减法就能得到。
对固定起点 \(i\) 来说，序列
$$S(i,i+1),\ S(i,i+2),\ S(i,i+3),\ \dots$$
一定严格递增，因为每向右扩一位都会再加入一个正素数。因此，只要某个终点 \(j\) 已经使 \(S(i,j) \ge N\)，那么所有更大的终点 \(j' \gt j\) 都不可能再满足限制。对于同一个起点，不存在“先超过上界，后面又回到上界以下”的情况。
这就是内层扫描可以立刻停止的数学理由。它不是经验优化，而是由所有加数都为正这一事实直接推出的。
设当前已经找到的最长链长度为 \(B\)。那么任何长度不超过 \(B\) 的新区间，即使它的和是素数，也不可能改写答案，因为题目要求的是“最长”的连续素数和。所以对固定起点 \(i\)，只需要考虑满足
$$j - i \ge B + 1$$
的终点 \(j\)。换句话说，真正有意义的第一个终点就是 \(j = i + B + 1\)。一旦发现更长的素数区间，\(B\) 就立即更新，之后所有搜索的长度门槛也随之提高。
这正是实现里最重要的不变量。代码并不是机械地检查所有长度，而是始终只扫描那些仍有可能刷新纪录的区间。
考虑任意一个有可能成为新纪录的区间 \((i,j)\)。当外层扫描走到起点 \(i\) 时，当前最佳长度 \(B\) 必然满足 \(B \lt j - i\)，否则这个区间根本不可能改写纪录。因此，\(j\) 一定落在内层循环真正会枚举到的范围内，因为内层循环正是从 \(i + B + 1\) 开始向右推进。
而内层循环会一直把终点向右移动，直到区间和达到上界为止，所以每一个仍然可能创造新纪录的候选区间都会被检查且只会被检查一次。也就是说，这不是启发式近似，而是对所有仍然有价值的候选区间做了一次完整搜索。
按照 \(q_0 = 2, q_1 = 3, q_2 = 5, q_3 = 7, \dots\) 的编号方式，下面这一段 \(21\) 项连续素数满足
$$7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953.$$
这段区间从 \(q_3\) 开始，到 \(q_{23}\) 结束，所以在前缀和记号下只是
$$S(3,24) = P_{24} - P_3 = 953.$$
检查点说明，在 \(1000\) 以下，不存在更长的连续素数区间还能得到素数和。这个例子把整套思路完整地展示出来了：先用端点表示区间，再用前缀差求值，最后把区间长度与当前最佳纪录比较。
C++、Python 和 Java 实现都会先建立一个到 \(N - 1\) 为止的筛表。这张表同时承担两件事：一方面生成递增的素数序列，另一方面为每个候选区间和提供 \(O(1)\) 的素性查询。
接着，实现构造前缀数组 \(P\)。前缀累加值会保存在足够宽的整数类型里，因为虽然单个候选窗口一旦超过 \(N\) 就不再有资格成为答案，但前缀总和本身仍会继续增长。
主搜索阶段维护两个状态：当前找到的最佳素数，以及对应的最长长度 \(B\)。对每个起点 \(i\)，终点直接从 \(i + B + 1\) 开始，这样所有注定太短的窗口都会被完全跳过。每个候选值都按 \(P_j - P_i\) 计算。如果这个值达到上界，就立刻结束该起点的扫描；如果它是素数，就立即更新最佳长度和最佳素数。
实现里还包含两个自检点，也就是极限为 \(100\) 时应得到 \(41\)，极限为 \(1000\) 时应得到 \(953\)。这些检查虽然不是数学推导的一部分，但能确认筛法、前缀和以及“只检查可能破纪录的区间”这一不变量在大规模运行前是彼此一致的。
构造筛表需要 \(O(N \log \log N)\) 时间和 \(O(N)\) 空间。提取素数列表并建立前缀和，还会额外带来 \(O(\pi(N))\) 的时间和空间，其中 \(\pi(N)\) 是素数计数函数。
在最坏情况下，区间搜索看起来是 \(O(\pi(N)^2)\)，因为它本质上是在素数列表上做起点和终点的双重扫描。但实际表现远好于朴素的二次枚举：对固定起点来说，区间和单调增长，所以会很快触发停止；与此同时，当前最长长度又会提前排除所有不可能改写答案的短区间。
Пусть \(N = 10^6\). Среди всех простых чисел меньше \(N\) нужно найти то, которое представимо в виде суммы самого длинного блока последовательных простых. Если \(q_0 = 2, q_1 = 3, q_2 = 5, \dots\) обозначают простые числа в порядке возрастания, то требуется максимизировать длину \(L = j - i\) блока
$$q_i + q_{i+1} + \cdots + q_{j-1}$$
при условии, что сама сумма тоже простая и при этом удовлетворяет неравенству \(q_i + \cdots + q_{j-1} \lt N\).
В реализациях есть два встроенных контрольных примера: ниже \(100\) победителем является \(41 = 2 + 3 + 5 + 7 + 11 + 13\), а ниже \(1000\) победителем является \(953\), полученное как сумма \(21\) последовательного простого. Для границы \(10^6\) математика задачи не меняется; меняется только масштаб, поэтому главное здесь не новая теория, а эффективный перебор тех интервалов, которые еще могут улучшить текущий рекорд.
Список простых упорядочен, и каждый его элемент положителен. Именно эти два свойства превращают наивный перебор в контролируемую задачу на интервалы.
Введем префиксные суммы
$$P_0 = 0,\qquad P_m = \sum_{t=0}^{m-1} q_t \quad (m \ge 1).$$
Тогда любой блок последовательных простых записывается в виде
$$S(i,j) = q_i + q_{i+1} + \cdots + q_{j-1} = P_j - P_i,$$
где \(0 \le i \lt j\), а длина блока равна \(L = j - i\). Это центральный математический объект решения: вместо повторного суммирования каждого кандидата мы кодируем его двумя концами интервала и вычисляем одной разностью.
При фиксированном начале \(i\) значения
$$S(i,i+1),\ S(i,i+2),\ S(i,i+3),\ \dots$$
строго возрастают, потому что на каждом шаге добавляется еще одно положительное простое. Поэтому, как только для некоторого конца \(j\) выполнено \(S(i,j) \ge N\), любой более поздний конец \(j' \gt j\) уже невозможен. Более длинное окно с тем же началом не может снова оказаться ниже границы.
Именно эта монотонность обосновывает немедленный выход из внутреннего цикла. Это не случайная оптимизация, а прямое следствие того, что все слагаемые положительны.
Пусть текущая лучшая найденная длина равна \(B\). Тогда никакой новый интервал длины \(B\) или меньше не способен улучшить ответ, даже если его сумма простая, потому что задача спрашивает именно о максимальной длине. Значит, для фиксированного старта \(i\) нужно рассматривать только такие концы \(j\), что
$$j - i \ge B + 1.$$
Иначе говоря, первый осмысленный конец равен \(j = i + B + 1\). Когда находится более длинный интервал с простым значением суммы, \(B\) сразу увеличивается, и минимально допустимая длина для всех последующих проверок становится еще строже.
Именно этот инвариант лежит в основе реализаций. Код не перебирает все окна вслепую; он проверяет только те интервалы, которые действительно еще могут установить новый рекорд.
Возьмем любой интервал \((i,j)\), который потенциально может стать первым представителем новой рекордной длины. В момент, когда внешний цикл доходит до старта \(i\), текущая лучшая длина \(B\) обязательно меньше \(j-i\); иначе этот интервал уже не мог бы улучшить результат. Следовательно, \(j\) попадает в реальный диапазон внутреннего цикла, который начинается с \(i + B + 1\).
После этого внутренний цикл увеличивает \(j\) по одному, пока сумма не достигнет границы. Значит, каждый интервал, способный побить рекорд, проверяется ровно один раз. Алгоритм не эвристический: это полный перебор всех кандидатов, которые еще имеют шанс изменить ответ.
Если нумеровать простые как \(q_0 = 2, q_1 = 3, q_2 = 5, q_3 = 7, \dots\), то блок из \(21\) последовательного простого
$$7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953$$
начинается в \(q_3\) и заканчивается в \(q_{23}\). В терминах префиксных сумм это просто
$$S(3,24) = P_{24} - P_3 = 953.$$
Контрольный пример подтверждает, что ниже \(1000\) не существует более длинного блока последовательных простых, сумма которого тоже была бы простой. Этот пример компактно показывает всю схему: выбрать концы, взять разность префиксов и сравнить полученную длину с текущим рекордом.
Реализации на C++, Python и Java сначала строят решето до \(N - 1\). Одна и та же таблица затем выполняет две функции: по ней формируется упорядоченный список простых и по ней же за \(O(1)\) проверяется простота каждой кандидатной суммы.
Затем формируется префиксный массив \(P\). Накопленные суммы хранятся в целочисленных типах, достаточно широких для значений, которые заметно больше итоговой границы, потому что сами префиксные суммы продолжают расти даже тогда, когда отдельные окна уже вышли за предел \(N\).
Основной поиск поддерживает два состояния: лучший найденный простой результат и соответствующую ему лучшую длину \(B\). Для каждого стартового индекса \(i\) конечный индекс сразу начинается с \(i + B + 1\), поэтому все заведомо слишком короткие окна пропускаются полностью. Значение каждого кандидата вычисляется как \(P_j - P_i\). Если сумма достигает предела, просмотр для этого старта немедленно прекращается; если сумма простая, лучшая длина и лучший простой результат обновляются сразу же.
Кроме того, в реализациях есть две проверки корректности: \(41\) для предела \(100\) и \(953\) для предела \(1000\). Они не добавляют новой математики, но позволяют убедиться, что решето, префиксы и инвариант рекордной длины работают согласованно до запуска основного случая.
Построение решета занимает \(O(N \log \log N)\) времени и \(O(N)\) памяти. Извлечение списка простых и построение префиксных сумм добавляют \(O(\pi(N))\) времени и памяти, где \(\pi(N)\) обозначает функцию подсчета простых.
В худшем случае поиск по интервалам имеет сложность \(O(\pi(N)^2)\), потому что выглядит как вложенный перебор начальных и конечных позиций в списке простых. На практике он заметно быстрее наивного квадратичного подхода: при фиксированном начале сумма растет монотонно и быстро вызывает остановку, а текущая рекордная длина заранее отбрасывает все интервалы, которые слишком коротки, чтобы что-то изменить.
ليكن \(N = 10^6\). من بين جميع الاعداد الاولية الاصغر من \(N\)، نريد العدد الاولي الذي يمكن كتابته على صورة مجموع لاطول كتلة من الاعداد الاولية المتتالية. اذا رمزنا للاعداد الاولية المرتبة تصاعديا بــ \(q_0 = 2, q_1 = 3, q_2 = 5, \dots\)، فالمطلوب هو تعظيم طول الكتلة \(L = j - i\) في المجموع
$$q_i + q_{i+1} + \cdots + q_{j-1}$$
مع اشتراط ان يكون هذا المجموع نفسه اوليا وان يظل ايضا اصغر من \(N\).
تحتوي التطبيقات على نقطتي تحقق معروفتين: تحت \(100\) تكون القيمة الفائزة هي \(41 = 2 + 3 + 5 + 7 + 11 + 13\)، وتحت \(1000\) تكون القيمة الفائزة هي \(953\) بوصفها مجموع \(21\) عددا اوليا متتاليا. لذلك فنسخة المسألة عند الحد \(10^6\) لا تحتاج الى فكرة نظرية جديدة، بل تحتاج الى طريقة فعالة لمسح الفترات المتتالية التي ما زال من الممكن ان تحطم الرقم الحالي.
قائمة الاعداد الاولية مرتبة، وكل حد فيها موجب. هاتان الحقيقتان وحدهما تكفيان لتحويل البحث الخام الى مسألة فترات يمكن التحكم فيها.
نعرف المجاميع البادئة بالصيغة
$$P_0 = 0,\qquad P_m = \sum_{t=0}^{m-1} q_t \quad (m \ge 1).$$
عندئذ يمكن كتابة اي كتلة من الاعداد الاولية المتتالية على الصورة
$$S(i,j) = q_i + q_{i+1} + \cdots + q_{j-1} = P_j - P_i,$$
حيث \(0 \le i \lt j\) وطول الكتلة هو \(L = j - i\). هذا هو الكائن الرياضي المركزي في الحل: كل مرشح صار يوصف بنقطتي نهاية فقط، وتصبح قيمته مجرد عملية طرح واحدة.
لثابت بداية \(i\)، تكون القيم
$$S(i,i+1),\ S(i,i+2),\ S(i,i+3),\ \dots$$
متزايدة على نحو صارم، لان كل خطوة تضيف عددا اوليا موجبا جديدا. لذلك متى ما تحقق لاحد النهايات \(j\) ان \(S(i,j) \ge N\)، فان كل نهاية لاحقة \(j' \gt j\) تصبح مستحيلة مباشرة. لا توجد نافذة اطول بالبداية نفسها يمكن ان تعود ثانية تحت الحد.
هذه الرتابة هي التبرير الرياضي للخروج المبكر من الحلقة الداخلية. ليست مجرد حيلة برمجية، بل نتيجة مباشرة لان جميع المجاميع الجزئية تبنى من حدود موجبة.
افترض ان افضل سلسلة وُجدت حتى الان طولها \(B\). عندئذ لا يمكن لاي فترة جديدة طولها \(B\) او اقل ان تحسن الجواب، حتى لو كان مجموعها اوليا، لان المسألة تسأل عن اطول سلسلة. لذلك، وعند تثبيت البداية \(i\)، لا يلزم النظر الا في النهايات \(j\) التي تحقق
$$j - i \ge B + 1.$$
اي ان اول نهاية ذات معنى هي \(j = i + B + 1\). وكلما عُثر على فترة اطول ذات مجموع اولي، يجري تحديث \(B\) فورا، ويصبح الحد الادنى للاطوال المقبولة في جميع الخطوات اللاحقة اكثر صرامة.
هذا هو الثابت الذي تعتمد عليه التطبيقات. فالشفرة لا تختبر جميع النوافذ على نحو اعمى، بل تمسح فقط الفترات التي ما زال بوسعها تسجيل طول قياسي جديد.
خذ اي فترة \((i,j)\) يمكن نظريا ان تصبح اول مثال على طول قياسي جديد. عندما تصل الحلقة الخارجية الى البداية \(i\)، لا بد ان يكون الطول القياسي الحالي \(B\) اصغر من \(j-i\)، والا فلن تضيف هذه الفترة شيئا جديدا. وهذا يعني ان \(j\) يقع تلقائيا داخل النطاق الذي تمسحه الحلقة الداخلية، لانها تبدأ من \(i + B + 1\).
وبما ان الحلقة الداخلية تزيد \(j\) خطوة خطوة حتى يبلغ المجموع الحد المطلوب، فان كل فترة قادرة على كسر الرقم القياسي تُفحص مرة واحدة بالضبط. لذا فهذه ليست خوارزمية تقريبية، بل بحث كامل على جميع الفترات التي ما زالت قادرة على تغيير النتيجة.
اذا كتبنا \(q_0 = 2, q_1 = 3, q_2 = 5, q_3 = 7, \dots\)، فان الكتلة المؤلفة من \(21\) عددا اوليا متتاليا
$$7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953$$
تبدأ من \(q_3\) وتنتهي عند \(q_{23}\). وبلغة المجاميع البادئة يصبح هذا ببساطة
$$S(3,24) = P_{24} - P_3 = 953.$$
تؤكد نقطة التحقق انه لا توجد تحت \(1000\) كتلة اطول من الاعداد الاولية المتتالية يكون مجموعها اوليا. وهذا المثال يوضح المنهج كله: نمثل الكتلة بطرفيها، نحسب قيمتها بفرق بادئتين، ثم نقارن طولها بالرقم الحالي.
تبدأ تطبيقات C++ وPython وJava ببناء منخل حتى \(N - 1\). والجدول نفسه يؤدي مهمتين معا: توليد قائمة الاعداد الاولية المرتبة، والاجابة في زمن ثابت عن سؤال اولية كل مجموع مرشح.
بعد ذلك تبني التطبيقات مصفوفة البادئات \(P\). وتخزن المجاميع التراكمية في انواع عددية قادرة على حمل قيم اكبر من حد الجواب النهائي، لان مجاميع البادئات تستمر في النمو حتى بعد ان تصبح النوافذ الفردية اكبر من \(N\) وغير صالحة كمرشحين.
يحافظ البحث الرئيسي على حالتين: افضل عدد اولي وُجد حتى الان، وافضل طول \(B\). ولكل بداية \(i\)، تبدأ النهاية مباشرة من \(i + B + 1\)، وبذلك تُحذف مسبقا جميع النوافذ القصيرة التي لا يمكنها تحسين الجواب. كل مجموع مرشح يحسب بالصيغة \(P_j - P_i\). اذا بلغ هذا المقدار الحد المطلوب، يتوقف المسح لتلك البداية فورا؛ واذا كان اوليا، يجري تحديث افضل طول وافضل عدد اولي في اللحظة نفسها.
تتضمن التطبيقات ايضا نقطتي تحقق: \(41\) عندما يكون الحد \(100\)، و\(953\) عندما يكون الحد \(1000\). وهذه الاختبارات ليست جزءا من البرهان الرياضي نفسه، لكنها تؤكد ان المنخل، ومجاميع البادئة، وثابت تتبع الرقم القياسي كلها متسقة قبل تشغيل الحالة الكبيرة.
بناء المنخل يكلف \(O(N \log \log N)\) زمنا و\(O(N)\) ذاكرة. ثم يضيف استخراج قائمة الاعداد الاولية وبناء المجاميع البادئة زمنا وذاكرة من الرتبة \(O(\pi(N))\)، حيث \(\pi(N)\) هي دالة عد الاعداد الاولية.
في اسوأ الاحوال، يكون بحث الفترات من الرتبة \(O(\pi(N)^2)\)، لانه يظهر على صورة مسح متداخل لبدايات ونهايات في قائمة الاعداد الاولية. لكن الاداء العملي افضل بكثير من التربيع الساذج: فالمجموع عند بداية ثابتة يزداد بصورة رتيبة ويؤدي الى توقف مبكر، كما ان افضل طول حالي يستبعد من البداية كل فترة اقصر من ان تكون مؤثرة.