The positive integers are written in triangular rows: row \(r\) contains \(r\) consecutive values, from \(T_{r-1}+1\) to \(T_r\), where \(T_r=\frac{r(r+1)}{2}\). For a fixed row \(n\), the quantity \(S(n)\) is the sum of those primes in row \(n\) that belong to at least one prime triplet under the problem's neighborhood rule.
The full task asks for \(S(5678027)+S(7208785)\). The key fact extracted from the implementations is that triplet membership is a purely local property: even for million-scale rows, the answer can be determined from a five-row strip centered on the target row.
It is convenient to index the triangle by row and column. For \(0 \le c < r\), let
$$a(r,c)=\frac{r(r-1)}{2}+1+c,$$
so \(a(r,c)\) is the value in row \(r\), column \(c\).
For each cell \((r,c)\), the implementations examine the clipped \(3\times3\) window
$$N(r,c)=\{(r+\Delta r,c+\Delta c): \Delta r,\Delta c\in\{-1,0,1\},\ 0\le c+\Delta c<r+\Delta r\}.$$
This set contains the center cell itself, the two horizontal neighbors in the same row when they exist, and up to three cells in the row above and three in the row below. Interior cells therefore have eight neighbors; boundary cells have fewer because invalid coordinates are discarded.
Let \(P(r,c)\) be 1 when \(a(r,c)\) is prime and 0 otherwise. Then the local prime count around \((r,c)\) is
$$M(r,c)=\sum_{(u,v)\in N(r,c)} P(u,v).$$
The implementations rely on the following equivalent characterization. A prime at \((r,c)\) can act as the center of a prime triplet exactly when \(P(r,c)=1\) and \(M(r,c)\ge 3\). The reason is that the count \(M(r,c)\) includes the center itself, so a value of at least 3 means there are at least two additional primes in the same neighborhood.
This immediately gives the marking rule used in code: if a prime center has \(M(r,c)\ge 3\), then every prime in \(N(r,c)\) belongs to at least one valid triplet. The center is already adjacent to all of them, and there is always at least one more prime in the same neighborhood to complete a three-prime configuration. So the problem is not just to find centers; it is to mark every prime lying inside a qualifying neighborhood.
Take any prime in row \(n\). If it belongs to a triplet, then either it is the center or it is adjacent to the center. In either case that center must lie in row \(n-1\), \(n\), or \(n+1\). Once the center is fixed, every cell in its neighborhood lies within one extra row, so all relevant values are contained in rows \(n-2\) through \(n+2\).
This is the central invariant of the solution. Instead of processing all values up to roughly \(\frac{n^2}{2}\), it is enough to inspect the exact interval covered by those five rows:
$$\left[\frac{(n-2)(n-3)}{2}+1,\ \frac{(n+2)(n+3)}{2}\right].$$
The total number of cells in that strip is
$$ (n-2)+(n-1)+n+(n+1)+(n+2)=5n,$$
so the relevant search space is linear in \(n\).
Because the five-row strip is a contiguous block of integers, primality is determined with a segmented sieve on that interval. Only primes up to
$$\sqrt{\frac{(n+2)(n+3)}{2}}$$
are needed to cross out all composites. After sieving, the flat boolean array is projected back into five jagged rows, one for each triangular row from \(n-2\) to \(n+2\).
With that notation, the answer can be expressed as
$$S(n)=\sum_{c=0}^{n-1} a(n,c)\,G(n,c),$$
where \(G(n,c)=1\) exactly when \(a(n,c)\) is prime and lies inside \(N(r,d)\) for some prime center \((r,d)\) with \(r\in\{n-1,n,n+1\}\) and \(M(r,d)\ge 3\).
The small checkpoint rows show the method clearly. Row 8 is \(29,30,31,32,33,34,35,36\), while row 9 is \(37,38,39,40,41,42,43,44,45\). Consider the prime 23 in row 7. Its clipped neighborhood contains the numbers \(16,17,18,22,23,24,29,30,31\), and the primes among them are \(17,23,29,31\). Since that neighborhood already contains at least three primes, both 29 and 31 are certified as members of prime triplets, so \(S(8)=29+31=60\).
For row 9, the prime 37 lies at the left edge, so its neighborhood is smaller: \(29,30,37,38,46,47\). The prime subset is \(29,37,47\), which is still enough to form a triplet. By contrast, the primes 41 and 43 never appear inside any qualifying neighborhood of size at least three primes, so they do not contribute. Hence \(S(9)=37\). The large target rows are solved by exactly the same local logic.
The C++, Python, and Java implementations first compute the start and end of the interval covering rows \(n-2\) through \(n+2\). They generate all base primes up to the square root of the interval endpoint, then mark composites inside the interval itself. The result is a primality table for every value that can possibly affect \(S(n)\).
Next, the flat segmented-sieve array is mapped back into five row-shaped boolean arrays. One array records which cells are prime, and a second array records which prime cells have already been proved to belong to at least one triplet. This layout mirrors the triangular geometry, so neighborhood scans become simple bounded loops instead of repeated coordinate arithmetic on absolute values.
The implementations inspect only the middle three rows, because only those rows can contain a triplet center relevant to row \(n\). For each prime cell in those rows, the code counts primes in the clipped \(3\times3\) neighborhood. If the count is at least three, every prime in that neighborhood is marked. A final pass over row \(n\) sums exactly the marked primes.
The three languages differ only in low-level representation and in how the small supporting primes are generated. The mathematical workflow is the same in every version.
The active interval has length exactly \(5n\), and every later step works only inside that strip. The neighborhood phase is linear as well: there are \(3n\) candidate-center positions in rows \(n-1\), \(n\), and \(n+1\), and each one inspects at most nine cells.
Using a standard segmented sieve, the running time is \(O(n \log \log n)\) in the usual sieve model, followed by an \(O(n)\) marking and summation pass. Extra space is \(O(n)\) for the interval primality array and the two five-row masks. The decisive optimization is locality: the algorithm never touches the whole triangle up to row \(n\), only the narrow strip that can influence the answer.
Die positiven ganzen Zahlen werden zeilenweise in einer Dreiecksstruktur angeordnet: Zeile \(r\) enthält \(r\) aufeinanderfolgende Werte, nämlich von \(T_{r-1}+1\) bis \(T_r\), wobei \(T_r=\frac{r(r+1)}{2}\) gilt. Für eine feste Zeile \(n\) ist \(S(n)\) die Summe genau der Primzahlen in dieser Zeile, die zu mindestens einem Prime-Triplet gemäß der Nachbarschaftsregel des Problems gehören.
Im eigentlichen Problem wird \(S(5678027)+S(7208785)\) verlangt. Die entscheidende Beobachtung aus allen drei Implementierungen lautet: Die Zugehörigkeit zu einem Prime-Triplet ist vollständig lokal. Selbst bei sehr großen Zeilen genügt ein Fenster aus fünf Zeilen um die Zielzeile.
Es ist zweckmäßig, die Dreiecksanordnung mit Zeilen- und Spaltenkoordinaten zu beschreiben. Für \(0 \le c < r\) setzen wir
$$a(r,c)=\frac{r(r-1)}{2}+1+c,$$
also den Wert in Zeile \(r\), Spalte \(c\).
Für jede Zelle \((r,c)\) betrachten die Implementierungen das beschnittene \(3\times3\)-Fenster
$$N(r,c)=\{(r+\Delta r,c+\Delta c): \Delta r,\Delta c\in\{-1,0,1\},\ 0\le c+\Delta c<r+\Delta r\}.$$
Diese Menge enthält die Zelle selbst, die beiden horizontalen Nachbarn derselben Zeile sofern vorhanden sowie bis zu drei Zellen in der darüberliegenden und drei in der darunterliegenden Zeile. Im Inneren gibt es also acht Nachbarn; am Rand fallen ungültige Koordinaten weg.
Sei \(P(r,c)\) die Primindikatorfunktion, also 1 für prim und 0 sonst. Dann ist die lokale Anzahl von Primzahlen um \((r,c)\)
$$M(r,c)=\sum_{(u,v)\in N(r,c)} P(u,v).$$
Die Implementierungen benutzen die äquivalente Formulierung: Eine Primzahl an Position \((r,c)\) kann genau dann Zentrum eines Prime-Triplets sein, wenn \(P(r,c)=1\) und \(M(r,c)\ge 3\) gilt. Der Zähler \(M(r,c)\) enthält die Primzahl selbst, also bedeutet \(M(r,c)\ge 3\), dass es mindestens zwei weitere Primzahlen in derselben Nachbarschaft gibt.
Daraus folgt sofort die Markierungsregel des Programms: Hat ein Primzentrum \(M(r,c)\ge 3\), dann gehört jede Primzahl in \(N(r,c)\) zu mindestens einem gültigen Triplet. Das Zentrum ist zu allen diesen Primzahlen benachbart, und wegen der Bedingung \(M(r,c)\ge 3\) existiert immer noch eine weitere Primzahl, die das Dreiermuster vervollständigt. Deshalb zählt der Algorithmus nicht nur Zentren, sondern markiert sämtliche Primzahlen in qualifizierenden Nachbarschaften.
Betrachte eine Primzahl in Zeile \(n\). Gehört sie zu einem Triplet, dann ist sie entweder selbst das Zentrum oder direkt an das Zentrum benachbart. In beiden Fällen liegt dieses Zentrum in Zeile \(n-1\), \(n\) oder \(n+1\). Sobald das Zentrum feststeht, liegen alle Zellen seiner Nachbarschaft höchstens eine weitere Zeile entfernt. Also befinden sich alle relevanten Werte in den Zeilen \(n-2\) bis \(n+2\).
Das ist die tragende Invariante der Lösung. Statt alle Werte bis ungefähr \(\frac{n^2}{2}\) zu betrachten, genügt das exakte Intervall dieser fünf Zeilen:
$$\left[\frac{(n-2)(n-3)}{2}+1,\ \frac{(n+2)(n+3)}{2}\right].$$
Die Gesamtzahl der Zellen in diesem Streifen ist
$$ (n-2)+(n-1)+n+(n+1)+(n+2)=5n,$$
also nur linear in \(n\).
Weil diese fünf Zeilen einen zusammenhängenden Block ganzer Zahlen bilden, wird die Primzahleigenschaft mit einem segmentierten Sieb direkt auf diesem Intervall bestimmt. Zum Streichen aller zusammengesetzten Zahlen genügen Primzahlen bis
$$\sqrt{\frac{(n+2)(n+3)}{2}}.$$
Anschließend wird das flache Bool-Array wieder in fünf Zeilenarrays zurückprojiziert, die den Zeilen \(n-2\) bis \(n+2\) entsprechen.
Damit lässt sich die gesuchte Summe schreiben als
$$S(n)=\sum_{c=0}^{n-1} a(n,c)\,G(n,c),$$
wobei \(G(n,c)=1\) genau dann ist, wenn \(a(n,c)\) prim ist und in einer Nachbarschaft \(N(r,d)\) eines Primzentrums \((r,d)\) mit \(r\in\{n-1,n,n+1\}\) und \(M(r,d)\ge 3\) liegt.
Die kleinen Kontrollwerte zeigen die Methode besonders klar. Zeile 8 lautet \(29,30,31,32,33,34,35,36\), Zeile 9 lautet \(37,38,39,40,41,42,43,44,45\). Betrachte die Primzahl 23 in Zeile 7. Ihre beschnittene Nachbarschaft besteht aus \(16,17,18,22,23,24,29,30,31\), und die Primzahlen darunter sind \(17,23,29,31\). Diese Nachbarschaft enthält also bereits mindestens drei Primzahlen; damit sind 29 und 31 als Mitglieder von Prime-Triplets zertifiziert, also \(S(8)=29+31=60\).
Für Zeile 9 liegt die Primzahl 37 am linken Rand, deshalb ist ihre Nachbarschaft kleiner: \(29,30,37,38,46,47\). Die Primzahlen darin sind \(29,37,47\), also wieder genug für ein Triplet. Dagegen tauchen 41 und 43 in keiner qualifizierenden Nachbarschaft mit mindestens drei Primzahlen auf und werden daher nicht gezählt. Folglich ist \(S(9)=37\). Genau dieselbe lokale Logik trägt auch die riesigen Zielzeilen.
Die Implementierungen in C++, Python und Java bestimmen zunächst Anfang und Ende des Intervalls, das die Zeilen \(n-2\) bis \(n+2\) überdeckt. Dann erzeugen sie alle Hilfsprimzahlen bis zur Quadratwurzel des rechten Endpunkts und markieren mit ihnen die zusammengesetzten Zahlen innerhalb des Intervalls. Das Ergebnis ist eine Primtabelle für jeden Wert, der \(S(n)\) überhaupt beeinflussen kann.
Danach wird das flache Segment-Sieb in fünf zeilenförmige Bool-Arrays übersetzt. Ein Array speichert, welche Zellen prim sind, ein zweites speichert, welche Primzellen bereits als Mitglieder eines Triplets nachgewiesen wurden. Diese Darstellung passt zur Geometrie des Dreiecks und macht die Nachbarschaftsprüfung zu einfachen kleinen Schleifen.
Untersucht werden nur die mittleren drei Zeilen, denn nur dort kann ein für Zeile \(n\) relevantes Zentrum liegen. Für jede Primzelle in diesen Zeilen zählt die Implementierung die Primzahlen in der beschnittenen \(3\times3\)-Nachbarschaft. Ist der Zähler mindestens 3, werden alle Primzahlen dieser Nachbarschaft markiert. Ein letzter Durchlauf über Zeile \(n\) summiert genau die markierten Primzahlen.
Die drei Sprachen unterscheiden sich nur in Datenstrukturen und kleineren Details der Primzahl-Erzeugung. Der mathematische Ablauf ist identisch.
Das aktive Intervall hat exakt die Länge \(5n\), und auch alle späteren Schritte bleiben auf diesen Streifen beschränkt. Die Nachbarschaftsphase ist ebenfalls linear: In den Zeilen \(n-1\), \(n\) und \(n+1\) gibt es zusammen \(3n\) Kandidatenzentren, und pro Zentrum werden höchstens neun Zellen geprüft.
Mit einem segmentierten Sieb ergibt sich damit eine Laufzeit von \(O(n \log \log n)\) im üblichen Siebmodell, gefolgt von einem \(O(n)\)-Durchlauf zum Markieren und Summieren. Der Zusatzspeicher ist \(O(n)\) für das Intervall-Sieb und die beiden Fünf-Zeilen-Masken. Die entscheidende Optimierung ist die Lokalität: Der Algorithmus verarbeitet nie das ganze Dreieck bis Zeile \(n\), sondern nur den schmalen Streifen, der das Ergebnis beeinflussen kann.
Pozitif tam sayılar üçgensel satırlara yazılır: \(r\). satırda tam olarak \(r\) tane ardışık sayı vardır ve bu satır \(T_{r-1}+1\) ile \(T_r\) arasında gider; burada \(T_r=\frac{r(r+1)}{2}\) üçgensel sayısıdır. Sabit bir \(n\) için \(S(n)\), \(n\). satırdaki ve problemdeki komşuluk kuralına göre en az bir prime triplet yapısına dahil olan asal sayıların toplamıdır.
Asıl hedef \(S(5678027)+S(7208785)\) toplamını bulmaktır. Üç uygulamanın ortak verdiği ana fikir şudur: bir asalın prime triplet üyesi olup olmaması tamamen yereldir. Milyonlar düzeyindeki satırlar için bile hedef satırın etrafındaki beş satırlık pencere yeterlidir.
Üçgensel tabloyu satır-sütun koordinatlarıyla yazmak faydalıdır. \(0 \le c < r\) için
$$a(r,c)=\frac{r(r-1)}{2}+1+c$$
olsun; bu, \(r\). satırın \(c\). sütunundaki gerçek sayıdır.
Her \((r,c)\) hücresi için uygulamalar kırpılmış \(3\times3\) pencereyi inceler:
$$N(r,c)=\{(r+\Delta r,c+\Delta c): \Delta r,\Delta c\in\{-1,0,1\},\ 0\le c+\Delta c<r+\Delta r\}.$$
Bu küme merkez hücrenin kendisini, varsa aynı satırdaki iki yatay komşuyu, üst satırdan en fazla üç hücreyi ve alt satırdan en fazla üç hücreyi içerir. İç bölgede bir hücrenin sekiz komşusu vardır; kenarlarda geçersiz koordinatlar atıldığı için bu sayı azalır.
\(P(r,c)\), \(a(r,c)\) asal ise 1, değilse 0 olsun. O zaman \((r,c)\) etrafındaki yerel asal sayısı
$$M(r,c)=\sum_{(u,v)\in N(r,c)} P(u,v)$$
şeklindedir.
Uygulamaların kullandığı eşdeğer karakterizasyon şudur: \((r,c)\) noktasındaki bir asal ancak ve ancak \(P(r,c)=1\) ve \(M(r,c)\ge 3\) ise bir prime triplet'in merkezi olabilir. Çünkü \(M(r,c)\) sayımı merkezin kendisini de içerir; dolayısıyla en az 3 olması, aynı komşuluk içinde en az iki ek asal daha bulunduğu anlamına gelir.
Buradan kodun işaretleme kuralı doğrudan çıkar. Bir asal merkez için \(M(r,c)\ge 3\) ise, \(N(r,c)\) içindeki her asal en az bir geçerli triplet'e aittir. Merkez bunların hepsiyle komşudur ve aynı pencerede yapıyı tamamlayacak en az bir başka asal daha vardır. Bu yüzden algoritma yalnızca merkezleri saymaz; uygun bir komşuluğun içindeki bütün asalları işaretler.
\(n\). satırdaki herhangi bir asalı ele alalım. Bu asal bir triplet'e dahilse ya merkezin kendisidir ya da merkeze komşu olan iki asaldan biridir. Her iki durumda da merkez ancak \(n-1\), \(n\) veya \(n+1\). satırda olabilir. Merkez sabitlendiğinde onun komşuluk penceresi en fazla bir satır daha uzağa uzanır. Demek ki ilgili bütün hücreler \(n-2\) ile \(n+2\) arasındaki satırlardadır.
Çözümün temel değişmezi budur. Yaklaşık \(\frac{n^2}{2}\) büyüklüğündeki tüm ön üçgeni incelemek yerine yalnızca şu kesin aralık yeterlidir:
$$\left[\frac{(n-2)(n-3)}{2}+1,\ \frac{(n+2)(n+3)}{2}\right].$$
Bu şeritteki toplam hücre sayısı
$$ (n-2)+(n-1)+n+(n+1)+(n+2)=5n$$
olduğundan, gerçekten ilgili veri büyüklüğü \(n\) ile lineerdir.
Beş satırlık şerit ardışık tam sayılardan oluştuğu için asal testi doğrudan bu aralık üzerinde segmented sieve ile yapılır. Bileşik sayıları elemek için yalnızca
$$\sqrt{\frac{(n+2)(n+3)}{2}}$$
değerine kadar olan asal çarpanlar gerekir. Eleme tamamlandıktan sonra düz mantık dizisi tekrar beş satırlık, satır uzunlukları farklı olan yapılara dönüştürülür.
Böylece cevap
$$S(n)=\sum_{c=0}^{n-1} a(n,c)\,G(n,c)$$
şeklinde yazılabilir. Burada \(G(n,c)=1\), ancak ve ancak \(a(n,c)\) asal ise ve \(r\in\{n-1,n,n+1\}\) olacak şekilde \(M(r,d)\ge 3\) koşulunu sağlayan asal bir merkez \((r,d)\) için \((n,c)\in N(r,d)\) ise gerçekleşir.
Küçük kontrol değerleri yöntemi somutlaştırır. 8. satır \(29,30,31,32,33,34,35,36\), 9. satır ise \(37,38,39,40,41,42,43,44,45\) biçimindedir. 7. satırdaki 23 asalını düşünelim. Onun kırpılmış komşuluğu \(16,17,18,22,23,24,29,30,31\) sayılarından oluşur ve bunların asalları \(17,23,29,31\)'dir. Yani bu pencere zaten en az üç asal içerir; dolayısıyla 29 ve 31 prime triplet üyesi olarak kesinleşir ve \(S(8)=29+31=60\) olur.
9. satır için 37 sol sınırda bulunduğundan komşuluğu daha küçüktür: \(29,30,37,38,46,47\). Buradaki asal kümesi \(29,37,47\)'dir ve bu da geçerli bir triplet için yeterlidir. Buna karşılık 41 ve 43, en az üç asal içeren hiçbir uygun komşulukta görünmez; bu yüzden toplama girmezler. Sonuç olarak \(S(9)=37\) olur. Milyonluk satırlarda da yapılan şey tam olarak budur.
C++, Python ve Java uygulamaları önce \(n-2\) ile \(n+2\) satırlarını kapsayan aralığın başlangıç ve bitişini hesaplar. Ardından aralığın sağ ucunun kareköküne kadar gerekli yardımcı asalları üretir ve bunlarla aralık içindeki bileşikleri işaretler. Böylece \(S(n)\)'i etkileyebilecek her sayı için bir asallık tablosu elde edilir.
Daha sonra düz segmented-sieve dizisi tekrar beş satırlık bir yapıya çevrilir. Bir mantık dizisi hangi hücrelerin asal olduğunu, paralel ikinci bir dizi ise hangi asal hücrelerin en az bir triplet'in üyesi olduğunun kanıtlandığını tutar. Bu yerleşim üçgensel geometriyle uyumlu olduğu için komşuluk taramaları küçük sınırlı döngülere indirgenir.
Yalnızca ortadaki üç satır incelenir; çünkü hedef satır açısından anlamlı bir merkez ancak orada bulunabilir. Bu satırlardaki her asal hücre için kırpılmış \(3\times3\) komşulukta kaç asal olduğu sayılır. Sayı en az 3 ise, o komşuluk içindeki bütün asallar işaretlenir. Son geçişte \(n\). satırda işaretlenmiş olan asallar toplanır.
Üç dil arasındaki farklar yalnızca veri yapıları ve küçük asal üretme ayrıntılarıdır. Matematiksel iş akışı aynıdır.
Aktif aralık tam olarak \(5n\) uzunluğundadır ve sonraki tüm adımlar da sadece bu şerit içinde kalır. Komşuluk taraması da lineerdir: \(n-1\), \(n\) ve \(n+1\). satırlarda toplam \(3n\) merkez adayı vardır ve her biri en fazla dokuz hücreye bakar.
Standart segmented sieve varsayımıyla toplam çalışma süresi olağan sieve modelinde \(O(n \log \log n)\), son işaretleme ve toplama geçişi ise \(O(n)\) olur. Ek bellek kullanımı, aralık üzerindeki asallık dizisi ve iki adet beş satırlık maske için \(O(n)\)'dir. Asıl kazanç yerelliktir: algoritma \(n\). satıra kadar olan tüm üçgeni değil, yalnızca cevabı etkileyebilen dar şeridi işler.
Los enteros positivos se escriben en filas triangulares: la fila \(r\) contiene \(r\) valores consecutivos, desde \(T_{r-1}+1\) hasta \(T_r\), con \(T_r=\frac{r(r+1)}{2}\). Para una fila fija \(n\), \(S(n)\) es la suma de los primos de esa fila que pertenecen al menos a un prime triplet según la regla de vecindad del problema.
La tarea completa pide \(S(5678027)+S(7208785)\). La observación decisiva, común a las tres implementaciones, es que pertenecer a un triplete es una propiedad estrictamente local: incluso para filas enormes basta una franja de cinco filas centrada en la fila objetivo.
Conviene describir el triángulo con coordenadas de fila y columna. Para \(0 \le c < r\), definimos
$$a(r,c)=\frac{r(r-1)}{2}+1+c,$$
que es el valor situado en la fila \(r\), columna \(c\).
Para cada celda \((r,c)\), las implementaciones examinan la ventana recortada de \(3\times3\)
$$N(r,c)=\{(r+\Delta r,c+\Delta c): \Delta r,\Delta c\in\{-1,0,1\},\ 0\le c+\Delta c<r+\Delta r\}.$$
Ese conjunto contiene la propia celda, los dos vecinos horizontales de la misma fila cuando existen, y hasta tres celdas en la fila superior y tres en la inferior. Las celdas interiores tienen por tanto ocho vecinos; en los bordes la cantidad baja porque las coordenadas inválidas se descartan.
Sea \(P(r,c)\) igual a 1 si \(a(r,c)\) es primo y 0 en caso contrario. Entonces el número local de primos alrededor de \((r,c)\) es
$$M(r,c)=\sum_{(u,v)\in N(r,c)} P(u,v).$$
Las implementaciones usan la caracterización equivalente siguiente. Un primo en \((r,c)\) puede actuar como centro de un prime triplet exactamente cuando \(P(r,c)=1\) y \(M(r,c)\ge 3\). Como \(M(r,c)\) incluye al propio centro, pedir al menos 3 significa que en la misma vecindad hay al menos otros dos primos.
De ahí sale la regla de marcado del algoritmo. Si un centro primo cumple \(M(r,c)\ge 3\), entonces todo primo dentro de \(N(r,c)\) pertenece a por lo menos un triplete válido. El centro es vecino de todos ellos y, además, siempre existe otro primo en la misma ventana para completar la configuración de tres. Por eso el programa no solo identifica centros; marca todos los primos contenidos en vecindades que califican.
Toma un primo de la fila \(n\). Si pertenece a un triplete, entonces o bien es el centro, o bien es uno de los dos primos adyacentes al centro. En ambos casos el centro debe estar en la fila \(n-1\), \(n\) o \(n+1\). Una vez fijado el centro, toda su vecindad queda contenida a una fila adicional de distancia. Por tanto, todos los valores relevantes están entre las filas \(n-2\) y \(n+2\).
Ese es el invariante principal de la solución. En vez de procesar todos los valores hasta aproximadamente \(\frac{n^2}{2}\), basta el intervalo exacto cubierto por esas cinco filas:
$$\left[\frac{(n-2)(n-3)}{2}+1,\ \frac{(n+2)(n+3)}{2}\right].$$
El número total de celdas en esa franja es
$$ (n-2)+(n-1)+n+(n+1)+(n+2)=5n,$$
de modo que el espacio realmente activo es lineal en \(n\).
Como la franja de cinco filas forma un bloque continuo de enteros, la primalidad se calcula con una criba segmentada directamente sobre ese intervalo. Solo hacen falta los primos hasta
$$\sqrt{\frac{(n+2)(n+3)}{2}}$$
para tachar todos los compuestos. Después de la criba, el arreglo booleano plano se vuelve a proyectar sobre cinco filas irregulares, una por cada fila triangular entre \(n-2\) y \(n+2\).
Con esta notación, la respuesta se escribe como
$$S(n)=\sum_{c=0}^{n-1} a(n,c)\,G(n,c),$$
donde \(G(n,c)=1\) exactamente cuando \(a(n,c)\) es primo y pertenece a \(N(r,d)\) para algún centro primo \((r,d)\) con \(r\in\{n-1,n,n+1\}\) y \(M(r,d)\ge 3\).
Los valores pequeños de control muestran bien la idea. La fila 8 es \(29,30,31,32,33,34,35,36\), y la fila 9 es \(37,38,39,40,41,42,43,44,45\). Considera el primo 23 en la fila 7. Su vecindad recortada contiene \(16,17,18,22,23,24,29,30,31\), y los primos allí son \(17,23,29,31\). Esa vecindad ya tiene al menos tres primos, así que 29 y 31 quedan certificados como miembros de tripletes; por eso \(S(8)=29+31=60\).
Para la fila 9, el primo 37 está en el borde izquierdo y su vecindad es más pequeña: \(29,30,37,38,46,47\). El subconjunto primo es \(29,37,47\), suficiente para formar un triplete. En cambio, 41 y 43 no aparecen nunca dentro de una vecindad válida con al menos tres primos, así que se excluyen. Por eso \(S(9)=37\). Las filas gigantes se resuelven con exactamente el mismo argumento local.
Las implementaciones en C++, Python y Java calculan primero el inicio y el final del intervalo que cubre las filas \(n-2\) a \(n+2\). Luego generan todos los primos auxiliares hasta la raíz cuadrada del extremo derecho y con ellos marcan los compuestos dentro del intervalo. El resultado es una tabla de primalidad para cada valor que puede influir en \(S(n)\).
Después, el arreglo plano de la criba segmentada se convierte otra vez en cinco arreglos booleanos con forma de fila. Uno guarda qué celdas son primas; el otro guarda qué celdas primas ya quedaron demostradas como parte de algún triplete. Esta representación coincide con la geometría del triángulo y hace que el barrido local sea un conjunto de bucles pequeños y acotados.
Solo se inspeccionan las tres filas centrales, porque solo allí puede estar un centro relevante para la fila \(n\). Para cada celda prima de esas filas, el código cuenta cuántos primos hay en la vecindad recortada de \(3\times3\). Si el conteo es al menos 3, se marcan todos los primos de esa vecindad. Una pasada final por la fila \(n\) suma exactamente los primos marcados.
Las tres versiones difieren solo en detalles de representación y en la forma de generar los primos auxiliares. El flujo matemático es idéntico.
El intervalo activo tiene longitud exacta \(5n\), y todos los pasos posteriores permanecen dentro de esa franja. La fase de vecindad también es lineal: en las filas \(n-1\), \(n\) y \(n+1\) hay en total \(3n\) posibles centros, y cada uno inspecciona como mucho nueve celdas.
Con una criba segmentada estándar, el tiempo total es \(O(n \log \log n)\) en el modelo habitual de cribas, seguido de una pasada \(O(n)\) para marcar y sumar. El espacio extra es \(O(n)\) para el arreglo de primalidad del intervalo y las dos máscaras de cinco filas. La optimización decisiva es la localidad: el algoritmo nunca toca todo el triángulo hasta la fila \(n\), solo la franja estrecha que puede afectar la respuesta.
正整数按三角形方式排列：第 \(r\) 行恰好有 \(r\) 个连续整数，从 \(T_{r-1}+1\) 到 \(T_r\)，其中 \(T_r=\frac{r(r+1)}{2}\)。对于固定的行号 \(n\)，\(S(n)\) 定义为第 \(n\) 行中那些至少属于一个 prime triplet 的素数之和，这里的“属于”完全按照题目的邻接规则来判断。
最终要求是求 \(S(5678027)+S(7208785)\)。三份实现共同揭示的关键点是：prime triplet 成员资格是一个纯粹的局部性质。哪怕目标行大到数百万级，也完全不需要处理到第 \(n\) 行为止的整个大三角，只要围绕目标行截取五行即可。
把这个三角阵写成行列坐标最清楚。对 \(0 \le c < r\)，定义
$$a(r,c)=\frac{r(r-1)}{2}+1+c,$$
表示第 \(r\) 行第 \(c\) 列上的实际数值。
对于每个单元格 \((r,c)\)，实现都会检查一个经过边界裁剪的 \(3\times3\) 局部窗口：
$$N(r,c)=\{(r+\Delta r,c+\Delta c): \Delta r,\Delta c\in\{-1,0,1\},\ 0\le c+\Delta c<r+\Delta r\}.$$
这个集合包括中心格本身、同一行中左右两个水平邻居（如果存在）、上一行最多三个格子、下一行最多三个格子。位于内部的格子因此会有八个邻居；位于边界时，超出范围的坐标被舍弃，邻居数量就会减少。
记 \(P(r,c)\) 为素性指示函数：如果 \(a(r,c)\) 是素数，则 \(P(r,c)=1\)，否则为 0。于是 \((r,c)\) 周围的局部素数个数就是
$$M(r,c)=\sum_{(u,v)\in N(r,c)} P(u,v).$$
三份实现都依赖同一个等价条件：\((r,c)\) 位置上的素数能够充当某个 prime triplet 的中心，当且仅当 \(P(r,c)=1\) 且 \(M(r,c)\ge 3\)。原因很直接，因为 \(M(r,c)\) 把中心本身也算进去了，所以 \(M(r,c)\ge 3\) 恰好表示在同一局部邻域里还能再找到至少两个素数。
这立刻导出代码中的标记规则。如果一个素数中心满足 \(M(r,c)\ge 3\)，那么 \(N(r,c)\) 中的每一个素数都属于至少一个有效 triplet。中心与这些素数全部相邻，而邻域里又至少还有另一个素数可以把三元组补齐。所以算法并不是只统计“中心点”，而是把所有落在合格邻域中的素数都标记为有效成员。
考虑第 \(n\) 行中的某个素数。如果它属于某个 triplet，那么它要么就是中心，要么就是与中心相邻的两个素数之一。无论哪种情况，那个中心所在的行号都只能是 \(n-1\)、\(n\) 或 \(n+1\)。而一旦中心固定，它的整个邻域又只会再多跨出一行。因此，所有真正相关的格子必然都落在第 \(n-2\) 行到第 \(n+2\) 行之间。
这就是整套解法的核心不变量。我们不需要处理大约到 \(\frac{n^2}{2}\) 的全部数，只要处理这五行对应的精确连续区间：
$$\left[\frac{(n-2)(n-3)}{2}+1,\ \frac{(n+2)(n+3)}{2}\right].$$
这条五行条带中一共只有
$$ (n-2)+(n-1)+n+(n+1)+(n+2)=5n$$
个格子，所以真正活跃的数据规模只是 \(n\) 的线性量级。
因为这五行恰好对应一段连续整数，所以可以直接在该区间上做 segmented sieve。要筛掉全部合数，只需要预先得到不超过
$$\sqrt{\frac{(n+2)(n+3)}{2}}$$
的素数。筛完以后，再把这一段平铺的一维布尔数组重新映射回五个长度不同的“行数组”。
在这种记号下，答案可以写成
$$S(n)=\sum_{c=0}^{n-1} a(n,c)\,G(n,c),$$
其中 \(G(n,c)=1\) 当且仅当 \(a(n,c)\) 本身是素数，并且存在某个素数中心 \((r,d)\)，满足 \(r\in\{n-1,n,n+1\}\)、\(M(r,d)\ge 3\)，而且 \((n,c)\in N(r,d)\)。
小样例最能说明方法。第 8 行是 \(29,30,31,32,33,34,35,36\)，第 9 行是 \(37,38,39,40,41,42,43,44,45\)。先看第 7 行的素数 23。它的裁剪邻域包含 \(16,17,18,22,23,24,29,30,31\)，其中素数是 \(17,23,29,31\)。这个邻域已经有至少三个素数，因此 29 和 31 都会被认定为某个 prime triplet 的成员，于是 \(S(8)=29+31=60\)。
再看第 9 行的 37。由于它在左边界，邻域更小，只包含 \(29,30,37,38,46,47\)。其中素数集合是 \(29,37,47\)，仍然足以构成有效 triplet。相比之下，41 和 43 从未落入任何“至少有三个素数”的合格邻域，因此不会被计入。于是 \(S(9)=37\)。真正的大行号计算和这个例子的逻辑完全一样，只是数值范围更大。
C++、Python 和 Java 实现都会先算出覆盖第 \(n-2\) 行到第 \(n+2\) 行的连续区间左右端点。接着先生成不超过区间右端平方根的基础素数，再在目标区间内部标记合数。这样得到的就是所有可能影响 \(S(n)\) 的数的素性表。
完成分段筛之后，程序把平铺的一维布尔数组重新拆成五个按行存储的布尔数组。第一组数组记录哪些位置是素数，第二组数组记录哪些素数已经被证明属于至少一个 triplet。这样的数据布局直接对应三角形几何结构，因此后续邻域扫描只需要固定范围的小循环。
程序只检查中间三行，因为只有那三行里的素数才可能成为与目标行有关的 triplet 中心。对于每一个候选素数中心，代码统计其裁剪 \(3\times3\) 邻域内的素数个数。如果计数至少为 3，就把该邻域中的所有素数都标记为有效。最后只需扫一遍第 \(n\) 行，把被标记的素数加总起来。
三种语言实现的差别只在底层容器和基础素数生成方式上，数学流程完全一致。
活动区间的长度精确等于 \(5n\)，后续所有步骤也都只在这条窄条带内进行。邻域扫描同样是线性的：第 \(n-1\)、\(n\)、\(n+1\) 三行一共只有 \(3n\) 个候选中心，而每个中心最多检查九个格子。
采用标准分段筛时，整体时间复杂度在通常的筛法模型下可写成 \(O(n \log \log n)\)，之后再加一个 \(O(n)\) 的标记与求和过程。额外空间复杂度是 \(O(n)\)，用于保存区间素性数组以及两个五行掩码。最关键的优化是“局部性”：算法从头到尾都不会触碰到第 \(n\) 行之前的整个大三角，只处理真正可能影响答案的那五行。
Положительные целые числа записаны треугольными строками: строка \(r\) содержит \(r\) последовательных значений от \(T_{r-1}+1\) до \(T_r\), где \(T_r=\frac{r(r+1)}{2}\). Для фиксированной строки \(n\) величина \(S(n)\) равна сумме тех простых чисел из строки \(n\), которые входят хотя бы в один prime triplet по правилу соседства из задачи.
В полной задаче требуется вычислить \(S(5678027)+S(7208785)\). Главный вывод из всех трех реализаций состоит в том, что принадлежность простого числа к triplet является чисто локальным свойством. Даже для огромных строк достаточно рассмотреть только полоску из пяти строк вокруг целевой.
Удобно ввести координаты строки и столбца. Для \(0 \le c < r\) положим
$$a(r,c)=\frac{r(r-1)}{2}+1+c,$$
то есть это значение в строке \(r\), столбце \(c\).
Для каждой клетки \((r,c)\) реализации рассматривают усеченное окно \(3\times3\)
$$N(r,c)=\{(r+\Delta r,c+\Delta c): \Delta r,\Delta c\in\{-1,0,1\},\ 0\le c+\Delta c<r+\Delta r\}.$$
Это множество содержит саму клетку, двух горизонтальных соседей в той же строке при их наличии, а также до трех клеток в строке выше и до трех в строке ниже. Внутренние клетки имеют восемь соседей; на границе часть координат выходит за допустимый диапазон и отбрасывается.
Пусть \(P(r,c)\) равно 1, если \(a(r,c)\) простое, и 0 иначе. Тогда локальное число простых в окрестности равно
$$M(r,c)=\sum_{(u,v)\in N(r,c)} P(u,v).$$
Реализации опираются на следующий эквивалентный факт. Простое число в позиции \((r,c)\) может быть центром prime triplet тогда и только тогда, когда \(P(r,c)=1\) и \(M(r,c)\ge 3\). Поскольку \(M(r,c)\) учитывает сам центр, условие \(M(r,c)\ge 3\) означает наличие по крайней мере двух дополнительных простых в той же окрестности.
Отсюда сразу получается правило пометки, используемое в коде. Если простое центрическое число удовлетворяет \(M(r,c)\ge 3\), то каждое простое из \(N(r,c)\) принадлежит хотя бы одному допустимому triplet. Центр соседствует со всеми этими простыми, а еще в той же окрестности всегда есть хотя бы одно дополнительное простое, завершающее тройку. Поэтому алгоритм не просто ищет центры, а помечает все простые внутри квалифицирующей окрестности.
Возьмем простое число из строки \(n\). Если оно входит в triplet, то либо оно само является центром, либо оно одно из двух простых, соседних с центром. В любом случае центр может лежать только в строке \(n-1\), \(n\) или \(n+1\). После фиксации центра вся его окрестность уходит максимум еще на одну строку вверх или вниз. Значит, все релевантные клетки находятся между строками \(n-2\) и \(n+2\).
Это и есть главный инвариант решения. Вместо обработки всех чисел до примерно \(\frac{n^2}{2}\) достаточно взять точный непрерывный интервал, покрывающий эти пять строк:
$$\left[\frac{(n-2)(n-3)}{2}+1,\ \frac{(n+2)(n+3)}{2}\right].$$
Общее число клеток в этой полосе равно
$$ (n-2)+(n-1)+n+(n+1)+(n+2)=5n,$$
то есть реально активный объем данных линейный по \(n\).
Так как пять нужных строк образуют непрерывный блок целых чисел, проверка на простоту делается сегментированным решетом прямо на этом интервале. Чтобы вычеркнуть все составные, достаточно иметь простые числа до
$$\sqrt{\frac{(n+2)(n+3)}{2}}.$$
После просеивания плоский булев массив снова раскладывается в пять массивов разной длины, соответствующих строкам \(n-2,\dots,n+2\).
В этих обозначениях ответ записывается так:
$$S(n)=\sum_{c=0}^{n-1} a(n,c)\,G(n,c),$$
где \(G(n,c)=1\) тогда и только тогда, когда \(a(n,c)\) простое и лежит внутри \(N(r,d)\) для некоторого простого центра \((r,d)\) с \(r\in\{n-1,n,n+1\}\) и условием \(M(r,d)\ge 3\).
Малые контрольные значения хорошо иллюстрируют метод. Строка 8 равна \(29,30,31,32,33,34,35,36\), а строка 9 равна \(37,38,39,40,41,42,43,44,45\). Рассмотрим простое 23 в строке 7. Его усеченная окрестность состоит из чисел \(16,17,18,22,23,24,29,30,31\), а простые среди них — \(17,23,29,31\). Значит, в этой окрестности уже есть как минимум три простых, поэтому 29 и 31 гарантированно входят в prime triplet, и потому \(S(8)=29+31=60\).
Для строки 9 простое 37 стоит на левом краю, поэтому его окрестность меньше: \(29,30,37,38,46,47\). Простые там — \(29,37,47\), чего достаточно для triplet. А вот 41 и 43 никогда не попадают ни в одну подходящую окрестность с тремя простыми, поэтому не учитываются. Следовательно, \(S(9)=37\). Для огромных целевых строк используется ровно та же локальная логика.
Реализации на C++, Python и Java сначала вычисляют начало и конец интервала, покрывающего строки \(n-2\) до \(n+2\). Затем они строят все вспомогательные простые до квадратного корня из правой границы и с их помощью помечают составные числа внутри самого интервала. Так получается таблица простоты для каждого значения, способного повлиять на \(S(n)\).
После этого плоский массив сегментированного решета преобразуется обратно в пять булевых массивов построчной формы. Один массив хранит признаки простоты, второй — признаки того, что данное простое уже доказано как член хотя бы одного triplet. Такое представление соответствует геометрии треугольника и делает локальный просмотр окрестностей простой системой коротких циклов.
Просматриваются только три средние строки, потому что только в них может находиться центр, влияющий на строку \(n\). Для каждой простой клетки в этих строках код считает число простых в усеченной окрестности \(3\times3\). Если счетчик не меньше 3, все простые из этой окрестности помечаются. Финальный проход по строке \(n\) суммирует ровно помеченные простые.
Три языковые версии различаются только контейнерами и деталями генерации вспомогательных простых. Математическая схема одна и та же.
Длина активного интервала в точности равна \(5n\), и все последующие шаги тоже ограничены этой полосой. Фаза просмотра окрестностей также линейна: в строках \(n-1\), \(n\) и \(n+1\) вместе имеется \(3n\) возможных центров, а для каждого проверяется не более девяти клеток.
При стандартном сегментированном решете итоговая трудоемкость равна \(O(n \log \log n)\) в обычной модели решета, после чего идет еще один проход \(O(n)\) на пометку и суммирование. Дополнительная память составляет \(O(n)\) для массива простоты на интервале и двух пятистрочных масок. Ключевая оптимизация здесь — локальность: алгоритм никогда не обрабатывает весь треугольник до строки \(n\), а только узкую полосу, которая вообще может повлиять на ответ.
تُرتَّب الأعداد الصحيحة الموجبة في صفوف مثلثية: الصف \(r\) يحتوي على \(r\) أعداد متتالية من \(T_{r-1}+1\) حتى \(T_r\)، حيث \(T_r=\frac{r(r+1)}{2}\). ولصف ثابت \(n\)، تُعرَّف \(S(n)\) بأنها مجموع الأعداد الأولية في الصف \(n\) التي تنتمي إلى prime triplet واحد على الأقل وفق قاعدة الجوار الموجودة في المسألة.
الهدف الكامل هو حساب \(S(5678027)+S(7208785)\). والفكرة الحاسمة المشتركة بين الحلول الثلاثة هي أن الانتماء إلى triplet أولي خاصية محلية بالكامل. حتى عندما تكون الصفوف بحجم الملايين، يكفي النظر إلى شريط مكوَّن من خمسة صفوف حول الصف المطلوب.
من الأنسب وصف المثلث بإحداثيات صف وعمود. إذا كان \(0 \le c < r\)، فنعرّف
$$a(r,c)=\frac{r(r-1)}{2}+1+c,$$
وهو العدد الموجود في الصف \(r\) والعمود \(c\).
لكل خلية \((r,c)\)، تفحص التطبيقات نافذة \(3\times3\) مقصوصة بالحدود:
$$N(r,c)=\{(r+\Delta r,c+\Delta c): \Delta r,\Delta c\in\{-1,0,1\},\ 0\le c+\Delta c<r+\Delta r\}.$$
هذه المجموعة تحتوي على الخلية نفسها، والجارتين الأفقيتين في الصف نفسه إن وُجدتا، وحتى ثلاث خلايا في الصف الأعلى وثلاث خلايا في الصف الأسفل. لذلك تملك الخلايا الداخلية ثمانية جيران، بينما يقل العدد على الحواف لأن الإحداثيات غير الصالحة تُهمل.
لتكن \(P(r,c)\) مساوية لـ 1 إذا كان \(a(r,c)\) أوليًا، و0 خلاف ذلك. عندئذ يكون عدد الأوليات في الجوار المحلي حول \((r,c)\) هو
$$M(r,c)=\sum_{(u,v)\in N(r,c)} P(u,v).$$
تعتمد التطبيقات على الصياغة المكافئة التالية: يكون العدد الأولي عند \((r,c)\) مركزًا محتملًا لـ prime triplet إذا وفقط إذا كان \(P(r,c)=1\) و\(M(r,c)\ge 3\). والسبب أن \(M(r,c)\) يحسب المركز نفسه، لذا فإن الشرط \(M(r,c)\ge 3\) يعني وجود أوليين إضافيين على الأقل في الجوار نفسه.
ومن هنا تأتي قاعدة التعليم في الشيفرة. إذا كان مركز أولي يحقق \(M(r,c)\ge 3\)، فإن كل عدد أولي داخل \(N(r,c)\) ينتمي إلى triplet صحيح واحد على الأقل. فالمركز جارٌ لجميع هذه الأوليات، وهناك دائمًا أولي آخر داخل النافذة نفسها لإكمال مجموعة من ثلاثة أوليات. لذلك لا يكتفي الحل باكتشاف المراكز، بل يعلّم كل الأوليات الواقعة داخل جوار مؤهَّل.
خذ عددًا أوليًا في الصف \(n\). إذا كان هذا العدد جزءًا من triplet، فهو إما المركز نفسه أو أحد العددين الأوليين المجاورين للمركز. وفي الحالتين لا يمكن أن يكون المركز إلا في الصف \(n-1\) أو \(n\) أو \(n+1\). وبعد تثبيت المركز، لا يمتد جواره إلا صفًا إضافيًا واحدًا صعودًا أو هبوطًا. لذلك فإن كل الخلايا ذات الصلة محصورة بين الصفين \(n-2\) و\(n+2\).
هذا هو الثابت الأساسي في الحل. بدل معالجة جميع الأعداد حتى نحو \(\frac{n^2}{2}\)، يكفي التعامل مع المجال المتصل الدقيق الذي تغطيه هذه الصفوف الخمسة:
$$\left[\frac{(n-2)(n-3)}{2}+1,\ \frac{(n+2)(n+3)}{2}\right].$$
ومجموع عدد الخلايا في هذا الشريط يساوي
$$ (n-2)+(n-1)+n+(n+1)+(n+2)=5n,$$
أي إن حجم البيانات الفعلي خطي في \(n\).
بما أن الشريط ذي الصفوف الخمسة يشكّل كتلة متصلة من الأعداد الصحيحة، فإن اختبار الأولية يتم مباشرة بواسطة segmented sieve على هذا المجال. ولا نحتاج لشطب جميع المركبات إلا إلى الأوليات التي لا تتجاوز
$$\sqrt{\frac{(n+2)(n+3)}{2}}.$$
بعد الغربلة، يُعاد إسقاط المصفوفة المنطقية المسطحة إلى خمسة صفوف ذات أطوال مختلفة، كل واحد منها يمثل صفًا من الصفوف \(n-2\) إلى \(n+2\).
وبهذا الترميز يمكن كتابة الجواب على الصورة
$$S(n)=\sum_{c=0}^{n-1} a(n,c)\,G(n,c),$$
حيث \(G(n,c)=1\) إذا وفقط إذا كان \(a(n,c)\) أوليًا ويقع داخل \(N(r,d)\) لمركز أولي \((r,d)\) يحقق \(r\in\{n-1,n,n+1\}\) و\(M(r,d)\ge 3\).
القيم الصغيرة التحققية توضّح الفكرة جيدًا. الصف 8 هو \(29,30,31,32,33,34,35,36\)، والصف 9 هو \(37,38,39,40,41,42,43,44,45\). لننظر إلى العدد الأولي 23 في الصف 7. جواره المقصوص يحتوي على \(16,17,18,22,23,24,29,30,31\)، والأعداد الأولية بينها هي \(17,23,29,31\). بما أن هذا الجوار يحتوي بالفعل على ثلاثة أوليات على الأقل، فإن 29 و31 يُعتمدان عضوين في prime triplet، ومن ثم \(S(8)=29+31=60\).
أما في الصف 9، فالعدد 37 يقع على الحافة اليسرى، ولذلك يكون جواره أصغر: \(29,30,37,38,46,47\). والأوليات هناك هي \(29,37,47\)، وهذا يكفي لتكوين triplet صالح. في المقابل، لا يظهر 41 ولا 43 داخل أي جوار مؤهل يحوي ثلاثة أوليات على الأقل، ولذلك لا يدخلان في المجموع. وهكذا نحصل على \(S(9)=37\). والمنطق نفسه يُطبَّق حرفيًا على الصفوف الضخمة المطلوبة في المسألة.
تحسب تطبيقات C++ وPython وJava أولًا بداية ونهاية المجال الذي يغطي الصفوف من \(n-2\) إلى \(n+2\). ثم تولّد جميع الأوليات المساعدة حتى الجذر التربيعي للطرف الأيمن، وتستخدمها لتمييز المركبات داخل المجال نفسه. والنتيجة هي جدول أولية لكل قيمة يمكن أن تؤثر في \(S(n)\).
بعد ذلك تُحوَّل مصفوفة الغربال المقطعي المسطحة إلى خمسة صفوف منطقية. الصف الأول يسجل أي الخلايا أولية، والصف الثاني يسجل أي الخلايا الأولية ثبت أنها تنتمي إلى triplet واحد على الأقل. هذا التمثيل يطابق الهندسة المثلثية مباشرة، ولذلك تصبح فحوص الجوار مجرد حلقات صغيرة محدودة.
لا تُفحَص إلا الصفوف الثلاثة الوسطى، لأن المركز الذي يمكن أن يؤثر في الصف \(n\) لا بد أن يقع فيها. ولكل خلية أولية في تلك الصفوف، تعدّ الشيفرة عدد الأوليات في الجوار المقصوص \(3\times3\). فإذا كان العدد 3 على الأقل، تُعلَّم جميع الأوليات الموجودة في ذلك الجوار. ثم يمر البرنامج مرورًا أخيرًا على الصف \(n\) ليجمع فقط الأوليات المعلَّمة.
الاختلافات بين اللغات الثلاث محصورة في التمثيل منخفض المستوى وفي تفاصيل توليد الأوليات المساعدة. أما سير العمل الرياضي فواحد تمامًا.
طول المجال النشط يساوي بالضبط \(5n\)، وجميع الخطوات اللاحقة تبقى داخل هذا الشريط. كما أن مرحلة فحص الجوار خطية أيضًا: ففي الصفوف \(n-1\) و\(n\) و\(n+1\) يوجد معًا \(3n\) مركزًا مرشحًا، وكل واحد منها يفحص في أقصى الأحوال تسع خلايا.
وباستخدام segmented sieve قياسي، يكون زمن التنفيذ الكلي \(O(n \log \log n)\) في نموذج الغربال المعتاد، ثم تتبعه مرحلة تعليم وجمع بكلفة \(O(n)\). أما الذاكرة الإضافية فهي \(O(n)\) لتخزين أولية المجال والقناعين الخاصين بالصفوف الخمسة. والتحسين الحاسم هنا هو المحلية: الخوارزمية لا تلمس المثلث كله حتى الصف \(n\)، بل الشريط الضيق الوحيد القادر على التأثير في الجواب.