For each positive integer \(n\), define \(p(n)\) to be the first prime \(p\) for which
$$ (n \bmod p)\bmod 7 \ne 0. $$
Equivalently, every earlier prime \(q<p(n)\) must satisfy \(n \bmod q \in \{0,7,14,\dots\}\), and \(p(n)\) is the first prime where that pattern breaks. The quantity to compute is
$$ A(N)=\sum_{n=1}^{N} p(n), $$
with the actual input \(N=10^{17}\). A direct search over all \(n\) is impossible. The successful idea is to group integers by congruence classes and move those classes from prime to prime.
The solution processes primes in increasing order and keeps track of the integers that have survived every test so far.
Let \(p_1=2,p_2=3,\dots\) be the primes. After all primes up to \(p_k\) have been checked, define
$$ S_k=\{n\le N : n \bmod q \in \{0,7,14,\dots\}\text{ for every prime } q\le p_k\}. $$
These are exactly the numbers whose first failing prime is still larger than \(p_k\). If we write \(C_k=|S_k|\), then the numbers that disappear when the next prime \(p\) is processed contribute
$$ p\,(C_k-C_{k+1}) $$
to the final sum, because all of them satisfy \(p(n)=p\). So the entire problem becomes: update the survivor set efficiently and count it after each prime.
After processing a prime prefix, set
$$ M_k=\prod_{q\le p_k} q. $$
Whether \(n\) belongs to \(S_k\) depends only on its remainders modulo the processed primes, so it depends only on \(n \pmod{M_k}\). That means \(S_k\) can be represented by a finite list of surviving residue classes \(r \pmod{M_k}\).
For a new prime \(p\), the allowed remainders are the multiples of \(7\) below \(p\):
$$ \mathcal{A}_p=\{0,7,14,\dots\}\cap[0,p-1]. $$
There are only \(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\) such residues. For small primes \(p<7\), the only allowed remainder is \(0\), so the early stages simply enforce divisibility by \(2\), then \(3\), then \(5\), then \(7\).
Suppose \(r \pmod{M_k}\) is a surviving class, and let \(a\in\mathcal{A}_p\) be an allowed residue modulo the next prime \(p\). We need the integers satisfying
$$ x\equiv r \pmod{M_k},\qquad x\equiv a \pmod p. $$
Write \(x=r+M_k t\). Then \(t\) must solve
$$ M_k t \equiv a-r \pmod p. $$
Because \(p\) is a new prime, \(\gcd(M_k,p)=1\), so \(M_k\) has an inverse modulo \(p\). Hence
$$ t\equiv (a-r)\,M_k^{-1}\pmod p, $$
and every pair \((r,a)\) produces one unique child residue modulo \(M_kp\):
$$ x\equiv r+M_k t \pmod{M_kp}. $$
This is the crucial compression step. Instead of testing every integer one by one, the algorithm lifts only the residue classes that are still alive.
Once a class \(r \pmod M\) is known to survive, its members in \([1,N]\) are easy to count. If \(r>0\), the class contributes
$$ r,\ r+M,\ r+2M,\dots, $$
so the count is
$$ \operatorname{cnt}(r;M)=\left\lfloor\dfrac{N-r}{M}\right\rfloor+1. $$
If \(r=0\), then the actual positive integers are
$$ M,\ 2M,\ 3M,\dots, $$
because \(0\) itself is outside the range, so
$$ \operatorname{cnt}(0;M)=\left\lfloor\dfrac{N}{M}\right\rfloor. $$
When \(M>N\), every nonzero residue can contribute at most one integer, namely the residue itself, and the zero residue contributes none. That explains the special branch used once the running modulus has become larger than the search interval.
After processing the primes \(2,3,5,7\), the only allowed residue at each step is \(0\). Therefore every surviving integer must be divisible by
$$ 2\cdot 3\cdot 5\cdot 7=210, $$
so the survivor set is just the single class \(0 \pmod{210}\).
Now process the prime \(11\). The allowed residues are \(0\) and \(7\). The pair
$$ x\equiv 0 \pmod{210},\qquad x\equiv 0 \pmod{11} $$
gives \(x\equiv 0 \pmod{2310}\). The pair
$$ x\equiv 0 \pmod{210},\qquad x\equiv 7 \pmod{11} $$
gives \(x\equiv 1470 \pmod{2310}\), because \(210\equiv 1 \pmod{11}\), so \(t\equiv 7\) and \(x=210\cdot 7\). Thus after prime \(11\), the surviving classes are
$$ 0 \pmod{2310}\quad\text{and}\quad 1470 \pmod{2310}. $$
If \(N=1470\), the first class contributes nothing because \(2310>N\), while the second contributes the single integer \(1470\). This example shows both the CRT lifting rule and the counting rule once the modulus has crossed \(N\).
The C++, Python, and Java implementations begin by generating a moderate list of primes. They keep four evolving quantities: the current prime product \(M\), the canonical surviving residues modulo \(M\), the number of integers in \([1,N]\) represented by those residues, and the running value of \(A(N)\).
For each prime \(p\), the implementation computes the inverse of \(M\bmod p\), enumerates the allowed residues \(0,7,14,\dots<p\), and creates every lifted residue modulo \(Mp\). It then counts how many integers up to \(N\) belong to those new classes. The difference between the previous survivor count and the new one is exactly the number of integers whose first failing prime is \(p\), so the code adds \(p\) times that difference to the answer. Once \(M>N\), any lift with a nonzero shift would already exceed \(N\), so those branches are skipped immediately. The process stops as soon as no survivors remain. The C++ implementation uses 128-bit arithmetic for the large products and totals, Python relies on arbitrary-precision integers, and the Java implementation uses big integers where fixed-width arithmetic would overflow.
Let \(R_k\) be the number of surviving residue classes after the \(k\)-th prime has been processed. If the next prime is \(p\), producing the next layer costs
$$ O\!\left(R_k\left(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\right)\right), $$
because each active residue is combined with every multiple of \(7\) below \(p\). Counting the next population is linear in the number of new residues, and the prime sieve itself is tiny by comparison.
The important point is that the algorithm never iterates over all integers up to \(N\). Its time and memory depend on the peak number of active residue classes, not on \(10^{17}\) itself. In practice the survivor population collapses quickly, so memory usage stays at \(O(\max_k R_k)\) and the computation remains manageable.
Für jede positive ganze Zahl \(n\) sei \(p(n)\) die erste Primzahl \(p\), für die
$$ (n \bmod p)\bmod 7 \ne 0 $$
gilt. Anders gesagt: Für jede kleinere Primzahl \(q<p(n)\) muss der Rest \(n \bmod q\) ein Vielfaches von \(7\) sein, also in \(\{0,7,14,\dots\}\) liegen, und erst bei \(p(n)\) bricht diese Eigenschaft zum ersten Mal. Gesucht ist
$$ A(N)=\sum_{n=1}^{N} p(n), $$
wobei in der eigentlichen Aufgabe \(N=10^{17}\) ist. Ein direktes Durchprobieren aller \(n\) ist völlig unbrauchbar. Die Lösung bündelt stattdessen ganze Kongruenzklassen und verfolgt nur deren Entwicklung.
Die Primzahlen werden der Reihe nach verarbeitet, und nach jedem Schritt wird festgehalten, welche Zahlen bislang alle Tests bestanden haben.
Seien \(p_1=2,p_2=3,\dots\) die Primzahlen. Nach allen Primzahlen bis \(p_k\) definieren wir
$$ S_k=\{n\le N : n \bmod q \in \{0,7,14,\dots\}\text{ für jede Primzahl } q\le p_k\}. $$
Das ist genau die Menge der Zahlen, deren erste scheiternde Primzahl noch größer als \(p_k\) ist. Schreiben wir \(C_k=|S_k|\), dann tragen die Zahlen, die beim nächsten Prime \(p\) ausscheiden, den Betrag
$$ p\,(C_k-C_{k+1}) $$
zur Endsumme bei, denn für sie gilt \(p(n)=p\). Damit reduziert sich alles auf zwei Aufgaben: die Überlebenden effizient aktualisieren und ihre Anzahl nach jedem Schritt bestimmen.
Nach einem Primzahlpräfix setzen wir
$$ M_k=\prod_{q\le p_k} q. $$
Ob \(n\) zu \(S_k\) gehört, hängt nur von seinen Resten modulo der bereits verarbeiteten Primzahlen ab und damit nur von \(n \pmod{M_k}\). Also kann \(S_k\) als endliche Liste überlebender Restklassen \(r \pmod{M_k}\) gespeichert werden.
Für eine neue Primzahl \(p\) sind genau die Vielfachen von \(7\) unterhalb von \(p\) erlaubt:
$$ \mathcal{A}_p=\{0,7,14,\dots\}\cap[0,p-1]. $$
Davon gibt es nur \(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\) Stück. Für kleine Primzahlen \(p<7\) ist sogar nur der Rest \(0\) zulässig, weshalb die ersten Schritte einfach Teilbarkeit durch \(2\), \(3\), \(5\) und \(7\) erzwingen.
Sei \(r \pmod{M_k}\) eine überlebende Klasse und \(a\in\mathcal{A}_p\) ein erlaubter Rest modulo der nächsten Primzahl \(p\). Gesucht sind die Zahlen mit
$$ x\equiv r \pmod{M_k},\qquad x\equiv a \pmod p. $$
Schreibe \(x=r+M_k t\). Dann muss \(t\) die Kongruenz
$$ M_k t \equiv a-r \pmod p $$
erfüllen. Weil \(p\) neu ist, gilt \(\gcd(M_k,p)=1\), also besitzt \(M_k\) ein Inverses modulo \(p\). Daher
$$ t\equiv (a-r)\,M_k^{-1}\pmod p, $$
und jedes Paar \((r,a)\) liefert genau eine Kindklasse modulo \(M_kp\):
$$ x\equiv r+M_k t \pmod{M_kp}. $$
Genau hier liegt die Verdichtung der Methode: Nicht einzelne Zahlen werden getestet, sondern nur die Restklassen, die noch nicht ausgeschieden sind.
Wenn eine Klasse \(r \pmod M\) überlebt, dann liegen ihre Vertreter in \([1,N]\) für \(r>0\) bei
$$ r,\ r+M,\ r+2M,\dots, $$
also ist ihre Anzahl
$$ \operatorname{cnt}(r;M)=\left\lfloor\dfrac{N-r}{M}\right\rfloor+1. $$
Für \(r=0\) sind die positiven Vertreter
$$ M,\ 2M,\ 3M,\dots, $$
weil \(0\) selbst nicht zum Summationsbereich gehört, also
$$ \operatorname{cnt}(0;M)=\left\lfloor\dfrac{N}{M}\right\rfloor. $$
Sobald \(M>N\) geworden ist, kann jede von \(0\) verschiedene Restklasse höchstens noch eine Zahl beitragen, nämlich den Rest selbst, und die Klasse \(0\) trägt gar nichts mehr bei. Genau deshalb schalten die Implementierungen dann auf einen einfacheren Zählzweig um.
Nach den Primzahlen \(2,3,5,7\) ist in jedem Schritt nur der Rest \(0\) erlaubt. Damit muss jede überlebende Zahl durch
$$ 2\cdot 3\cdot 5\cdot 7=210 $$
teilbar sein, also besteht die Überlebendenmenge nur aus der einen Klasse \(0 \pmod{210}\).
Als Nächstes kommt die Primzahl \(11\). Die erlaubten Reste sind \(0\) und \(7\). Das Paar
$$ x\equiv 0 \pmod{210},\qquad x\equiv 0 \pmod{11} $$
liefert \(x\equiv 0 \pmod{2310}\). Das Paar
$$ x\equiv 0 \pmod{210},\qquad x\equiv 7 \pmod{11} $$
liefert \(x\equiv 1470 \pmod{2310}\), denn \(210\equiv 1 \pmod{11}\), also ist \(t\equiv 7\) und damit \(x=210\cdot 7\). Nach der Primzahl \(11\) bleiben also genau die beiden Klassen
$$ 0 \pmod{2310}\quad\text{und}\quad 1470 \pmod{2310}. $$
Für \(N=1470\) trägt die erste Klasse nichts bei, weil \(2310>N\), während die zweite genau die Zahl \(1470\) enthält. Dieses Beispiel zeigt sowohl das CRT-Anheben als auch die Zählregel nach dem Überschreiten von \(N\).
Die C++-, Python- und Java-Implementierungen erzeugen zunächst eine moderate Primzahlliste. Während des Laufs halten sie vier Größen fest: das aktuelle Primprodukt \(M\), die kanonischen überlebenden Restklassen modulo \(M\), die Anzahl der in \([1,N]\) liegenden Zahlen in diesen Klassen und den aktuellen Wert von \(A(N)\).
Für jede neue Primzahl \(p\) wird das Inverse von \(M\bmod p\) bestimmt, dann werden die erlaubten Reste \(0,7,14,\dots<p\) durchlaufen und alle Kindklassen modulo \(Mp\) erzeugt. Anschließend wird gezählt, wie viele Zahlen bis \(N\) in diesen neuen Klassen liegen. Die Differenz zwischen alter und neuer Überlebendenzahl ist genau die Zahl der Werte, deren erste schlechte Primzahl \(p\) ist, also wird \(p\) mal diese Differenz zur Antwort addiert. Sobald \(M>N\) gilt, würden alle Anhebungen mit nichtverschobenem Rest außer dem Fall ohne Verschiebung schon oberhalb von \(N\) liegen; diese Zweige werden deshalb sofort verworfen. Der Prozess endet, sobald keine Überlebenden mehr vorhanden sind. Die C++-Version nutzt 128-Bit-Arithmetik für große Produkte und Summen, Python arbeitet mit beliebiger Genauigkeit, und die Java-Version verwendet große Ganzzahlen, sobald feste Wortbreiten nicht mehr ausreichen.
Sei \(R_k\) die Zahl der überlebenden Restklassen nach der \(k\)-ten Primzahl. Ist \(p\) die nächste Primzahl, dann kostet der Aufbau der nächsten Stufe
$$ O\!\left(R_k\left(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\right)\right), $$
weil jede aktive Klasse mit jedem Vielfachen von \(7\) unterhalb von \(p\) kombiniert wird. Das Zählen der neuen Population ist linear in der Zahl der neu erzeugten Klassen; die Primzahlsiebung ist dagegen vernachlässigbar klein.
Der entscheidende Vorteil ist, dass das Verfahren niemals alle Zahlen bis \(N\) einzeln besucht. Zeit- und Speicherverbrauch hängen vom Maximum der aktiven Restklassen ab, nicht direkt von \(10^{17}\). In der Praxis schrumpft die Überlebendenmenge schnell, daher bleibt der Speicherbedarf bei \(O(\max_k R_k)\) und die Laufzeit gut beherrschbar.
Her pozitif tam sayı \(n\) için,
$$ (n \bmod p)\bmod 7 \ne 0 $$
koşulunu sağlayan ilk asal \(p\) değeri \(p(n)\) ile tanımlanır. Eşdeğer olarak, \(p(n)\)'den küçük her asal \(q\) için \(n \bmod q\) değeri \(\{0,7,14,\dots\}\) kümesinde, yani \(7\)'nin katı olmak zorundadır; bu düzenin ilk bozulduğu asal ise \(p(n)\)'dir. Hesaplanacak büyüklük
$$ A(N)=\sum_{n=1}^{N} p(n), $$
ve gerçek giriş \(N=10^{17}\)'dir. Tüm \(n\) değerlerini tek tek dolaşmak pratik değildir. Çözüm, sayıları tekil adaylar olarak değil, sağ kalmış artık sınıfları olarak izler.
Asallar artan sırayla işlenir ve her aşamada o ana kadarki tüm testleri geçmiş sayılar tutulur.
\(p_1=2,p_2=3,\dots\) asallar olsun. \(p_k\)'ye kadar olan tüm asallar işlendiğinde
$$ S_k=\{n\le N : n \bmod q \in \{0,7,14,\dots\}\text{ her asal } q\le p_k\text{ için}\} $$
kümesini tanımlarız. Bu küme tam olarak ilk başarısız asalının hâlâ \(p_k\)'den büyük olduğu sayılardan oluşur. \(C_k=|S_k|\) yazarsak, bir sonraki asal \(p\) işlendiğinde elenen sayılar toplam cevaba
$$ p\,(C_k-C_{k+1}) $$
katkısını yapar; çünkü bu sayıların hepsi için \(p(n)=p\) olur. Dolayısıyla problem, sağ kalan kümeyi verimli biçimde güncelleyip her adımdan sonra saymaya indirgenir.
Bir asal öneki işlendiğinde
$$ M_k=\prod_{q\le p_k} q $$
olsun. \(n\)'in \(S_k\) içinde olup olmaması yalnızca işlenen asallara göre kalanlarına, yani yalnızca \(n \pmod{M_k}\)'ye bağlıdır. Bu yüzden \(S_k\), \(M_k\) modunda sağ kalan artık sınıflarının sonlu bir listesiyle temsil edilebilir.
Yeni bir asal \(p\) geldiğinde izinli kalanlar, \(p\)'den küçük \(7\) katlarıdır:
$$ \mathcal{A}_p=\{0,7,14,\dots\}\cap[0,p-1]. $$
Bunların sayısı sadece \(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\) kadardır. Özellikle \(p<7\) iken tek izinli kalan \(0\)'dır; bu nedenle ilk aşamalar yalnızca \(2\), sonra \(3\), sonra \(5\), sonra da \(7\) ile bölünebilirliği zorlar.
\(r \pmod{M_k}\) bir sağ kalan sınıf ve \(a\in\mathcal{A}_p\) yeni asal \(p\) modunda izinli bir kalan olsun. Aradığımız sayılar
$$ x\equiv r \pmod{M_k},\qquad x\equiv a \pmod p $$
koşullarını sağlar. \(x=r+M_k t\) yazarsak, \(t\) için
$$ M_k t \equiv a-r \pmod p $$
gerekir. \(p\) yeni bir asal olduğu için \(\gcd(M_k,p)=1\) ve \(M_k\)'nin \(p\) modunda tersi vardır. Bu yüzden
$$ t\equiv (a-r)\,M_k^{-1}\pmod p, $$
ve her \((r,a)\) çifti \(M_kp\) modunda tam bir çocuk sınıf üretir:
$$ x\equiv r+M_k t \pmod{M_kp}. $$
Asıl sıkıştırma burada gerçekleşir: algoritma her tamsayıyı ayrı ayrı sınamak yerine yalnızca hâlâ yaşayan artık sınıflarını bir sonraki moda taşır.
\(r \pmod M\) sınıfı sağ kalıyorsa ve \(r>0\) ise ilgili pozitif sayılar
$$ r,\ r+M,\ r+2M,\dots $$
şeklindedir; dolayısıyla sayı adedi
$$ \operatorname{cnt}(r;M)=\left\lfloor\dfrac{N-r}{M}\right\rfloor+1 $$
olur. \(r=0\) için pozitif temsilciler
$$ M,\ 2M,\ 3M,\dots $$
olduğu için, \(0\) aralığın dışında kaldığından
$$ \operatorname{cnt}(0;M)=\left\lfloor\dfrac{N}{M}\right\rfloor $$
elde edilir. \(M>N\) olduğunda sıfırdan farklı her artık sınıfı en fazla bir sayı verir, o da artık değerin kendisidir; sıfır sınıfı ise hiç sayı vermez. Kodun, modül \(N\)'i geçtikten sonra daha basit bir sayım dalına geçmesinin sebebi budur.
\(2,3,5,7\) asalları işlendiğinde her adımda yalnızca kalan \(0\) izinlidir. Bu yüzden her sağ kalan sayı
$$ 2\cdot 3\cdot 5\cdot 7=210 $$
ile bölünebilir olmalıdır; yani sağ kalan küme tek bir sınıftan, \(0 \pmod{210}\)'dan ibarettir.
Sıradaki asal \(11\)'dir. İzinli kalanlar \(0\) ve \(7\)'dir. Şu ikili
$$ x\equiv 0 \pmod{210},\qquad x\equiv 0 \pmod{11} $$
bize \(x\equiv 0 \pmod{2310}\) verir. Şu ikili ise
$$ x\equiv 0 \pmod{210},\qquad x\equiv 7 \pmod{11} $$
\(x\equiv 1470 \pmod{2310}\) sonucunu verir; çünkü \(210\equiv 1 \pmod{11}\), dolayısıyla \(t\equiv 7\) ve \(x=210\cdot 7\) olur. Böylece \(11\)'den sonra sağ kalan sınıflar tam olarak
$$ 0 \pmod{2310}\quad\text{ve}\quad 1470 \pmod{2310} $$
olur. Eğer \(N=1470\) ise ilk sınıf hiçbir katkı yapmaz; çünkü \(2310>N\). İkinci sınıf ise yalnızca \(1470\) sayısını içerir. Bu örnek hem CRT yükseltmesini hem de modül \(N\)'i geçtikten sonraki sayım kuralını gösterir.
C++, Python ve Java uygulamaları önce makul büyüklükte bir asal listesi üretir. Ardından dört büyüklüğü güncelleyerek ilerler: mevcut asal çarpımı \(M\), \(M\) modundaki kanonik sağ kalan artıkları, bu sınıfların \([1,N]\) içinde temsil ettiği sayı adedi ve \(A(N)\)'in biriken değeri.
Her yeni asal \(p\) için uygulama \(M\bmod p\)'nin tersini hesaplar, \(0,7,14,\dots<p\) izinli kalanlarını dolaşır ve \(Mp\) modundaki tüm çocuk artık sınıflarını üretir. Sonra bu yeni sınıfların \(N\)'e kadar kaç sayı içerdiği sayılır. Eski sağ kalan sayısı ile yeni sağ kalan sayısı arasındaki fark, ilk kez \(p\)'de elenen sayıların tam sayısıdır; bu yüzden koda düşen iş bu farkı \(p\) ile çarpıp cevaba eklemektir. \(M>N\) olduktan sonra sıfır olmayan kaydırmalı tüm yükseltmeler zaten \(N\)'i aşacağından bu dallar hemen atılır. Sağ kalan sayısı sıfıra düştüğü anda süreç biter. C++ sürümü büyük çarpımlar ve toplamlar için 128 bit aritmetik kullanır, Python doğal olarak sınırsız hassasiyetle çalışır, Java sürümü ise sabit genişlik yetmediğinde büyük tamsayılara geçer.
\(R_k\), \(k\)'ıncı asaldan sonra sağ kalan artık sınıfı sayısı olsun. Sıradaki asal \(p\) ise bir sonraki katmanı oluşturmanın maliyeti
$$ O\!\left(R_k\left(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\right)\right) $$
olur; çünkü her aktif sınıf, \(p\)'den küçük her \(7\) katı ile birleştirilir. Yeni nüfusu saymak, üretilen yeni sınıf sayısında lineerdir; asal eleme adımı ise buna kıyasla çok küçüktür.
Esas avantaj, algoritmanın hiçbir zaman \(1\)'den \(N\)'e kadar bütün sayıları dolaşmamasıdır. Zaman ve bellek kullanımı doğrudan \(10^{17}\)'ye değil, aynı anda aktif olan artık sınıflarının tepe sayısına bağlıdır. Pratikte sağ kalan nüfus hızla küçüldüğü için bellek maliyeti \(O(\max_k R_k)\) düzeyinde kalır ve hesap yönetilebilir olur.
Para cada entero positivo \(n\), se define \(p(n)\) como el primer primo \(p\) para el cual
$$ (n \bmod p)\bmod 7 \ne 0. $$
Dicho de otro modo, para todo primo anterior \(q<p(n)\) debe cumplirse que \(n \bmod q\) es un múltiplo de \(7\), es decir, pertenece a \(\{0,7,14,\dots\}\), y \(p(n)\) es el primer primo donde esa propiedad deja de cumplirse. La cantidad buscada es
$$ A(N)=\sum_{n=1}^{N} p(n), $$
con el valor real \(N=10^{17}\). Probar todos los \(n\) uno por uno es inviable. La idea útil es agrupar enteros en clases de congruencia y propagar solo las clases que siguen vivas.
La solución recorre los primos en orden creciente y mantiene el conjunto de enteros que han sobrevivido a todas las pruebas vistas hasta ese momento.
Sean \(p_1=2,p_2=3,\dots\) los primos. Después de procesar todos los primos hasta \(p_k\), definimos
$$ S_k=\{n\le N : n \bmod q \in \{0,7,14,\dots\}\text{ para todo primo } q\le p_k\}. $$
Ese conjunto contiene exactamente los números cuyo primer primo “malo” todavía es mayor que \(p_k\). Si escribimos \(C_k=|S_k|\), entonces los números que mueren al procesar el siguiente primo \(p\) aportan
$$ p\,(C_k-C_{k+1}) $$
a la suma final, porque para todos ellos se cumple \(p(n)=p\). Por eso el problema completo se reduce a actualizar \(S_k\) con rapidez y contar su tamaño en cada paso.
Tras procesar un prefijo de primos, definimos
$$ M_k=\prod_{q\le p_k} q. $$
Pertenecer o no a \(S_k\) depende únicamente de los residuos de \(n\) módulo de los primos ya procesados, y por tanto solo depende de \(n \pmod{M_k}\). En consecuencia, \(S_k\) puede representarse mediante una lista finita de clases residuales supervivientes \(r \pmod{M_k}\).
Cuando entra un nuevo primo \(p\), los residuos permitidos son los múltiplos de \(7\) menores que \(p\):
$$ \mathcal{A}_p=\{0,7,14,\dots\}\cap[0,p-1]. $$
Solo hay \(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\) de ellos. En particular, si \(p<7\), el único residuo permitido es \(0\), de modo que las primeras etapas solo fuerzan divisibilidad por \(2\), \(3\), \(5\) y \(7\).
Supongamos que \(r \pmod{M_k}\) es una clase que sigue viva y que \(a\in\mathcal{A}_p\) es un residuo permitido para el siguiente primo \(p\). Debemos resolver
$$ x\equiv r \pmod{M_k},\qquad x\equiv a \pmod p. $$
Escribimos \(x=r+M_k t\). Entonces \(t\) debe satisfacer
$$ M_k t \equiv a-r \pmod p. $$
Como \(p\) es un primo nuevo, \(\gcd(M_k,p)=1\), así que \(M_k\) tiene inverso módulo \(p\). Por tanto,
$$ t\equiv (a-r)\,M_k^{-1}\pmod p, $$
y cada par \((r,a)\) genera exactamente una clase hija módulo \(M_kp\):
$$ x\equiv r+M_k t \pmod{M_kp}. $$
Aquí aparece la compresión decisiva: el algoritmo no examina enteros individuales, sino solo las clases residuales que aún no han sido descartadas.
Una vez conocida una clase superviviente \(r \pmod M\), contar sus representantes en \([1,N]\) es fácil. Si \(r>0\), los elementos son
$$ r,\ r+M,\ r+2M,\dots, $$
de modo que su cantidad es
$$ \operatorname{cnt}(r;M)=\left\lfloor\dfrac{N-r}{M}\right\rfloor+1. $$
Si \(r=0\), los enteros positivos correspondientes son
$$ M,\ 2M,\ 3M,\dots, $$
porque \(0\) no pertenece al rango, y por eso
$$ \operatorname{cnt}(0;M)=\left\lfloor\dfrac{N}{M}\right\rfloor. $$
Cuando \(M>N\), cualquier residuo no nulo puede aportar como mucho un entero, que es el propio residuo, mientras que la clase \(0\) no aporta ninguno. Esa es la razón de la rama especial que aparece cuando el módulo acumulado ya supera \(N\).
Tras procesar los primos \(2,3,5,7\), el único residuo permitido en cada etapa es \(0\). Por tanto, todo superviviente debe ser múltiplo de
$$ 2\cdot 3\cdot 5\cdot 7=210, $$
y el conjunto superviviente se reduce a la única clase \(0 \pmod{210}\).
Ahora entra el primo \(11\). Los residuos permitidos son \(0\) y \(7\). El sistema
$$ x\equiv 0 \pmod{210},\qquad x\equiv 0 \pmod{11} $$
produce \(x\equiv 0 \pmod{2310}\). El sistema
$$ x\equiv 0 \pmod{210},\qquad x\equiv 7 \pmod{11} $$
produce \(x\equiv 1470 \pmod{2310}\), porque \(210\equiv 1 \pmod{11}\), así que \(t\equiv 7\) y \(x=210\cdot 7\). En consecuencia, después del primo \(11\) sobreviven exactamente las clases
$$ 0 \pmod{2310}\quad\text{y}\quad 1470 \pmod{2310}. $$
Si \(N=1470\), la primera clase no aporta nada porque \(2310>N\), mientras que la segunda aporta el único valor \(1470\). Este ejemplo ilustra tanto la elevación por CRT como la regla de conteo una vez que el módulo rebasa \(N\).
Las implementaciones en C++, Python y Java generan primero una lista moderada de primos. Durante la ejecución mantienen cuatro cantidades: el producto actual de primos \(M\), las clases residuales supervivientes en forma canónica módulo \(M\), el número de enteros en \([1,N]\) representados por esas clases y el valor acumulado de \(A(N)\).
Para cada nuevo primo \(p\), la implementación calcula el inverso de \(M\bmod p\), recorre los residuos permitidos \(0,7,14,\dots<p\) y genera todas las clases hijas módulo \(Mp\). Después cuenta cuántos enteros hasta \(N\) pertenecen a esas nuevas clases. La diferencia entre la población anterior y la nueva es exactamente el número de enteros cuyo primer primo desfavorable es \(p\), de modo que el código suma \(p\) veces esa diferencia. Cuando ya se cumple \(M>N\), cualquier elevación con desplazamiento no nulo quedaría automáticamente por encima de \(N\), así que esas ramas se descartan de inmediato. El proceso termina tan pronto como el número de supervivientes llega a cero. La versión en C++ usa aritmética de 128 bits para productos y sumas grandes, Python trabaja con enteros de precisión arbitraria y la versión en Java utiliza enteros grandes cuando el ancho fijo deja de bastar.
Sea \(R_k\) el número de clases residuales supervivientes tras el \(k\)-ésimo primo. Si el siguiente primo es \(p\), construir la siguiente capa cuesta
$$ O\!\left(R_k\left(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\right)\right), $$
porque cada clase activa se combina con cada múltiplo de \(7\) menor que \(p\). Contar la población siguiente es lineal en el número de clases nuevas, y el cribado de primos es pequeño frente a eso.
La observación decisiva es que el algoritmo nunca recorre todos los enteros hasta \(N\). El tiempo y la memoria dependen del máximo número de clases activas, no de \(10^{17}\) como tal. En la práctica la población superviviente cae muy deprisa, así que la memoria permanece en \(O(\max_k R_k)\) y el cálculo es manejable.
对每个正整数 \(n\)，定义 \(p(n)\) 为第一个满足
$$ (n \bmod p)\bmod 7 \ne 0 $$
的素数 \(p\)。等价地说，对于所有更小的素数 \(q<p(n)\)，都必须有 \(n \bmod q\in\{0,7,14,\dots\}\)，也就是余数必须是 \(7\) 的倍数；而 \(p(n)\) 正是第一个让这一性质失效的素数。题目要求计算
$$ A(N)=\sum_{n=1}^{N} p(n), $$
其中实际输入是 \(N=10^{17}\)。如果逐个枚举 \(n\)，再对每个 \(n\) 去试素数，规模完全不可接受。真正可行的办法，是把整数按同余类打包，只跟踪那些到当前为止仍然“幸存”的剩余类。
解法按照素数从小到大的顺序推进，并在每一步维护“已经通过所有已检查素数”的整数集合。
设素数序列为 \(p_1=2,p_2=3,\dots\)。当所有不超过 \(p_k\) 的素数都已经处理完后，定义
$$ S_k=\{n\le N : n \bmod q \in \{0,7,14,\dots\}\text{ 对每个素数 } q\le p_k\text{ 都成立}\}. $$
这个集合恰好由“第一个失败素数还大于 \(p_k\)”的整数构成。若记 \(C_k=|S_k|\)，那么在处理下一个素数 \(p\) 时被淘汰的整数，对最终答案的贡献就是
$$ p\,(C_k-C_{k+1}), $$
因为这些数的 \(p(n)\) 全都等于 \(p\)。因此整个问题被压缩成两件事：如何高效更新幸存集合，以及如何在每一步准确计算它的大小。
处理完一段素数前缀之后，令
$$ M_k=\prod_{q\le p_k} q. $$
一个整数 \(n\) 是否属于 \(S_k\)，只取决于它对这些已处理素数的余数，因此只取决于 \(n \pmod{M_k}\)。这意味着 \(S_k\) 可以表示成若干个幸存剩余类 \(r \pmod{M_k}\) 的有限列表。
当加入新素数 \(p\) 时，允许的余数就是所有小于 \(p\) 的 \(7\) 的倍数：
$$ \mathcal{A}_p=\{0,7,14,\dots\}\cap[0,p-1]. $$
这样的余数只有 \(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\) 个。特别地，当 \(p<7\) 时，唯一允许的余数就是 \(0\)，所以最开始几步实际上只是在依次强制被 \(2\)、\(3\)、\(5\)、\(7\) 整除。
假设 \(r \pmod{M_k}\) 是一个仍然幸存的类，且 \(a\in\mathcal{A}_p\) 是新素数 \(p\) 下允许的余数。我们需要解同余组
$$ x\equiv r \pmod{M_k},\qquad x\equiv a \pmod p. $$
令 \(x=r+M_k t\)，则 \(t\) 必须满足
$$ M_k t \equiv a-r \pmod p. $$
由于 \(p\) 是新加入的素数，\(\gcd(M_k,p)=1\)，所以 \(M_k\) 在模 \(p\) 下有逆元。于是
$$ t\equiv (a-r)\,M_k^{-1}\pmod p, $$
从而每一对 \((r,a)\) 都会在模 \(M_kp\) 下产生唯一的子类：
$$ x\equiv r+M_k t \pmod{M_kp}. $$
这一步是整个算法的关键压缩：程序根本不枚举所有整数，而只是把仍然存活的剩余类从一个模提升到下一个模。
一旦知道某个类 \(r \pmod M\) 是幸存类，就可以直接数出它在区间 \([1,N]\) 里有多少成员。若 \(r>0\)，对应的正整数是
$$ r,\ r+M,\ r+2M,\dots, $$
所以数量为
$$ \operatorname{cnt}(r;M)=\left\lfloor\dfrac{N-r}{M}\right\rfloor+1. $$
若 \(r=0\)，真正落在求和范围里的正整数是
$$ M,\ 2M,\ 3M,\dots, $$
因为 \(0\) 本身不在 \([1,N]\) 内，因此
$$ \operatorname{cnt}(0;M)=\left\lfloor\dfrac{N}{M}\right\rfloor. $$
当 \(M>N\) 时，任何非零剩余类最多只会贡献一个整数，也就是该剩余本身，而零类则一个也不贡献。这正是实现里在累计模超过 \(N\) 之后改用更简单计数分支的原因。
处理完素数 \(2,3,5,7\) 以后，每一步允许的余数都只有 \(0\)。因此所有幸存整数都必须被
$$ 2\cdot 3\cdot 5\cdot 7=210 $$
整除，所以此时只有一个幸存类：\(0 \pmod{210}\)。
接下来处理素数 \(11\)。允许余数变成 \(0\) 和 \(7\)。同余组
$$ x\equiv 0 \pmod{210},\qquad x\equiv 0 \pmod{11} $$
给出 \(x\equiv 0 \pmod{2310}\)。而
$$ x\equiv 0 \pmod{210},\qquad x\equiv 7 \pmod{11} $$
给出 \(x\equiv 1470 \pmod{2310}\)，因为 \(210\equiv 1 \pmod{11}\)，所以 \(t\equiv 7\)，从而 \(x=210\cdot 7\)。于是处理完 \(11\) 之后，幸存类恰好是
$$ 0 \pmod{2310}\quad\text{和}\quad 1470 \pmod{2310}. $$
如果取 \(N=1470\)，那么第一类没有任何贡献，因为 \(2310>N\)；第二类只贡献唯一的整数 \(1470\)。这个例子同时展示了 CRT 提升规则，以及模数超过 \(N\) 之后的计数方式。
C++、Python 和 Java 实现首先生成一份规模适中的素数表。随后它们在循环中维护四个量：当前的素数乘积 \(M\)、模 \(M\) 下的规范幸存剩余、这些剩余类在 \([1,N]\) 中实际代表的整数个数，以及答案 \(A(N)\) 的累计值。
对每个新素数 \(p\)，实现都会先求出 \(M\bmod p\) 的逆元，再枚举所有允许余数 \(0,7,14,\dots<p\)，从而生成模 \(Mp\) 下的全部子类。然后程序统计这些新类在 \(N\) 以内包含多少整数。旧幸存人数与新幸存人数之差，恰好就是“第一个失败素数等于 \(p\)”的整数个数，因此代码把这个差乘上 \(p\) 加入答案。当 \(M>N\) 之后，任何带非零位移的提升都会直接落到 \(N\) 之外，所以这些分支会立刻被剪掉。只要幸存人数降到零，算法就可以停止。C++ 实现对较大的乘积和累计值使用 128 位整数，Python 直接依赖任意精度整数，Java 则在固定宽度会溢出的地方使用大整数。
设 \(R_k\) 是处理完第 \(k\) 个素数后幸存剩余类的数量。如果下一个素数是 \(p\)，那么构造下一层的代价为
$$ O\!\left(R_k\left(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\right)\right), $$
因为每一个活跃剩余类都要与每一个小于 \(p\) 的 \(7\) 的倍数配对一次。之后的人数统计与新生成的剩余类数量线性相关，而素数筛本身相对很小。
真正关键的是，算法从头到尾都不遍历 \(1\) 到 \(N\) 的所有整数。时间和空间取决于活跃剩余类数量的峰值，而不是直接取决于 \(10^{17}\)。由于幸存者数量下降得很快，实际内存开销保持在 \(O(\max_k R_k)\)，运行时间也远小于朴素做法。
Для каждого положительного целого \(n\) определим \(p(n)\) как первое простое число \(p\), для которого
$$ (n \bmod p)\bmod 7 \ne 0. $$
Иными словами, для любого меньшего простого \(q<p(n)\) остаток \(n \bmod q\) обязан лежать в множестве \(\{0,7,14,\dots\}\), то есть быть кратным \(7\), а \(p(n)\) является первым простым, на котором это перестает выполняться. Нужно вычислить
$$ A(N)=\sum_{n=1}^{N} p(n), $$
причем в самой задаче \(N=10^{17}\). Перебирать все \(n\) по одному невозможно. Рабочая идея состоит в том, чтобы объединять числа в классы вычетов и отслеживать только те классы, которые еще не выбыли.
Решение идет по простым числам в порядке возрастания и после каждого шага хранит множество чисел, прошедших все проверки до текущего момента.
Пусть \(p_1=2,p_2=3,\dots\) — последовательность простых. После обработки всех простых до \(p_k\) включительно положим
$$ S_k=\{n\le N : n \bmod q \in \{0,7,14,\dots\}\text{ для каждого простого } q\le p_k\}. $$
Это в точности числа, у которых первое “плохое” простое еще больше \(p_k\). Если обозначить \(C_k=|S_k|\), то числа, исчезающие при обработке следующего простого \(p\), дают вклад
$$ p\,(C_k-C_{k+1}) $$
в окончательную сумму, потому что для них \(p(n)=p\). Значит, задача сводится к эффективному обновлению множества выживших и подсчету его размера после каждого нового простого.
После обработки некоторого префикса простых положим
$$ M_k=\prod_{q\le p_k} q. $$
Принадлежность числа \(n\) множеству \(S_k\) зависит только от остатков по уже обработанным простым, а значит, только от \(n \pmod{M_k}\). Поэтому \(S_k\) можно хранить как конечный список выживших классов вычетов \(r \pmod{M_k}\).
Для нового простого \(p\) допустимыми являются ровно те остатки, которые являются кратными \(7\) и меньше \(p\):
$$ \mathcal{A}_p=\{0,7,14,\dots\}\cap[0,p-1]. $$
Их всего \(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\). В частности, для \(p<7\) допустим только остаток \(0\), поэтому первые шаги просто поочередно навязывают делимость на \(2\), \(3\), \(5\) и \(7\).
Пусть \(r \pmod{M_k}\) — выживший класс, а \(a\in\mathcal{A}_p\) — допустимый остаток по следующему простому \(p\). Нужно решить систему
$$ x\equiv r \pmod{M_k},\qquad x\equiv a \pmod p. $$
Запишем \(x=r+M_k t\). Тогда \(t\) должно удовлетворять сравнению
$$ M_k t \equiv a-r \pmod p. $$
Поскольку \(p\) — новое простое, \(\gcd(M_k,p)=1\), значит, у \(M_k\) существует обратный элемент по модулю \(p\). Следовательно,
$$ t\equiv (a-r)\,M_k^{-1}\pmod p, $$
и каждая пара \((r,a)\) порождает ровно один дочерний класс по модулю \(M_kp\):
$$ x\equiv r+M_k t \pmod{M_kp}. $$
Именно здесь происходит основное сжатие задачи: алгоритм не перебирает числа, а переносит вперед только еще живые классы вычетов.
Если класс \(r \pmod M\) выживает, то его представители в \([1,N]\) при \(r>0\) имеют вид
$$ r,\ r+M,\ r+2M,\dots, $$
и потому их количество равно
$$ \operatorname{cnt}(r;M)=\left\lfloor\dfrac{N-r}{M}\right\rfloor+1. $$
Для \(r=0\) положительные представители — это
$$ M,\ 2M,\ 3M,\dots, $$
поскольку само число \(0\) не входит в диапазон суммирования, так что
$$ \operatorname{cnt}(0;M)=\left\lfloor\dfrac{N}{M}\right\rfloor. $$
Когда \(M>N\), любой ненулевой класс может дать не более одного числа, а именно сам остаток, тогда как нулевой класс не дает ни одного. Именно этим объясняется упрощенная ветка подсчета после того, как накопленный модуль становится больше \(N\).
После обработки простых \(2,3,5,7\) на каждом шаге разрешен только остаток \(0\). Значит, любое выжившее число обязано делиться на
$$ 2\cdot 3\cdot 5\cdot 7=210, $$
поэтому множество выживших состоит из единственного класса \(0 \pmod{210}\).
Теперь берется простое \(11\). Разрешенные остатки — \(0\) и \(7\). Система
$$ x\equiv 0 \pmod{210},\qquad x\equiv 0 \pmod{11} $$
дает \(x\equiv 0 \pmod{2310}\). Система
$$ x\equiv 0 \pmod{210},\qquad x\equiv 7 \pmod{11} $$
дает \(x\equiv 1470 \pmod{2310}\), поскольку \(210\equiv 1 \pmod{11}\), а значит \(t\equiv 7\) и \(x=210\cdot 7\). Итак, после простого \(11\) выживают ровно два класса:
$$ 0 \pmod{2310}\quad\text{и}\quad 1470 \pmod{2310}. $$
Если взять \(N=1470\), то первый класс ничего не дает, потому что \(2310>N\), а второй дает ровно одно число \(1470\). В этом примере видны и шаг подъема по CRT, и правило подсчета после перехода через \(N\).
Реализации на C++, Python и Java сначала строят умеренный список простых чисел. Затем они поддерживают четыре изменяющихся объекта: текущее произведение простых \(M\), канонические выжившие остатки по модулю \(M\), количество чисел из \([1,N]\), представленных этими остатками, и текущий накопленный ответ \(A(N)\).
Для каждого нового простого \(p\) программа вычисляет обратный элемент к \(M\bmod p\), перебирает разрешенные остатки \(0,7,14,\dots<p\) и строит все дочерние классы по модулю \(Mp\). Затем она подсчитывает, сколько чисел до \(N\) лежит в новых классах. Разность между старым и новым числом выживших — это в точности количество чисел, для которых первым плохим простым является \(p\), поэтому код прибавляет к ответу \(p\), умноженное на эту разность. Как только \(M>N\), любой подъем с ненулевым сдвигом сразу уводит представителя выше \(N\), поэтому такие ветви немедленно отбрасываются. Процесс останавливается, когда выживших больше не остается. Версия на C++ использует 128-битную арифметику для больших произведений и сумм, Python опирается на целые произвольной точности, а Java применяет большие целые там, где фиксированной разрядности уже недостаточно.
Пусть \(R_k\) — число выживших классов вычетов после обработки \(k\)-го простого. Если следующее простое равно \(p\), то построение следующего слоя стоит
$$ O\!\left(R_k\left(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\right)\right), $$
потому что каждый активный класс комбинируется с каждым кратным \(7\), меньшим \(p\). Подсчет новой популяции линеен по числу новых классов, а построение списка простых на этом фоне ничтожно мало.
Ключевое достоинство состоит в том, что алгоритм никогда не проходит по всем числам от \(1\) до \(N\). Его время и память определяются максимальным количеством активных классов, а не самим числом \(10^{17}\). На практике число выживших быстро падает, поэтому память остается на уровне \(O(\max_k R_k)\), а вычисление оказывается вполне подъемным.
لكل عدد صحيح موجب \(n\)، نعرّف \(p(n)\) بأنه أول عدد أولي \(p\) يحقق
$$ (n \bmod p)\bmod 7 \ne 0. $$
وبصيغة مكافئة: لكل عدد أولي أصغر \(q<p(n)\) يجب أن يكون الباقي \(n \bmod q\) من مضاعفات \(7\)، أي ضمن المجموعة \(\{0,7,14,\dots\}\)، ثم يكون \(p(n)\) هو أول أولي تتوقف عنده هذه الخاصية. المطلوب حساب
$$ A(N)=\sum_{n=1}^{N} p(n), $$
وفي المسألة الفعلية يكون \(N=10^{17}\). الفحص المباشر لكل \(n\) غير ممكن عمليًا. الفكرة الفعالة هي جمع الأعداد في فئات توافقية، ثم تتبع الفئات التي ما زالت حية فقط.
يُعالج الحل الأعداد الأولية بترتيب تصاعدي، وبعد كل خطوة يحتفظ بمجموعة الأعداد التي اجتازت جميع الاختبارات السابقة.
لتكن الأعداد الأولية \(p_1=2,p_2=3,\dots\). بعد معالجة جميع الأوليات حتى \(p_k\) نعرّف
$$ S_k=\{n\le N : n \bmod q \in \{0,7,14,\dots\}\text{ for every prime } q\le p_k\}. $$
هذه هي بالضبط الأعداد التي ما يزال أول أولي سيئ لها أكبر من \(p_k\). وإذا كتبنا \(C_k=|S_k|\)، فإن الأعداد التي تُستبعد عند معالجة الأولي التالي \(p\) تضيف إلى الجواب
$$ p\,(C_k-C_{k+1}), $$
لأن جميع هذه الأعداد تحقق \(p(n)=p\). لذلك ينحصر جوهر المسألة في تحديث مجموعة الناجين بكفاءة، ثم عدّ حجمها بعد كل أولي.
بعد معالجة بادئة من الأوليات نضع
$$ M_k=\prod_{q\le p_k} q. $$
انتماء العدد \(n\) إلى \(S_k\) يعتمد فقط على بواقيه بالنسبة إلى الأوليات التي عولجت سابقًا، وبالتالي يعتمد فقط على \(n \pmod{M_k}\). لهذا يمكن تمثيل \(S_k\) بقائمة منتهية من فئات البواقي الناجية \(r \pmod{M_k}\).
عند إدخال أولي جديد \(p\)، تكون البواقي المسموحة هي مضاعفات \(7\) الأصغر من \(p\):
$$ \mathcal{A}_p=\{0,7,14,\dots\}\cap[0,p-1]. $$
وعددها لا يتجاوز \(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\). وعندما يكون \(p<7\)، لا يبقى إلا الباقي \(0\)، ولذلك فإن المراحل الأولى لا تفعل سوى فرض القابلية للقسمة على \(2\) ثم \(3\) ثم \(5\) ثم \(7\).
افترض أن \(r \pmod{M_k}\) فئة ناجية، وأن \(a\in\mathcal{A}_p\) باقٍ مسموح modulo الأولي التالي \(p\). نحتاج إلى حل النظام
$$ x\equiv r \pmod{M_k},\qquad x\equiv a \pmod p. $$
نكتب \(x=r+M_k t\). عندئذ يجب أن يحقق \(t\)
$$ M_k t \equiv a-r \pmod p. $$
وبما أن \(p\) أولي جديد، فإن \(\gcd(M_k,p)=1\)، ولذلك يوجد معكوس لـ \(M_k\) modulo \(p\). ومن ثم
$$ t\equiv (a-r)\,M_k^{-1}\pmod p, $$
وينتج عن كل زوج \((r,a)\) فئة ابنة وحيدة modulo \(M_kp\):
$$ x\equiv r+M_k t \pmod{M_kp}. $$
هذه هي نقطة الضغط الأساسية في الخوارزمية: فهي لا تختبر الأعداد واحدًا واحدًا، بل ترفع فقط فئات البواقي التي ما زالت باقية.
إذا كانت الفئة \(r \pmod M\) ناجية و\(r>0\)، فإن عناصرها داخل \([1,N]\) هي
$$ r,\ r+M,\ r+2M,\dots, $$
ولذلك يكون عددها
$$ \operatorname{cnt}(r;M)=\left\lfloor\dfrac{N-r}{M}\right\rfloor+1. $$
أما إذا كان \(r=0\)، فإن العناصر الموجبة هي
$$ M,\ 2M,\ 3M,\dots, $$
لأن الصفر نفسه خارج مجال الجمع، وبالتالي
$$ \operatorname{cnt}(0;M)=\left\lfloor\dfrac{N}{M}\right\rfloor. $$
وعندما يصبح \(M>N\)، فإن أي فئة غير صفرية لا يمكن أن تمثل أكثر من عدد واحد، وهو الباقي نفسه، بينما لا تمثل الفئة الصفرية أي عدد. وهذا يفسر الفرع الأبسط الذي تستخدمه الشيفرة بعد أن يتجاوز الموديل التراكمي المجال.
بعد معالجة الأوليات \(2,3,5,7\)، يكون الباقي المسموح في كل خطوة هو \(0\) فقط. لذلك يجب أن يكون كل عدد ناجٍ قابلًا للقسمة على
$$ 2\cdot 3\cdot 5\cdot 7=210, $$
أي إن مجموعة الناجين تختزل إلى الفئة الوحيدة \(0 \pmod{210}\).
بعد ذلك يأتي الأولي \(11\). البواقي المسموحة هي \(0\) و\(7\). النظام
$$ x\equiv 0 \pmod{210},\qquad x\equiv 0 \pmod{11} $$
يعطي \(x\equiv 0 \pmod{2310}\). أما النظام
$$ x\equiv 0 \pmod{210},\qquad x\equiv 7 \pmod{11} $$
فيعطي \(x\equiv 1470 \pmod{2310}\)، لأن \(210\equiv 1 \pmod{11}\)، ومن ثم \(t\equiv 7\) و\(x=210\cdot 7\). وهكذا تصبح فئات الناجين بعد معالجة \(11\) هي
$$ 0 \pmod{2310},\qquad 1470 \pmod{2310}. $$
إذا أخذنا \(N=1470\)، فإن الفئة الأولى لا تسهم بشيء لأن \(2310>N\)، بينما تسهم الثانية بالعدد الوحيد \(1470\). هذا المثال يوضح معًا خطوة الرفع بواسطة CRT وقاعدة العد بعد تجاوز \(N\).
تبدأ تطبيقات C++ وPython وJava بتوليد قائمة معتدلة من الأعداد الأولية. ثم تحافظ أثناء التنفيذ على أربع كميات: حاصل الضرب الحالي للأوليات \(M\)، وبواقي الناجين بصيغتها المعيارية modulo \(M\)، وعدد الأعداد في \([1,N]\) التي تمثلها هذه الفئات، والقيمة المتراكمة لـ \(A(N)\).
لكل أولي جديد \(p\)، تحسب الشيفرة معكوس \(M\bmod p\)، ثم تمر على البواقي المسموحة \(0,7,14,\dots<p\)، وتولد جميع الفئات الابنة modulo \(Mp\). بعد ذلك تُحصى الأعداد التي لا تتجاوز \(N\) داخل هذه الفئات الجديدة. الفرق بين عدد الناجين القديم والجديد هو بالضبط عدد الأعداد التي يكون أول أولي سيئ لها هو \(p\)، ولذلك تضيف الشيفرة \(p\) مضروبًا في هذا الفرق إلى الجواب. وعندما يصبح \(M>N\)، فإن أي رفع بإزاحة غير صفرية سيقع مباشرة فوق \(N\)، لذا تُقصى هذه الفروع فورًا. وتتوقف العملية عندما يهبط عدد الناجين إلى الصفر. تستخدم نسخة C++ حسابًا بعرض 128 بت للجداءات والمجاميع الكبيرة، وتعتمد Python على أعداد صحيحة غير محدودة الدقة، بينما تستخدم Java أعدادًا صحيحة كبيرة عندما لا تكفي الأنواع ذات العرض الثابت.
إذا رمزنا إلى عدد فئات البواقي الناجية بعد الأولي رقم \(k\) بالرمز \(R_k\)، وكان الأولي التالي هو \(p\)، فإن بناء الطبقة التالية يكلف
$$ O\!\left(R_k\left(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\right)\right), $$
لأن كل فئة نشطة تُدمج مع كل مضاعف لـ \(7\) أصغر من \(p\). أما عدّ السكان الجدد فهو خطي في عدد الفئات الجديدة، وخطوة توليد الأوليات صغيرة جدًا بالمقارنة.
الميزة الحاسمة هي أن الخوارزمية لا تمر أبدًا على جميع الأعداد حتى \(N\). فالزمن والذاكرة يعتمدان على أكبر عدد من الفئات النشطة في أي لحظة، لا على \(10^{17}\) نفسه. عمليًا ينهار عدد الناجين بسرعة، ولذلك تبقى الذاكرة ضمن \(O(\max_k R_k)\) ويظل الحساب ممكنًا.