We seek the sum of all integers \(n < 150{,}000{,}000\) for which the six values $$n^2+1,\ n^2+3,\ n^2+7,\ n^2+9,\ n^2+13,\ n^2+27$$ are prime, while the odd values between them, $$n^2+5,\ n^2+11,\ n^2+15,\ n^2+17,\ n^2+19,\ n^2+21,\ n^2+23,\ n^2+25,$$ are composite. Because the primes must be consecutive inside that window, those eight exclusions are part of the definition of a valid \(n\), not an optional afterthought.
A brute-force search would examine far too many large numbers near \(2.25\times 10^{16}\). The successful strategy is to force \(n\) into a tiny set of residue classes, precompute modular obstructions for many small primes, and reserve exact primality testing for the few candidates that survive all cheap filters.
Let $$G=\{1,3,7,9,13,27\},\qquad C=\{5,11,15,17,19,21,23,25\}.$$ Then \(n\) is a solution exactly when \(n^2+g\) is prime for every \(g\in G\) and \(n^2+c\) is composite for every \(c\in C\).
If \(n\) is even, then \(n^2\) is even, so every even offset produces an even number greater than 2 and is automatically composite. That is why only the odd offsets matter. The implementation therefore tracks two explicit sets: the six offsets that must produce primes and the eight odd offsets in the same interval that must not.
Several modular arguments remove almost all integers before any primality test is attempted.
If \(n\) were odd, then \(n^2+1\) would be even and larger than 2, so \(n\) must be even.
Modulo 5, the quadratic residues are \(0,1,4\). If \(n^2\equiv 1\pmod 5\), then \(n^2+9\equiv 0\pmod 5\). If \(n^2\equiv 4\pmod 5\), then \(n^2+1\equiv 0\pmod 5\). Therefore the only surviving case is \(n^2\equiv 0\pmod 5\), which forces \(5\mid n\).
Modulo 3, a multiple of 3 would make \(n^2+3\), \(n^2+9\), and \(n^2+27\) divisible by 3, so \(3\nmid n\).
The strongest restriction comes from modulo 7. The quadratic residues mod 7 are \(0,1,2,4\). If \(n^2\equiv 0\pmod 7\), then \(n^2+7\) is divisible by 7. If \(n^2\equiv 1\pmod 7\), then \(n^2+13\equiv 0\pmod 7\). If \(n^2\equiv 4\pmod 7\), then \(n^2+3\equiv 0\pmod 7\). Only \(n^2\equiv 2\pmod 7\) survives, which is equivalent to \(n\equiv \pm 3\pmod 7\).
Combining \(2\mid n\), \(5\mid n\), and \(n\equiv \pm 3\pmod 7\) leaves exactly two arithmetic progressions: $$n\equiv 10 \pmod{70}\qquad\text{or}\qquad n\equiv 60 \pmod{70}.$$ The same mod-7 argument automatically makes \(n^2+5\) and \(n^2+19\) divisible by 7, so two forbidden offsets are eliminated for free.
The smallest candidate already exhibits the full pattern. For \(n=10\), we have \(n^2=100\), so the required values are $$101,\ 103,\ 107,\ 109,\ 113,\ 127,$$ and each of them is prime. The forbidden odd offsets give $$105,\ 111,\ 115,\ 117,\ 119,\ 121,\ 123,\ 125,$$ and each of those is composite. So \(10\) is a genuine solution and a concrete illustration of the exact condition being tested.
The fixed mod-70 reduction is only the first layer. For each small prime \(p\) up to 2000, the implementations precompute the bad residue set $$R_p=\{r\in\{0,\dots,p-1\}: r^2+g\equiv 0\pmod p\text{ for some }g\in G\}.$$ If \(n\bmod p\in R_p\), then at least one required value is divisible by \(p\), so the candidate can be discarded immediately.
Primes 2 and 5 are omitted from this table because divisibility by them has already been absorbed into the forced form \(n\equiv 0\pmod{10}\). For very small \(n\), a congruence \(n^2+g\equiv 0\pmod p\) could still mean \(n^2+g=p\), which is prime rather than composite. The implementations avoid that edge case by activating these precomputed tables only once \(n\ge 1000\), a conservative threshold well above \(\sqrt{2000}\).
After the modular screens, the surviving candidates are rare. Each survivor is then checked exactly: the six values \(n^2+g\) must be prime and the eight values \(n^2+c\) must be composite. Since $$n^2+27 < (150{,}000{,}000)^2+27 < 2.25\times 10^{16},$$ every tested integer fits comfortably in 64-bit arithmetic, so fast Miller-Rabin based certification is practical for the last stage.
The C++, Python, and Java implementations iterate only over the sequences \(70m+10\) and \(70m+60\). This is the direct payoff of the congruence analysis: instead of checking all integers, the search immediately keeps only about one out of every 35 candidates.
Inside one progression, the step size is always 70, so the square is updated by the recurrence $$ (n+70)^2=n^2+140n+4900.$$ That avoids recomputing \(n^2\) from scratch. The same incremental idea is used for every small-prime filter: if the current residue modulo \(p\) is known, the next one is obtained by adding \(70\bmod p\). The sieve phase therefore becomes a sequence of cheap table lookups instead of repeated modular squaring.
Each candidate passes through a short pipeline: inexpensive divisibility checks for 3 and 13, lookup in the precomputed bad-residue tables, exact primality tests on the six required offsets, and exact compositeness checks on the eight forbidden offsets. When every condition succeeds, the candidate \(n\) is added to the running sum.
The interval splits naturally into independent chunks. The C++ and Java implementations parallelize those chunks directly, and the Python implementation can also distribute chunks across worker processes. The mathematics is identical in all three languages; only the execution strategy changes.
Let \(L\) be the search limit and \(B\) the upper bound for the small-prime residue tables. Building the tables costs \(O(B\log\log B+\sum_{p\le B} p)\) time and \(O(\sum_{p\le B} p)\) memory, because each prime \(p\) stores a boolean array of length \(p\).
The main scan visits only about \(L/35\) integers because it uses two residue classes modulo 70. For each candidate it performs constant-time arithmetic plus one residue update per sieve prime, and only a tiny fraction survive to the primality stage. With the fixed choice \(B=2000\) used by the implementations, memory usage stays small and the running time is effectively linear in the search limit.
Gesucht ist die Summe aller ganzen Zahlen \(n < 150{,}000{,}000\), für die die sechs Werte $$n^2+1,\ n^2+3,\ n^2+7,\ n^2+9,\ n^2+13,\ n^2+27$$ prim sind, während die dazwischenliegenden ungeraden Werte $$n^2+5,\ n^2+11,\ n^2+15,\ n^2+17,\ n^2+19,\ n^2+21,\ n^2+23,\ n^2+25$$ zusammengesetzt sind. Weil die Primzahlen in diesem Intervall aufeinanderfolgend sein sollen, gehören diese acht Ausschlusswerte zwingend zur Bedingung.
Ein direkter Durchlauf wäre viel zu teuer, denn die getesteten Zahlen liegen in der Größenordnung \(10^{16}\). Die Lösung reduziert deshalb zuerst die möglichen Restklassen von \(n\), verwendet dann für viele kleine Primzahlen vorberechnete Verbotsreste und führt exakte Primzahltests nur noch für die wenigen Überlebenden aus.
Setze $$G=\{1,3,7,9,13,27\},\qquad C=\{5,11,15,17,19,21,23,25\}.$$ Dann ist \(n\) genau dann gültig, wenn \(n^2+g\) für alle \(g\in G\) prim und \(n^2+c\) für alle \(c\in C\) zusammengesetzt ist.
Ist \(n\) gerade, dann ist \(n^2\) ebenfalls gerade. Jeder gerade Offset liefert dann eine gerade Zahl größer als 2 und ist automatisch zusammengesetzt. Deshalb müssen nur die ungeraden Offsets explizit betrachtet werden: sechs Stück, die prim sein müssen, und acht Stück, die ausdrücklich nicht prim sein dürfen.
Mehrere modulare Argumente verwerfen fast alle Zahlen schon vor dem ersten Primzahltest.
Wäre \(n\) ungerade, dann wäre \(n^2+1\) gerade und größer als 2. Also muss \(n\) gerade sein.
Modulo 5 sind die quadratischen Reste \(0,1,4\). Falls \(n^2\equiv 1\pmod 5\), ist \(n^2+9\equiv 0\pmod 5\). Falls \(n^2\equiv 4\pmod 5\), ist \(n^2+1\equiv 0\pmod 5\). Es bleibt also nur \(n^2\equiv 0\pmod 5\), also \(5\mid n\).
Modulo 3 würde ein Vielfaches von 3 die Werte \(n^2+3\), \(n^2+9\) und \(n^2+27\) durch 3 teilbar machen. Daher gilt \(3\nmid n\).
Die stärkste Einschränkung kommt von modulo 7. Die quadratischen Reste mod 7 sind \(0,1,2,4\). Bei \(n^2\equiv 0\pmod 7\) ist \(n^2+7\) durch 7 teilbar. Bei \(n^2\equiv 1\pmod 7\) ist \(n^2+13\equiv 0\pmod 7\). Bei \(n^2\equiv 4\pmod 7\) ist \(n^2+3\equiv 0\pmod 7\). Nur \(n^2\equiv 2\pmod 7\) bleibt übrig, also \(n\equiv \pm 3\pmod 7\).
Aus \(2\mid n\), \(5\mid n\) und \(n\equiv \pm 3\pmod 7\) folgen genau zwei arithmetische Progressionen: $$n\equiv 10 \pmod{70}\qquad\text{oder}\qquad n\equiv 60 \pmod{70}.$$ Dasselbe mod-7-Argument sorgt außerdem automatisch dafür, dass \(n^2+5\) und \(n^2+19\) durch 7 teilbar sind.
Schon der kleinste Kandidat zeigt das vollständige Muster. Für \(n=10\) ist \(n^2=100\), also lauten die geforderten Werte $$101,\ 103,\ 107,\ 109,\ 113,\ 127,$$ und alle sind prim. Für die verbotenen ungeraden Offsets erhält man $$105,\ 111,\ 115,\ 117,\ 119,\ 121,\ 123,\ 125,$$ und jede dieser Zahlen ist zusammengesetzt. Damit ist \(10\) tatsächlich eine Lösung.
Die Reduktion auf mod 70 ist nur die erste Ebene. Für jede kleine Primzahl \(p\) bis 2000 berechnen die Implementierungen die verbotene Restmenge $$R_p=\{r\in\{0,\dots,p-1\}: r^2+g\equiv 0\pmod p\text{ für ein }g\in G\}.$$ Gilt \(n\bmod p\in R_p\), dann ist mindestens einer der geforderten Werte durch \(p\) teilbar und der Kandidat kann sofort verworfen werden.
Die Primzahlen 2 und 5 tauchen in dieser Tabelle nicht auf, weil ihre Wirkung bereits in der Form \(n\equiv 0\pmod{10}\) steckt. Für sehr kleine \(n\) könnte \(n^2+g\equiv 0\pmod p\) allerdings noch bedeuten, dass \(n^2+g=p\) und damit prim ist. Deshalb schalten die Implementierungen die vorberechneten Resttabellen erst ab \(n\ge 1000\) zu, also mit einem bewusst konservativen Grenzwert weit oberhalb von \(\sqrt{2000}\).
Nach den modularen Filtern bleiben nur wenige Kandidaten übrig. Diese werden exakt geprüft: Die sechs Zahlen \(n^2+g\) müssen prim sein, die acht Zahlen \(n^2+c\) zusammengesetzt. Wegen $$n^2+27 < (150{,}000{,}000)^2+27 < 2.25\times 10^{16}$$ passen alle getesteten Werte bequem in 64 Bit, sodass schnelle Miller-Rabin-Tests für die Schlussphase ausreichen.
Die C++-, Python- und Java-Implementierungen iterieren nur über \(70m+10\) und \(70m+60\). Das ist der unmittelbare Gewinn der Kongruenzanalyse: Statt aller ganzen Zahlen muss nur etwa jeder fünfunddreißigste Kandidat betrachtet werden.
Innerhalb einer Progression beträgt der Schritt immer 70. Daher wird das Quadrat über $$ (n+70)^2=n^2+140n+4900$$ aktualisiert, statt jedes Mal neu multipliziert zu werden. Genauso werden die Reste modulo jeder Sieb-Primzahl fortgeschrieben: Kennt man den aktuellen Rest, erhält man den nächsten durch Addition von \(70\bmod p\). Dadurch besteht das Filtern fast nur aus Arrayzugriffen.
Jeder Kandidat durchläuft eine kurze Prüfkette: billige Teilbarkeitstests für 3 und 13, Nachschlagen in den vorberechneten Resttabellen, exakte Primzahltests für die sechs geforderten Offsets und exakte Zusammengesetzt-Tests für die acht verbotenen Offsets. Besteht ein Kandidat alle Stufen, wird \(n\) zur Summe addiert.
Das Intervall zerfällt natürlich in unabhängige Teilbereiche. Die C++- und Java-Implementierungen parallelisieren diese Blöcke direkt, und auch die Python-Implementierung kann die Arbeit auf mehrere Prozesse verteilen. Die mathematische Logik bleibt dabei identisch.
Sei \(L\) die Suchgrenze und \(B\) die Obergrenze für die Resttabellen kleiner Primzahlen. Der Aufbau dieser Tabellen kostet \(O(B\log\log B+\sum_{p\le B} p)\) Zeit und \(O(\sum_{p\le B} p)\) Speicher, weil für jede Primzahl \(p\) ein boolesches Feld der Länge \(p\) gespeichert wird.
Der Hauptdurchlauf besucht nur etwa \(L/35\) Zahlen, da nur zwei Restklassen modulo 70 betrachtet werden. Pro Kandidat fallen nur konstante Arithmetik und ein Restupdate pro Sieb-Primzahl an; nur ein winziger Teil erreicht überhaupt die Primzahltests. Mit dem festen Wert \(B=2000\) aus den Implementierungen bleibt der Speicher klein und die Laufzeit ist praktisch linear in der Suchgrenze.
\(n < 150{,}000{,}000\) için şu altı sayının $$n^2+1,\ n^2+3,\ n^2+7,\ n^2+9,\ n^2+13,\ n^2+27$$ asal olduğu, buna karşılık aradaki tek kaymaların $$n^2+5,\ n^2+11,\ n^2+15,\ n^2+17,\ n^2+19,\ n^2+21,\ n^2+23,\ n^2+25$$ bileşik kaldığı tüm \(n\) değerlerinin toplamı isteniyor. Soruda bu asal sayıların aralık içinde art arda gelmesi gerektiği için, bu sekiz yasak değer çözüm tanımının doğrudan bir parçasıdır.
Doğrudan tarama çok pahalı olur; çünkü test edilen sayılar \(2.25\times 10^{16}\) mertebesine kadar çıkıyor. Bu yüzden çözüm, önce \(n\) için zorunlu kalan kalıntı sınıflarını çıkarıyor, sonra birçok küçük asal için önceden hesaplanmış eleme tabloları kullanıyor ve kesin asallık testlerini yalnızca son derece az sayıdaki adaya bırakıyor.
$$G=\{1,3,7,9,13,27\},\qquad C=\{5,11,15,17,19,21,23,25\}$$ olsun. O hâlde \(n\), ancak ve ancak her \(g\in G\) için \(n^2+g\) asal ve her \(c\in C\) için \(n^2+c\) bileşikse çözümdür.
\(n\) çiftse \(n^2\) de çifttir. Bu durumda her çift kayma, 2'den büyük bir çift sayı üretir ve otomatik olarak bileşiktir. Bu yüzden açıkça takip edilmesi gerekenler sadece tek kaymalardır: asal olması zorunlu olan altı kayma ve asal olmaması zorunlu olan sekiz kayma.
Daha asallık testine gelmeden çok sayıda \(n\) değeri modüler nedenlerle elenir.
\(n\) tek olsaydı \(n^2+1\) çift ve 2'den büyük olurdu. Demek ki \(n\) mutlaka çifttir.
Mod 5'te karesel kalıntılar \(0,1,4\)'tür. Eğer \(n^2\equiv 1\pmod 5\) ise \(n^2+9\equiv 0\pmod 5\). Eğer \(n^2\equiv 4\pmod 5\) ise \(n^2+1\equiv 0\pmod 5\). O halde ayakta kalan tek durum \(n^2\equiv 0\pmod 5\), yani \(5\mid n\) olur.
Mod 3'te ise \(n\) sayısı 3'ün katı olursa \(n^2+3\), \(n^2+9\) ve \(n^2+27\) de 3'e bölünür. Bu yüzden \(3\nmid n\) gerekir.
Asıl güçlü kısıt mod 7'den gelir. Mod 7'de karesel kalıntılar \(0,1,2,4\)'tür. \(n^2\equiv 0\pmod 7\) olursa \(n^2+7\) 7'ye bölünür. \(n^2\equiv 1\pmod 7\) olursa \(n^2+13\equiv 0\pmod 7\). \(n^2\equiv 4\pmod 7\) olursa \(n^2+3\equiv 0\pmod 7\). Geriye sadece \(n^2\equiv 2\pmod 7\) kalır; bu da \(n\equiv \pm 3\pmod 7\) demektir.
\(2\mid n\), \(5\mid n\) ve \(n\equiv \pm 3\pmod 7\) birlikte ele alındığında tam olarak iki aritmetik dizi kalır: $$n\equiv 10 \pmod{70}\qquad\text{veya}\qquad n\equiv 60 \pmod{70}.$$ Aynı mod-7 analizi, \(n^2+5\) ile \(n^2+19\) ifadelerini de otomatik olarak 7'ye bölünebilir yapar; yani yasak kaymaların ikisi bedavadan bileşiktir.
En küçük aday bile tüm deseni gösterir. \(n=10\) için \(n^2=100\) olur. Zorunlu değerler $$101,\ 103,\ 107,\ 109,\ 113,\ 127$$ olup hepsi asaldır. Yasak tek kaymalar ise $$105,\ 111,\ 115,\ 117,\ 119,\ 121,\ 123,\ 125$$ verir ve bunların her biri bileşiktir. Dolayısıyla \(10\), gerçekten geçerli bir çözümdür.
Mod 70 indirgemesi sadece ilk katmandır. Uygulamalar, 2000'e kadar her küçük asal \(p\) için $$R_p=\{r\in\{0,\dots,p-1\}: r^2+g\equiv 0\pmod p\text{ olacak şekilde bir }g\in G\text{ vardır}\}$$ kümesini önceden hesaplar. Eğer \(n\bmod p\in R_p\) ise zorunlu altı sayıdan en az biri \(p\)'ye bölünür ve aday hemen elenir.
2 ve 5 bu tablolarda yer almaz; çünkü onların etkisi zaten \(n\equiv 0\pmod{10}\) şartının içine gömülmüştür. Çok küçük \(n\) değerlerinde \(n^2+g\equiv 0\pmod p\) olması, bazen \(n^2+g=p\) anlamına gelebilir ve bu sayı asal olabilir. Uygulamalar bu köşe durumundan kaçınmak için önceden hesaplanan tabloları ancak \(n\ge 1000\) olduktan sonra devreye sokar.
Modüler filtrelerden sonra çok az aday kalır. Bunlar için tam doğrulama yapılır: \(n^2+g\) değerlerinin altısı da asal olmalı, \(n^2+c\) değerlerinin sekizi de bileşik olmalıdır. Ayrıca $$n^2+27 < (150{,}000{,}000)^2+27 < 2.25\times 10^{16}$$ olduğu için bütün test edilen sayılar 64 bit içinde kalır; bu da son aşamada hızlı Miller-Rabin temelli asallık kontrollerini mümkün kılar.
C++, Python ve Java uygulamaları sadece \(70m+10\) ile \(70m+60\) dizilerini dolaşır. Bu, kongruens analizinin doğrudan kazancıdır: bütün tamsayılar yerine yaklaşık her 35 sayıdan yalnızca biri değerlendirilir.
Tek bir dizide adım büyüklüğü hep 70'tir. Bu yüzden kareler her seferinde yeniden çarpılmak yerine $$ (n+70)^2=n^2+140n+4900$$ bağıntısıyla güncellenir. Aynı fikir küçük asal filtrelerinde de kullanılır: \(p\)'ye göre mevcut kalıntı biliniyorsa bir sonraki kalıntı sadece \(70\bmod p\) eklenerek bulunur. Böylece eleme aşaması tekrarlı modüler kare hesapları yerine ucuz tablo erişimlerine dönüşür.
Her aday kısa bir karar hattından geçer: 3 ve 13 için ucuz bölünebilirlik testleri, önceden hesaplanmış kötü kalıntı tablolarına bakış, altı zorunlu kayma için kesin asallık testleri ve sekiz yasak kayma için kesin bileşiklik testleri. Bütün koşullar sağlanırsa \(n\) toplama eklenir.
Aralık doğal olarak bağımsız parçalara bölünebilir. C++ ve Java uygulamaları bu parçaları doğrudan paralelleştirir; Python uygulaması da işi birden çok işçi sürece dağıtabilir. Matematik aynı kalır, sadece yürütme şekli değişir.
\(L\) arama sınırı, \(B\) ise küçük asal kalıntı tablolarının üst sınırı olsun. Bu tabloların kurulumu \(O(B\log\log B+\sum_{p\le B} p)\) zaman ve \(O(\sum_{p\le B} p)\) bellek ister; çünkü her asal \(p\) için uzunluğu \(p\) olan bir boole tablosu tutulur.
Ana tarama, mod 70'te yalnızca iki kalıntı sınıfı kullandığı için yaklaşık \(L/35\) adayı ziyaret eder. Her aday için sabit zamanlı aritmetik ve her filtre asalı başına bir kalıntı güncellemesi yapılır; adayların çok küçük bir kısmı asallık testlerine kadar ulaşır. Uygulamaların kullandığı sabit \(B=2000\) değeriyle bellek küçüktür ve çalışma süresi pratikte arama sınırına göre doğrusal davranır.
Se pide la suma de todos los enteros \(n < 150{,}000{,}000\) tales que los seis valores $$n^2+1,\ n^2+3,\ n^2+7,\ n^2+9,\ n^2+13,\ n^2+27$$ son primos, mientras que los valores impares intermedios $$n^2+5,\ n^2+11,\ n^2+15,\ n^2+17,\ n^2+19,\ n^2+21,\ n^2+23,\ n^2+25$$ son compuestos. Como el enunciado exige que esos primos sean consecutivos dentro de esa ventana, las ocho exclusiones forman parte esencial de la condición.
Un barrido ingenuo sería demasiado costoso, porque los enteros comprobados llegan a la escala de \(10^{16}\). La solución eficaz reduce primero \(n\) a muy pocas clases residuales, luego usa obstrucciones modulares precalculadas para muchos primos pequeños y deja las pruebas exactas de primalidad para el pequeño conjunto de candidatos supervivientes.
Definamos $$G=\{1,3,7,9,13,27\},\qquad C=\{5,11,15,17,19,21,23,25\}.$$ Entonces \(n\) es solución si y solo si \(n^2+g\) es primo para todo \(g\in G\) y \(n^2+c\) es compuesto para todo \(c\in C\).
Si \(n\) es par, entonces \(n^2\) también es par. Por tanto, cualquier desplazamiento par produce un número par mayor que 2 y queda automáticamente descartado como primo. Por eso solo importan los desplazamientos impares: seis que deben dar primos y ocho que deben dar compuestos.
Antes de ejecutar ninguna prueba de primalidad, varios argumentos modulares eliminan casi todos los enteros.
Si \(n\) fuera impar, \(n^2+1\) sería par y mayor que 2, así que \(n\) debe ser par.
Módulo 5, los residuos cuadráticos son \(0,1,4\). Si \(n^2\equiv 1\pmod 5\), entonces \(n^2+9\equiv 0\pmod 5\). Si \(n^2\equiv 4\pmod 5\), entonces \(n^2+1\equiv 0\pmod 5\). La única posibilidad es \(n^2\equiv 0\pmod 5\), es decir, \(5\mid n\).
Módulo 3, si \(n\) fuera múltiplo de 3, entonces \(n^2+3\), \(n^2+9\) y \(n^2+27\) serían divisibles por 3. Por lo tanto, \(3\nmid n\).
La restricción decisiva aparece módulo 7. Los residuos cuadráticos mod 7 son \(0,1,2,4\). Si \(n^2\equiv 0\pmod 7\), entonces \(n^2+7\) es divisible por 7. Si \(n^2\equiv 1\pmod 7\), entonces \(n^2+13\equiv 0\pmod 7\). Si \(n^2\equiv 4\pmod 7\), entonces \(n^2+3\equiv 0\pmod 7\). Solo sobrevive \(n^2\equiv 2\pmod 7\), equivalente a \(n\equiv \pm 3\pmod 7\).
Al combinar \(2\mid n\), \(5\mid n\) y \(n\equiv \pm 3\pmod 7\), quedan exactamente dos progresiones aritméticas: $$n\equiv 10 \pmod{70}\qquad\text{o}\qquad n\equiv 60 \pmod{70}.$$ El mismo argumento módulo 7 hace que \(n^2+5\) y \(n^2+19\) sean automáticamente divisibles por 7.
El candidato más pequeño ya muestra el patrón completo. Para \(n=10\), \(n^2=100\), de modo que los valores exigidos son $$101,\ 103,\ 107,\ 109,\ 113,\ 127,$$ y todos son primos. Los desplazamientos impares prohibidos producen $$105,\ 111,\ 115,\ 117,\ 119,\ 121,\ 123,\ 125,$$ y todos son compuestos. Así, \(10\) es una solución auténtica.
La reducción módulo 70 es solo la primera capa. Para cada primo pequeño \(p\) hasta 2000, las implementaciones precalculan el conjunto de residuos prohibidos $$R_p=\{r\in\{0,\dots,p-1\}: r^2+g\equiv 0\pmod p\text{ para algún }g\in G\}.$$ Si \(n\bmod p\in R_p\), entonces al menos uno de los seis valores obligatorios es divisible por \(p\), y el candidato se descarta sin más.
Los primos 2 y 5 no aparecen en esas tablas porque su efecto ya está absorbido por la forma \(n\equiv 0\pmod{10}\). Para valores muy pequeños de \(n\), la congruencia \(n^2+g\equiv 0\pmod p\) todavía podría significar \(n^2+g=p\), que sí sería primo. Para evitar ese caso límite, las implementaciones activan las tablas precalculadas solo cuando \(n\ge 1000\), un umbral conservador muy por encima de \(\sqrt{2000}\).
Después de los filtros modulares quedan muy pocos candidatos. Cada superviviente se comprueba exactamente: los seis valores \(n^2+g\) deben ser primos y los ocho valores \(n^2+c\) deben ser compuestos. Como $$n^2+27 < (150{,}000{,}000)^2+27 < 2.25\times 10^{16},$$ todos los enteros examinados caben cómodamente en 64 bits, lo que hace viable una etapa final con pruebas rápidas de Miller-Rabin.
Las implementaciones en C++, Python y Java iteran únicamente sobre \(70m+10\) y \(70m+60\). Ese es el beneficio directo del análisis de congruencias: en lugar de examinar todos los enteros, la búsqueda conserva desde el principio solo uno de cada 35 aproximadamente.
Dentro de una progresión, el paso siempre es 70, así que el cuadrado se actualiza mediante $$ (n+70)^2=n^2+140n+4900.$$ Eso evita recalcular \(n^2\) desde cero. La misma idea se usa para cada filtro modular: si se conoce el residuo actual módulo \(p\), el siguiente se obtiene sumando \(70\bmod p\). Por eso la fase de cribado se reduce a accesos muy baratos a tablas booleanas.
Cada candidato atraviesa una cadena breve: pruebas baratas de divisibilidad por 3 y 13, consulta de las tablas de residuos prohibidos, pruebas exactas de primalidad en los seis desplazamientos obligatorios y comprobaciones exactas de compositividad en los ocho desplazamientos prohibidos. Si todo se cumple, se añade \(n\) a la suma.
El intervalo se divide naturalmente en bloques independientes. Las implementaciones de C++ y Java paralelizan esos bloques de forma directa, y la implementación de Python también puede repartirlos entre procesos trabajadores. La matemática es la misma en los tres casos; cambia solo la estrategia de ejecución.
Sea \(L\) el límite de búsqueda y \(B\) la cota usada para las tablas de residuos de primos pequeños. Construir esas tablas cuesta \(O(B\log\log B+\sum_{p\le B} p)\) en tiempo y \(O(\sum_{p\le B} p)\) en memoria, porque cada primo \(p\) almacena un arreglo booleano de longitud \(p\).
El barrido principal visita solo unas \(L/35\) cantidades, ya que usa dos clases residuales módulo 70. Para cada candidato se hace aritmética constante y una actualización de residuo por primo del tamiz; únicamente una fracción diminuta alcanza la etapa de primalidad. Con el valor fijo \(B=2000\) usado por las implementaciones, la memoria sigue siendo pequeña y el tiempo de ejecución es, en la práctica, lineal en el límite de búsqueda.
要求所有满足 \(n < 150{,}000{,}000\) 的整数 \(n\) 之和，使得下面六个数 $$n^2+1,\ n^2+3,\ n^2+7,\ n^2+9,\ n^2+13,\ n^2+27$$ 都是质数，而它们之间的奇数偏移 $$n^2+5,\ n^2+11,\ n^2+15,\ n^2+17,\ n^2+19,\ n^2+21,\ n^2+23,\ n^2+25$$ 全部是合数。题目中的“连续质数”并不是泛泛而谈，它明确要求在这段区间内，除了那六项之外，其他可能出现的奇数候选都不能是质数。
如果直接遍历所有 \(n\) 并对这些大约在 \(10^{16}\) 量级的数逐个做完整质性判断，代价会很高。真正有效的做法是先利用同余条件把 \(n\) 压缩到极少数剩余类，再为许多小质数预计算“必败余数”，最后只对极少数漏网候选做精确的质数与合数验证。
记 $$G=\{1,3,7,9,13,27\},\qquad C=\{5,11,15,17,19,21,23,25\}.$$ 那么 \(n\) 成为解，当且仅当对每个 \(g\in G\)，\(n^2+g\) 都是质数；并且对每个 \(c\in C\)，\(n^2+c\) 都是合数。
一旦 \(n\) 为偶数，\(n^2\) 也是偶数。这样任何偶数偏移都会得到一个大于 2 的偶数，自然不可能是质数，所以根本不需要显式检查。真正需要关心的只有奇数偏移：六个必须给出质数的偏移，以及同一区间里八个必须保持合数的偏移。
在真正做质性测试之前，几个简单的模运算已经能砍掉绝大多数整数。
如果 \(n\) 是奇数，那么 \(n^2+1\) 就是大于 2 的偶数，不可能是质数，所以 \(n\) 必须是偶数。
模 5 的平方剩余只有 \(0,1,4\)。如果 \(n^2\equiv 1\pmod 5\)，那么 \(n^2+9\equiv 0\pmod 5\)；如果 \(n^2\equiv 4\pmod 5\)，那么 \(n^2+1\equiv 0\pmod 5\)。因此唯一可能是 \(n^2\equiv 0\pmod 5\)，也就是 \(5\mid n\)。
模 3 时，如果 \(n\) 是 3 的倍数，那么 \(n^2+3\)、\(n^2+9\) 与 \(n^2+27\) 都会被 3 整除，所以还必须有 \(3\nmid n\)。
最关键的限制来自模 7。模 7 的平方剩余为 \(0,1,2,4\)。若 \(n^2\equiv 0\pmod 7\)，则 \(n^2+7\) 被 7 整除；若 \(n^2\equiv 1\pmod 7\)，则 \(n^2+13\equiv 0\pmod 7\)；若 \(n^2\equiv 4\pmod 7\)，则 \(n^2+3\equiv 0\pmod 7\)。只有 \(n^2\equiv 2\pmod 7\) 可以保留下来，也就是 \(n\equiv \pm 3\pmod 7\)。
把 \(2\mid n\)、\(5\mid n\) 与 \(n\equiv \pm 3\pmod 7\) 合并起来，\(n\) 只可能落在两条等差数列中： $$n\equiv 10 \pmod{70}\qquad\text{或}\qquad n\equiv 60 \pmod{70}.$$ 同一个模 7 论证还自动保证 \(n^2+5\) 与 \(n^2+19\) 一定能被 7 整除，因此这两个“禁止偏移”根本不需要再单独费力处理。
最小的候选值已经能把整个结构展示得很清楚。取 \(n=10\)，则 \(n^2=100\)。这时要求为质数的六个数是 $$101,\ 103,\ 107,\ 109,\ 113,\ 127,$$ 它们全部是质数。对应的八个禁止奇数偏移则给出 $$105,\ 111,\ 115,\ 117,\ 119,\ 121,\ 123,\ 125,$$ 它们全部是合数。所以 \(10\) 的确是一个满足题意的解，这个例子也准确展示了程序在检查什么。
模 70 的化简只是第一层。实现中对每个不超过 2000 的小质数 \(p\) 预计算一个坏余数集合 $$R_p=\{r\in\{0,\dots,p-1\}: r^2+g\equiv 0\pmod p\text{ 对某个 }g\in G\text{ 成立}\}.$$ 如果 \(n\bmod p\in R_p\)，那么六个必须为质数的值中至少有一个会被 \(p\) 整除，于是这个候选可以立刻淘汰。
质数 2 和 5 不必进入这张表，因为它们的作用已经被 \(n\equiv 0\pmod{10}\) 吸收掉了。对于很小的 \(n\)，同余式 \(n^2+g\equiv 0\pmod p\) 仍有可能对应 \(n^2+g=p\)，那样反而是质数。为避免这个边界情况，实现采用了一个保守阈值，只在 \(n\ge 1000\) 时启用这些预计算表；这个阈值远大于 \(\sqrt{2000}\)，因此完全安全。
经过模筛以后，剩下的候选已经非常少。此时再做精确判断：六个 \(n^2+g\) 必须全部为质数，八个 \(n^2+c\) 必须全部为合数。由于 $$n^2+27 < (150{,}000{,}000)^2+27 < 2.25\times 10^{16},$$ 所有被测试的整数都稳稳落在 64 位范围内，因此最后阶段可以高效地使用 Miller-Rabin 一类的快速质性检测。
C++、Python 和 Java 实现都只遍历 \(70m+10\) 与 \(70m+60\) 这两条数列。这正是前面同余分析的直接收益：原本所有整数都需要检查，现在一开始就只保留大约三十五分之一。
在同一条数列中，步长恒为 70，所以平方可以用 $$ (n+70)^2=n^2+140n+4900$$ 递推更新，而不必每次重新计算 \(n^2\)。对每个小质数的模状态也一样：已知当前 \(n\bmod p\) 后，下一个状态只需要再加上 \(70\bmod p\)。这样一来，筛选阶段几乎只剩下数组查询和少量整数加法。
每个候选都会经过一条很短的流水线：先做 3 和 13 的廉价整除检查，再查询预计算的坏余数表，然后对六个必须偏移做精确质数测试，对八个禁止偏移做精确合数测试。全部通过时，就把该 \(n\) 加入总和。
搜索区间天然可以拆成互不影响的块。C++ 和 Java 实现直接并行处理这些块，Python 实现也可以把块分发给多个工作进程。三种语言的数学逻辑完全一致，只是执行方式不同。
设搜索上界为 \(L\)，小质数余数表的上界为 \(B\)。建立这些表需要 \(O(B\log\log B+\sum_{p\le B} p)\) 时间和 \(O(\sum_{p\le B} p)\) 空间，因为对每个质数 \(p\) 都要保存一个长度为 \(p\) 的布尔数组。
主循环只访问约 \(L/35\) 个候选，因为它只保留模 70 下的两个剩余类。对每个候选，程序执行常数次整数运算以及每个筛质数一次的余数更新，真正进入质数测试阶段的只占极小比例。由于实现固定采用 \(B=2000\)，所以内存开销很小，运行时间在实践中几乎与搜索上界成线性关系。
Нужно найти сумму всех целых \(n < 150{,}000{,}000\), для которых шесть чисел $$n^2+1,\ n^2+3,\ n^2+7,\ n^2+9,\ n^2+13,\ n^2+27$$ являются простыми, а все промежуточные нечётные значения $$n^2+5,\ n^2+11,\ n^2+15,\ n^2+17,\ n^2+19,\ n^2+21,\ n^2+23,\ n^2+25$$ являются составными. Условие о последовательных простых в этом промежутке означает, что эти восемь исключений обязательны так же, как и шесть требуемых простых.
Прямой перебор слишком дорог, потому что проверяемые числа достигают порядка \(10^{16}\). Рабочее решение сначала резко сокращает множество кандидатов по модульным соображениям, затем использует заранее подготовленные запрещённые остатки для многих малых простых и лишь после этого запускает точные тесты простоты.
Обозначим $$G=\{1,3,7,9,13,27\},\qquad C=\{5,11,15,17,19,21,23,25\}.$$ Тогда \(n\) подходит тогда и только тогда, когда \(n^2+g\) простое для каждого \(g\in G\), а \(n^2+c\) составное для каждого \(c\in C\).
Если \(n\) чётно, то и \(n^2\) чётно. Значит, любое чётное смещение даёт чётное число больше 2 и автоматически не может быть простым. Поэтому в явном виде нужно проверять только нечётные смещения: шесть обязательных и восемь запрещённых.
Ещё до тестов простоты несколько простых модульных рассуждений отсекают почти все значения.
Если бы \(n\) было нечётным, то \(n^2+1\) было бы чётным и больше 2. Следовательно, \(n\) обязано быть чётным.
По модулю 5 квадратичные вычеты равны \(0,1,4\). Если \(n^2\equiv 1\pmod 5\), то \(n^2+9\equiv 0\pmod 5\). Если \(n^2\equiv 4\pmod 5\), то \(n^2+1\equiv 0\pmod 5\). Значит, остаётся только \(n^2\equiv 0\pmod 5\), то есть \(5\mid n\).
По модулю 3 число \(n\) не может делиться на 3, иначе \(n^2+3\), \(n^2+9\) и \(n^2+27\) делились бы на 3.
Самое сильное ограничение даёт модуль 7. Квадратичные вычеты mod 7 равны \(0,1,2,4\). При \(n^2\equiv 0\pmod 7\) число \(n^2+7\) делится на 7. При \(n^2\equiv 1\pmod 7\) получаем \(n^2+13\equiv 0\pmod 7\). При \(n^2\equiv 4\pmod 7\) имеем \(n^2+3\equiv 0\pmod 7\). Выживает только случай \(n^2\equiv 2\pmod 7\), что эквивалентно \(n\equiv \pm 3\pmod 7\).
Совмещая \(2\mid n\), \(5\mid n\) и \(n\equiv \pm 3\pmod 7\), получаем ровно две арифметические прогрессии: $$n\equiv 10 \pmod{70}\qquad\text{или}\qquad n\equiv 60 \pmod{70}.$$ Тот же аргумент по модулю 7 автоматически делает \(n^2+5\) и \(n^2+19\) кратными 7, так что две запрещённые позиции отбрасываются автоматически.
Самый маленький кандидат уже показывает всю структуру. Для \(n=10\) имеем \(n^2=100\). Тогда обязательные значения равны $$101,\ 103,\ 107,\ 109,\ 113,\ 127,$$ и все они простые. Запрещённые нечётные смещения дают $$105,\ 111,\ 115,\ 117,\ 119,\ 121,\ 123,\ 125,$$ и все эти числа составные. Значит, \(10\) действительно является допустимым решением.
Сведение к модулю 70 лишь первая ступень. Для каждого малого простого \(p\) до 2000 реализации заранее вычисляют множество плохих остатков $$R_p=\{r\in\{0,\dots,p-1\}: r^2+g\equiv 0\pmod p\text{ для некоторого }g\in G\}.$$ Если \(n\bmod p\in R_p\), то хотя бы одно из шести обязательных чисел делится на \(p\), и кандидат можно немедленно отбросить.
Простые 2 и 5 не включаются в эти таблицы, потому что их влияние уже учтено условием \(n\equiv 0\pmod{10}\). Для очень маленьких \(n\) сравнение \(n^2+g\equiv 0\pmod p\) ещё может означать \(n^2+g=p\), то есть простое число, а не составное. Поэтому реализации начинают применять предвычисленные таблицы только при \(n\ge 1000\), что является заведомо безопасным порогом.
После модульных фильтров остаётся совсем немного кандидатов. Для каждого из них выполняется точная проверка: шесть чисел \(n^2+g\) должны быть простыми, а восемь чисел \(n^2+c\) составными. Поскольку $$n^2+27 < (150{,}000{,}000)^2+27 < 2.25\times 10^{16},$$ все проверяемые значения уверенно помещаются в 64 бита, поэтому быстрые проверки простоты Миллера-Рабина полностью подходят для финального этапа.
Реализации на C++, Python и Java итерируются только по последовательностям \(70m+10\) и \(70m+60\). Это непосредственный выигрыш от анализа сравнений: вместо всех целых чисел остаётся примерно один кандидат из каждых 35.
Внутри одной прогрессии шаг всегда равен 70, поэтому квадрат поддерживается по рекуррентной формуле $$ (n+70)^2=n^2+140n+4900.$$ Аналогично поддерживаются и остатки по малым простым: зная текущий остаток modulo \(p\), следующий получают добавлением \(70\bmod p\). Благодаря этому просеивание сводится к дешёвым обращениям к таблицам, а не к повторным вычислениям квадратов по модулю.
Каждый кандидат проходит короткий конвейер: дешёвые проверки делимости на 3 и 13, обращение к предвычисленным таблицам плохих остатков, точные тесты простоты для шести обязательных смещений и точные проверки составности для восьми запрещённых. Если всё успешно, значение \(n\) добавляется к сумме.
Интервал поиска естественно разбивается на независимые блоки. Реализации на C++ и Java распараллеливают эти блоки напрямую, а реализация на Python тоже может распределять их между рабочими процессами. Математическое условие во всех трёх языках одинаково.
Пусть \(L\) обозначает верхнюю границу поиска, а \(B\) верхнюю границу для таблиц остатков по малым простым. Построение таблиц стоит \(O(B\log\log B+\sum_{p\le B} p)\) по времени и \(O(\sum_{p\le B} p)\) по памяти, поскольку для каждого простого \(p\) хранится булев массив длины \(p\).
Основной проход посещает только около \(L/35\) значений, потому что используются две классы вычетов по модулю 70. Для каждого кандидата требуется константная арифметика и одно обновление остатка на каждый простой фильтра; до этапа тестов простоты доходит лишь крошечная доля значений. При фиксированном \(B=2000\), как в реализациях, память остаётся небольшой, а время работы на практике ведёт себя почти линейно по \(L\).
المطلوب هو إيجاد مجموع كل الأعداد الصحيحة \(n < 150{,}000{,}000\) التي تجعل القيم الست $$n^2+1,\ n^2+3,\ n^2+7,\ n^2+9,\ n^2+13,\ n^2+27$$ أولية، بينما تكون القيم الفردية الواقعة بينها $$n^2+5,\ n^2+11,\ n^2+15,\ n^2+17,\ n^2+19,\ n^2+21,\ n^2+23,\ n^2+25$$ مركبة. وبما أن المسألة تطلب أن تكون هذه الأعداد الأولية متتالية داخل هذا المدى، فإن هذه القيم الثماني المستبعدة جزء أساسي من الشرط وليست تفصيلاً إضافياً.
الفحص المباشر لكل \(n\) سيكون مكلفًا جدًا، لأن الأعداد التي نختبر أوليتها تصل إلى مرتبة \(10^{16}\). لذلك تعتمد الفكرة الصحيحة على تضييق \(n\) أولًا إلى عدد صغير جدًا من أصناف البواقي، ثم استخدام جداول بواقي ممنوعة لعدد كبير من الأوليات الصغيرة، ثم إجراء اختبارات أولية دقيقة فقط على العدد القليل الذي ينجو من هذه المرشحات.
لنكتب $$G=\{1,3,7,9,13,27\},\qquad C=\{5,11,15,17,19,21,23,25\}.$$ عندئذ يكون \(n\) حلًا إذا وفقط إذا كانت \(n^2+g\) أولية لكل \(g\in G\)، وكانت \(n^2+c\) مركبة لكل \(c\in C\).
إذا كان \(n\) زوجيًا فإن \(n^2\) زوجي أيضًا. لذلك فإن أي إزاحة زوجية تعطي عددًا زوجيًا أكبر من 2، وهذا يعني أنه مركب تلقائيًا. لهذا السبب لا تحتاج الخوارزمية إلى فحص الإزاحات الزوجية أصلًا، بل تركز فقط على الإزاحات الفردية: ست إزاحات يجب أن تعطي أعدادًا أولية، وثماني إزاحات يجب أن تبقى مركبة.
قبل أي اختبار أولية فعلي، توجد حجج معيارية بسيطة تزيل معظم القيم الممكنة.
لو كان \(n\) فرديًا، لكان \(n^2+1\) عددًا زوجيًا أكبر من 2، وهذا مستحيل. إذن \(n\) يجب أن يكون زوجيًا.
بترديد 5 تكون البواقي التربيعية هي \(0,1,4\). إذا كان \(n^2\equiv 1\pmod 5\) فإن \(n^2+9\equiv 0\pmod 5\). وإذا كان \(n^2\equiv 4\pmod 5\) فإن \(n^2+1\equiv 0\pmod 5\). إذن الحالة الوحيدة الممكنة هي \(n^2\equiv 0\pmod 5\)، أي \(5\mid n\).
وبترديد 3، إذا كان \(n\) من مضاعفات 3 فستكون \(n^2+3\) و\(n^2+9\) و\(n^2+27\) قابلة للقسمة على 3. لذلك لا بد أن يكون \(3\nmid n\).
أقوى قيد يأتي من الترديد 7. البواقي التربيعية modulo 7 هي \(0,1,2,4\). إذا كان \(n^2\equiv 0\pmod 7\) فإن \(n^2+7\) يقبل القسمة على 7. وإذا كان \(n^2\equiv 1\pmod 7\) فإن \(n^2+13\equiv 0\pmod 7\). وإذا كان \(n^2\equiv 4\pmod 7\) فإن \(n^2+3\equiv 0\pmod 7\). الحالة الوحيدة التي تبقى هي \(n^2\equiv 2\pmod 7\)، وهذا يكافئ \(n\equiv \pm 3\pmod 7\).
بجمع الشروط \(2\mid n\) و\(5\mid n\) و\(n\equiv \pm 3\pmod 7\) نحصل على متتاليتين حسابيتين فقط: $$n\equiv 10 \pmod{70}\qquad\text{or}\qquad n\equiv 60 \pmod{70}.$$ والحجة نفسها modulo 7 تجعل \(n^2+5\) و\(n^2+19\) قابلين للقسمة على 7 تلقائيًا، وبالتالي يختفي شرطان من شروط التركيب من دون كلفة إضافية.
أصغر مرشح يوضح النمط كاملًا. عندما \(n=10\) يكون \(n^2=100\). عندها تصبح القيم المطلوبة $$101,\ 103,\ 107,\ 109,\ 113,\ 127,$$ وهي كلها أولية. أما الإزاحات الفردية الممنوعة فتعطي $$105,\ 111,\ 115,\ 117,\ 119,\ 121,\ 123,\ 125,$$ وكل هذه الأعداد مركبة. لذلك فإن \(10\) بالفعل حل صحيح، وهذا المثال يوضح بدقة ما الذي تبحث عنه الخوارزمية.
الاختزال إلى modulo 70 ليس سوى الطبقة الأولى. فلكل عدد أولي صغير \(p\) حتى 2000، تقوم التطبيقات بحساب مجموعة البواقي السيئة مسبقًا: $$R_p=\{r\in\{0,\dots,p-1\}:\exists g\in G,\ r^2+g\equiv 0\pmod p\}.$$ إذا تحقق \(n\bmod p\in R_p\)، فهذا يعني أن واحدًا على الأقل من القيم الست المطلوبة يقبل القسمة على \(p\)، وبالتالي يمكن استبعاد المرشح فورًا.
لا يدخل العددان الأوليان 2 و5 في هذه الجداول، لأن أثرهما قد حُسم أصلًا بواسطة الشرط \(n\equiv 0\pmod{10}\). أما عندما يكون \(n\) صغيرًا جدًا، فقد تعني العلاقة \(n^2+g\equiv 0\pmod p\) أن \(n^2+g=p\) نفسه، وفي هذه الحالة يكون العدد أوليًا لا مركبًا. لتجنب هذه الحالة الحدية، لا تفعّل التطبيقات هذه الجداول المسبقة إلا عندما \(n\ge 1000\)، وهو حد محافظ وآمن.
بعد المرشحات المعيارية يبقى عدد قليل جدًا من المرشحين. عندئذ يتم التحقق بدقة: يجب أن تكون القيم الست \(n^2+g\) أولية، ويجب أن تكون القيم الثماني \(n^2+c\) مركبة. وبما أن $$n^2+27 < (150{,}000{,}000)^2+27 < 2.25\times 10^{16},$$ فإن كل الأعداد المختبرة تقع بأمان داخل مجال 64 بت، ولذلك تصبح اختبارات Miller-Rabin السريعة مناسبة تمامًا للمرحلة الأخيرة.
تقوم تطبيقات C++ وPython وJava بالمرور فقط على المتتاليتين \(70m+10\) و\(70m+60\). هذا هو الأثر المباشر لتحليل التطابقات: بدلًا من فحص جميع الأعداد الصحيحة، تبدأ الخوارزمية منذ اللحظة الأولى بالاحتفاظ بنحو مرشح واحد فقط من كل 35 مرشحًا.
داخل كل متتالية يكون مقدار الزيادة ثابتًا ويساوي 70، لذلك يُحدَّث المربع بالعلاقة $$ (n+70)^2=n^2+140n+4900.$$ وهذا يمنع إعادة حساب \(n^2\) من الصفر في كل خطوة. والفكرة نفسها تُستعمل مع بواقي الغربال: إذا كانت الباقي الحالي modulo \(p\) معروفًا، فإن الباقي التالي يُستخرج بإضافة \(70\bmod p\). بهذه الطريقة تتحول مرحلة التصفية إلى عمليات جمع بسيطة ووصول سريع إلى جداول منطقية.
كل مرشح يمر عبر سلسلة قصيرة: اختبارات رخيصة للقسمة على 3 و13، ثم مراجعة جداول البواقي السيئة المحسوبة مسبقًا، ثم اختبارات أولية دقيقة للإزاحات الست المطلوبة، ثم اختبارات تركيب دقيقة للإزاحات الثماني الممنوعة. وإذا اجتاز المرشح كل هذه المراحل يُضاف \(n\) إلى المجموع.
يمكن تقسيم مجال البحث طبيعيًا إلى مقاطع مستقلة. تطبق نسختا C++ وJava هذا التقسيم على نحو متوازٍ مباشرة، كما يمكن لنسخة Python توزيع المقاطع على عمليات عاملة متعددة. الرياضيات نفسها ثابتة في اللغات الثلاث، والاختلاف فقط في طريقة التنفيذ.
لنرمز إلى حد البحث بـ \(L\)، وإلى حد جداول بواقي الأوليات الصغيرة بـ \(B\). بناء هذه الجداول يحتاج إلى زمن \(O(B\log\log B+\sum_{p\le B} p)\) وذاكرة \(O(\sum_{p\le B} p)\)، لأن كل عدد أولي \(p\) يملك مصفوفة منطقية بطول \(p\).
أما المسح الرئيسي فلا يزور إلا نحو \(L/35\) قيمة، لأنه يستخدم فئتين فقط من البواقي modulo 70. ولكل مرشح هناك عمليات حسابية ثابتة وتحديث واحد لكل باقي غربال، ولا يصل إلى مرحلة اختبار الأولية إلا جزء صغير جدًا من القيم. ومع الاختيار الثابت \(B=2000\) المستخدم في التطبيقات، تبقى الذاكرة صغيرة ويصبح زمن التنفيذ عمليًا شبه خطي في حد البحث.