For \(n\ge 2\), let \(s(n)\) be the smallest prime factor of \(n\). We must evaluate
$$S(N)=\sum_{n=2}^{N} s(n), \qquad N=10^{12},$$
and return the result modulo \(10^9\). A direct sieve up to \(N\) would require linear memory and essentially linear time, so the implementation instead tracks how composite numbers disappear when primes are processed in increasing order.
The key idea is that every composite number is removed exactly once, namely when its smallest prime factor is reached, while primes are never removed. The algorithm turns that observation into coupled recurrences for filtered counts and filtered sums.
If \(n\) is prime, then \(s(n)=n\). If \(n\) is composite, then \(s(n)\le \sqrt n\le \sqrt N\). Therefore
$$S(N)=\sum_{\substack{q\le N\\ q\text{ prime}}} q+\sum_{p\le \sqrt N} p\,M_p(N),$$
where \(M_p(N)\) denotes the number of composite integers \(n\le N\) whose smallest prime factor is exactly \(p\). So the entire task becomes: count those composites efficiently, and also recover the sum of all primes up to \(N\).
For a prime threshold \(p\), define the surviving set
$$\mathcal{R}_p(x)=\left\{m\in\{2,\dots,x\}: s(m)\ge p\right\}\cup\left\{q\le x:q\text{ prime},\ q<p\right\}.$$
This set contains two kinds of numbers: primes smaller than \(p\), which are kept forever, and numbers whose prime factors are all at least \(p\), which have not yet been removed. Now define
$$C_p(x)=\#\mathcal{R}_p(x), \qquad T_p(x)=\sum_{m\in\mathcal{R}_p(x)} m.$$
At the start no filtering has happened, so for \(p=2\) we simply have
$$C_2(x)=x-1,\qquad T_2(x)=\sum_{m=2}^{x} m=\frac{x(x+1)}{2}-1.$$
A useful consequence is that \(C_p(p)-C_p(p-1)=1\) exactly when \(p\) is prime, because every composite number has already disappeared before its own turn.
Take a prime \(p\). Any composite \(n\le x\) with \(s(n)=p\) can be written uniquely as
$$n=p\,m,$$
where \(m\ge p\) and every prime factor of \(m\) is at least \(p\). Equivalently, \(m\) lies in \(\mathcal{R}_p(\lfloor x/p\rfloor)\), but the elements below \(p\) must be excluded because they are precisely the smaller primes. Hence
$$M_p(x)=C_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-C_p(p-1).$$
The weighted contribution of all such composites is therefore
$$p\,M_p(N)=p\left(C_p\!\left(\left\lfloor\frac{N}{p}\right\rfloor\right)-C_p(p-1)\right).$$
There is no extra \(+p\) term here because the prime \(p\) itself remains in the filtered sum and is added later together with the other primes.
After the composites with smallest prime factor \(p\) have been identified, they must be removed from later stages. The count recurrence is
$$C_{p^+}(x)=C_p(x)-\left(C_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-C_p(p-1)\right),$$
where \(p^+\) denotes the state immediately after processing \(p\). The corresponding sum recurrence removes the actual composite values \(p\,m\):
$$T_{p^+}(x)=T_p(x)-p\left(T_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-T_p(p-1)\right).$$
Once every prime \(p\le \sqrt N\) has been processed, each composite number has been removed exactly once, so the surviving filtered sum is just the sum of all primes up to \(N\):
$$T_{\mathrm{final}}(N)=\sum_{\substack{q\le N\\ q\text{ prime}}} q.$$
Let
$$v=\left\lfloor\sqrt N\right\rfloor.$$
Every argument needed by the recurrence is either at most \(v\), or has the form \(\left\lfloor N/i\right\rfloor\) for some \(1\le i\le v\). This is the standard floor-quotient compression: the number of distinct values is only \(O(\sqrt N)\), not \(O(N)\). So the implementation stores two synchronized views,
$$C_p(x),\ T_p(x)\quad \text{for }1\le x\le v,$$
and
$$C_p\!\left(\left\lfloor\frac{N}{i}\right\rfloor\right),\ T_p\!\left(\left\lfloor\frac{N}{i}\right\rfloor\right)\quad \text{for }1\le i\le v.$$
That is why the memory usage stays near \(O(\sqrt N)\).
The smallest prime factors are
$$s(2),\dots,s(10)=2,3,2,5,2,7,2,3,2,$$
so the correct total is \(28\).
Initially, \(T_2(10)=2+3+\cdots+10=54\).
For \(p=2\),
$$M_2(10)=C_2(5)-C_2(1)=4-0=4,$$
corresponding to \(4,6,8,10\). Their weighted contribution is \(2\cdot 4=8\), and their actual sum \(4+6+8+10=28\) is removed from the filtered sum, leaving \(26\).
For \(p=3\), the current surviving set up to \(10\) is \(\{2,3,5,7,9\}\). Then
$$M_3(10)=C_3(3)-C_3(2)=2-1=1,$$
which corresponds to \(9\). Its weighted contribution is \(3\), and removing \(9\) leaves \(17\), exactly the sum of the primes \(2+3+5+7\).
Therefore
$$S(10)=17+8+3=28.$$
The C++, Python, and Java implementations all begin with \(v=\lfloor\sqrt N\rfloor\) and build four tables: filtered counts and filtered sums for small arguments \(x\le v\), plus the same quantities for large arguments of the form \(\lfloor N/i\rfloor\). The initial values are the unfiltered counts \(x-1\) and the unfiltered sums \(\frac{x(x+1)}{2}-1\).
They then scan \(p=2,3,\dots,v\). A position is treated as prime exactly when the filtered count changes between \(p-1\) and \(p\). For each prime, the implementation first adds
$$p\left(C_p\!\left(\left\lfloor\frac{N}{p}\right\rfloor\right)-C_p(p-1)\right)$$
to the answer accumulator, accounting for every composite whose smallest prime factor is \(p\). It then applies the recurrence for \(C\) and \(T\) to every stored argument, selecting the small-table or large-table source according to whether the quotient lies below \(\sqrt N\).
The C++ and Python implementations keep exact integer sums during the whole process and reduce modulo \(10^9\) only at the end. The Java implementation keeps the sum tables modulo \(10^9\) during the updates while retaining exact counts; this is valid because only linear combinations of the sums are used, and the final answer itself is required modulo \(10^9\). After the prime loop finishes, the remaining filtered sum is the sum of all primes up to \(N\), so adding it to the accumulator yields \(S(N)\).
Let \(v=\lfloor\sqrt N\rfloor\). The tables use \(O(v)=O(\sqrt N)\) memory. For each prime \(p\le v\), the implementation updates one range of length about \(\min\!\left(v,\left\lfloor N/p^2\right\rfloor\right)\) in the large-domain tables and one range of length about \(\max(0,v-p^2+1)\) in the small-domain tables. Summed over all primes, the work is roughly
$$O\!\left(\sum_{p\le v}\left(\min\!\left(v,\frac{N}{p^2}\right)+\max(0,v-p^2)\right)\right),$$
which is about \(O\!\left(N^{3/4}/\log N\right)\) for this split-domain sieve. The important point is practical rather than asymptotic finesse: both time and memory are far below any linear-in-\(N\) method, which is why \(N=10^{12}\) is manageable.
Für \(n\ge 2\) sei \(s(n)\) der kleinste Primfaktor von \(n\). Gesucht ist
$$S(N)=\sum_{n=2}^{N} s(n), \qquad N=10^{12},$$
wobei das Ergebnis modulo \(10^9\) ausgegeben wird. Ein direktes Sieb bis \(N\) wäre hinsichtlich Zeit und Speicher viel zu teuer, daher verfolgt die Implementierung stattdessen, wie zusammengesetzte Zahlen beim Durchlauf der Primzahlen schrittweise verschwinden.
Der Kern der Methode ist: Jede zusammengesetzte Zahl wird genau einmal entfernt, nämlich dann, wenn ihr kleinster Primfaktor verarbeitet wird, während Primzahlen niemals entfernt werden. Daraus entstehen gekoppelte Rekursionen für gefilterte Anzahlen und gefilterte Summen.
Ist \(n\) prim, so gilt \(s(n)=n\). Ist \(n\) zusammengesetzt, dann ist \(s(n)\le \sqrt n\le \sqrt N\). Also
$$S(N)=\sum_{\substack{q\le N\\ q\text{ prim}}} q+\sum_{p\le \sqrt N} p\,M_p(N),$$
wobei \(M_p(N)\) die Anzahl zusammengesetzter Zahlen \(n\le N\) mit kleinstem Primfaktor \(p\) bezeichnet. Damit reduziert sich das Problem darauf, diese Kompositzahlen effizient zu zählen und zugleich die Summe aller Primzahlen bis \(N\) zu erhalten.
Für einen Primschwellenwert \(p\) definieren wir die überlebende Menge
$$\mathcal{R}_p(x)=\left\{m\in\{2,\dots,x\}: s(m)\ge p\right\}\cup\left\{q\le x:q\text{ prim},\ q<p\right\}.$$
Diese Menge enthält zwei Arten von Zahlen: bereits erkannte Primzahlen kleiner als \(p\), die dauerhaft erhalten bleiben, und Zahlen, deren Primfaktoren alle mindestens \(p\) sind und die daher noch nicht entfernt wurden. Dazu definieren wir
$$C_p(x)=\#\mathcal{R}_p(x), \qquad T_p(x)=\sum_{m\in\mathcal{R}_p(x)} m.$$
Am Anfang wurde noch nichts gefiltert, also gilt für \(p=2\)
$$C_2(x)=x-1,\qquad T_2(x)=\sum_{m=2}^{x} m=\frac{x(x+1)}{2}-1.$$
Eine nützliche Folgerung ist: \(C_p(p)-C_p(p-1)=1\) genau dann, wenn \(p\) prim ist, denn jede zusammengesetzte Zahl ist schon vor ihrem eigenen Index verschwunden.
Sei \(p\) prim. Jede zusammengesetzte Zahl \(n\le x\) mit \(s(n)=p\) lässt sich eindeutig als
$$n=p\,m$$
schreiben, wobei \(m\ge p\) ist und alle Primfaktoren von \(m\) mindestens \(p\) sind. Anders gesagt liegt \(m\) in \(\mathcal{R}_p(\lfloor x/p\rfloor)\), aber die Elemente unterhalb von \(p\) müssen ausgeschlossen werden, weil das genau die kleineren Primzahlen sind. Daher
$$M_p(x)=C_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-C_p(p-1).$$
Der gewichtete Beitrag aller dieser Kompositzahlen lautet somit
$$p\,M_p(N)=p\left(C_p\!\left(\left\lfloor\frac{N}{p}\right\rfloor\right)-C_p(p-1)\right).$$
Ein zusätzlicher Term \(+p\) ist nicht nötig, weil die Primzahl \(p\) selbst in der gefilterten Summe verbleibt und später zusammen mit allen anderen Primzahlen addiert wird.
Sobald die Zahlen mit kleinstem Primfaktor \(p\) identifiziert sind, müssen sie für alle späteren Stufen entfernt werden. Die Rekursion für die Anzahl ist
$$C_{p^+}(x)=C_p(x)-\left(C_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-C_p(p-1)\right),$$
wobei \(p^+\) den Zustand unmittelbar nach der Verarbeitung von \(p\) bezeichnet. Die zugehörige Summenrekursion entfernt die tatsächlichen Kompositwerte \(p\,m\):
$$T_{p^+}(x)=T_p(x)-p\left(T_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-T_p(p-1)\right).$$
Wenn alle Primzahlen \(p\le \sqrt N\) verarbeitet wurden, ist jede zusammengesetzte Zahl genau einmal entfernt worden. Die verbleibende gefilterte Summe ist dann schlicht die Summe aller Primzahlen bis \(N\):
$$T_{\mathrm{final}}(N)=\sum_{\substack{q\le N\\ q\text{ prim}}} q.$$
Setze
$$v=\left\lfloor\sqrt N\right\rfloor.$$
Jedes in der Rekursion benötigte Argument ist entweder höchstens \(v\) oder von der Form \(\left\lfloor N/i\right\rfloor\) für ein \(1\le i\le v\). Das ist die übliche Quotientenkompression mit Abrundung: Es gibt nur \(O(\sqrt N)\) verschiedene Werte, nicht \(O(N)\). Deshalb speichert die Implementierung zwei synchronisierte Ansichten,
$$C_p(x),\ T_p(x)\quad \text{für }1\le x\le v,$$
und
$$C_p\!\left(\left\lfloor\frac{N}{i}\right\rfloor\right),\ T_p\!\left(\left\lfloor\frac{N}{i}\right\rfloor\right)\quad \text{für }1\le i\le v.$$
Genau deshalb bleibt der Speicherverbrauch bei \(O(\sqrt N)\).
Die kleinsten Primfaktoren lauten
$$s(2),\dots,s(10)=2,3,2,5,2,7,2,3,2,$$
also ist die richtige Summe \(28\).
Anfangs ist \(T_2(10)=2+3+\cdots+10=54\).
Für \(p=2\) gilt
$$M_2(10)=C_2(5)-C_2(1)=4-0=4,$$
entsprechend den Zahlen \(4,6,8,10\). Ihr gewichteter Beitrag ist \(2\cdot 4=8\), und ihre tatsächliche Summe \(4+6+8+10=28\) wird aus der gefilterten Summe entfernt, sodass \(26\) übrig bleiben.
Für \(p=3\) ist die aktuelle überlebende Menge bis \(10\) gleich \(\{2,3,5,7,9\}\). Dann folgt
$$M_3(10)=C_3(3)-C_3(2)=2-1=1,$$
also genau die Zahl \(9\). Ihr gewichteter Beitrag ist \(3\), und nach dem Entfernen von \(9\) bleibt \(17\), genau die Primzahlsumme \(2+3+5+7\).
Damit erhält man
$$S(10)=17+8+3=28.$$
Die C++-, Python- und Java-Implementierungen beginnen alle mit \(v=\lfloor\sqrt N\rfloor\) und erzeugen vier Tabellen: gefilterte Anzahlen und gefilterte Summen für kleine Argumente \(x\le v\) sowie dieselben Größen für große Argumente der Form \(\lfloor N/i\rfloor\). Die Anfangswerte sind die ungefilterten Anzahlen \(x-1\) und die ungefilterten Summen \(\frac{x(x+1)}{2}-1\).
Anschließend wird \(p=2,3,\dots,v\) durchlaufen. Ein Index wird genau dann als prim behandelt, wenn sich die gefilterte Anzahl zwischen \(p-1\) und \(p\) ändert. Für jede Primzahl addiert die Implementierung zuerst
$$p\left(C_p\!\left(\left\lfloor\frac{N}{p}\right\rfloor\right)-C_p(p-1)\right)$$
zum Antwortakkumulator; damit sind alle zusammengesetzten Zahlen mit kleinstem Primfaktor \(p\) erfasst. Danach wird die Rekursion für \(C\) und \(T\) auf alle gespeicherten Argumente angewandt, wobei je nach Größe des Quotienten auf die kleine oder große Tabellenansicht zugegriffen wird.
Die C++- und Python-Implementierungen führen die Summen exakt und reduzieren erst ganz am Ende modulo \(10^9\). Die Java-Implementierung hält die Summen während der Aktualisierung bereits modulo \(10^9\), lässt die Anzahlen aber exakt; das ist korrekt, weil nur lineare Kombinationen der Summen verwendet werden und die Endantwort ohnehin nur modulo \(10^9\) gefragt ist. Nach der Primschleife ist die verbleibende gefilterte Summe genau die Summe aller Primzahlen bis \(N\); zusammen mit dem Akkumulator ergibt das \(S(N)\).
Sei \(v=\lfloor\sqrt N\rfloor\). Die Tabellen benötigen \(O(v)=O(\sqrt N)\) Speicher. Für jede Primzahl \(p\le v\) aktualisiert die Implementierung einen Bereich der Länge ungefähr \(\min\!\left(v,\left\lfloor N/p^2\right\rfloor\right)\) in den großen Tabellen und einen Bereich der Länge ungefähr \(\max(0,v-p^2+1)\) in den kleinen Tabellen. Über alle Primzahlen aufsummiert ergibt das näherungsweise
$$O\!\left(\sum_{p\le v}\left(\min\!\left(v,\frac{N}{p^2}\right)+\max(0,v-p^2)\right)\right),$$
also für diesen Split-Domain-Ansatz etwa \(O\!\left(N^{3/4}/\log N\right)\). Wichtiger als die exakte Feinstruktur ist hier: Zeit und Speicher liegen weit unter jedem linearen Verfahren in \(N\), weshalb \(N=10^{12}\) praktisch erreichbar ist.
\(n\ge 2\) için \(s(n)\), \(n\)'in en küçük asal bölenidir. Hesaplamamız gereken toplam
$$S(N)=\sum_{n=2}^{N} s(n), \qquad N=10^{12},$$
ve sonuç \(10^9\) modunda istenir. \(N\)'ye kadar doğrudan eleme yapmak hem zaman hem bellek açısından fazla pahalıdır; bu yüzden uygulama, asallar artan sırayla işlenirken bileşik sayıların nasıl ortadan kalktığını izler.
Ana gözlem şudur: Her bileşik sayı tam bir kez silinir; bu da en küçük asal böleni işlenirken olur. Asallar ise hiç silinmez. Algoritma bu fikri, filtrelenmiş adetler ve filtrelenmiş toplamlar için eşlenik bağıntılara dönüştürür.
\(n\) asal ise \(s(n)=n\) olur. \(n\) bileşik ise \(s(n)\le \sqrt n\le \sqrt N\). Dolayısıyla
$$S(N)=\sum_{\substack{q\le N\\ q\text{ asal}}} q+\sum_{p\le \sqrt N} p\,M_p(N),$$
burada \(M_p(N)\), en küçük asal böleni tam olarak \(p\) olan \(n\le N\) bileşiklerinin sayısıdır. Böylece iş, bu bileşikleri hızlıca saymaya ve aynı anda \(N\)'ye kadar olan tüm asalların toplamını çıkarmaya indirgenir.
Bir asal eşik \(p\) için hayatta kalan küme
$$\mathcal{R}_p(x)=\left\{m\in\{2,\dots,x\}: s(m)\ge p\right\}\cup\left\{q\le x:q\text{ asal},\ q<p\right\}$$
olsun. Bu kümede iki tür sayı vardır: \(p\)'den küçük olup artık kalıcı hale gelmiş asallar ve tüm asal çarpanları en az \(p\) olan, dolayısıyla henüz elenmemiş sayılar. Şimdi
$$C_p(x)=\#\mathcal{R}_p(x), \qquad T_p(x)=\sum_{m\in\mathcal{R}_p(x)} m$$
tanımlarını yapalım. Başlangıçta hiçbir filtreleme olmadığından \(p=2\) için
$$C_2(x)=x-1,\qquad T_2(x)=\sum_{m=2}^{x} m=\frac{x(x+1)}{2}-1$$
elde edilir. Buradan önemli bir yan sonuç çıkar: \(C_p(p)-C_p(p-1)=1\) ancak ve ancak \(p\) asalsa gerçekleşir; çünkü bileşik sayılar kendi sıraları gelmeden önce çoktan elenmiştir.
\(p\) asal olsun. \(s(n)=p\) olan her \(n\le x\) bileşiği tek biçimde
$$n=p\,m$$
şeklinde yazılır; burada \(m\ge p\) ve \(m\)'nin tüm asal bölenleri en az \(p\)'dir. Başka bir deyişle \(m\), \(\mathcal{R}_p(\lfloor x/p\rfloor)\) içinde yer alır; fakat \(p\)'den küçük elemanlar çıkarılmalıdır, çünkü onlar tam olarak daha küçük asallardır. Bu yüzden
$$M_p(x)=C_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-C_p(p-1)$$
olur. Buna göre bu bileşiklerin ağırlıklı katkısı
$$p\,M_p(N)=p\left(C_p\!\left(\left\lfloor\frac{N}{p}\right\rfloor\right)-C_p(p-1)\right)$$
şeklindedir. Burada ayrıca \(+p\) eklenmez; çünkü asal \(p\) filtreli toplamda kalır ve daha sonra diğer asallarla birlikte eklenir.
En küçük asal böleni \(p\) olan bileşikler tespit edildikten sonra, sonraki aşamalar için sistemden çıkarılmaları gerekir. Adet bağıntısı
$$C_{p^+}(x)=C_p(x)-\left(C_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-C_p(p-1)\right)$$
şeklindedir; burada \(p^+\), \(p\) işlendikten hemen sonraki durumu gösterir. Gerçek bileşik değerleri \(p\,m\) olduğu için toplam bağıntısı ise
$$T_{p^+}(x)=T_p(x)-p\left(T_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-T_p(p-1)\right)$$
olur. Tüm \(p\le \sqrt N\) asalları işlendiğinde her bileşik sayı tam bir kez silinmiş olur; elde kalan filtreli toplam da yalnızca \(N\)'ye kadar olan asalların toplamıdır:
$$T_{\mathrm{final}}(N)=\sum_{\substack{q\le N\\ q\text{ asal}}} q.$$
Şunu tanımlayalım:
$$v=\left\lfloor\sqrt N\right\rfloor.$$
Bağıntılarda görülen her argüman ya en fazla \(v\)'dir ya da \(\left\lfloor N/i\right\rfloor\) biçimindedir (\(1\le i\le v\)). Bu, taban alma bölüm değerlerinin klasik sıkıştırmasıdır: farklı değer sayısı \(O(N)\) değil, yalnızca \(O(\sqrt N)\) olur. Bu nedenle uygulama iki eşlenik görünüm saklar:
$$C_p(x),\ T_p(x)\quad \text{ için }1\le x\le v,$$
ve
$$C_p\!\left(\left\lfloor\frac{N}{i}\right\rfloor\right),\ T_p\!\left(\left\lfloor\frac{N}{i}\right\rfloor\right)\quad \text{ için }1\le i\le v.$$
Belleğin \(O(\sqrt N)\) düzeyinde kalmasının nedeni budur.
En küçük asal bölenler
$$s(2),\dots,s(10)=2,3,2,5,2,7,2,3,2$$
olduğundan doğru toplam \(28\)'dir.
Başlangıçta \(T_2(10)=2+3+\cdots+10=54\) olur.
\(p=2\) için
$$M_2(10)=C_2(5)-C_2(1)=4-0=4$$
elde edilir; bunlar \(4,6,8,10\) sayılarıdır. Ağırlıklı katkı \(2\cdot 4=8\) olur ve gerçek toplamları \(4+6+8+10=28\) filtreli toplamdan çıkarılınca \(26\) kalır.
\(p=3\) için, \(10\)'a kadar hayatta kalan küme artık \(\{2,3,5,7,9\}\)'dur. Bu kez
$$M_3(10)=C_3(3)-C_3(2)=2-1=1$$
bulunur; bu da \(9\)'a karşılık gelir. Ağırlıklı katkı \(3\)'tür ve \(9\) silinince geriye \(17\) kalır; bu da tam olarak \(2+3+5+7\) asal toplamıdır.
Sonuç olarak
$$S(10)=17+8+3=28.$$
C++, Python ve Java uygulamaları \(v=\lfloor\sqrt N\rfloor\) ile başlar ve dört tablo kurar: küçük argümanlar \(x\le v\) için filtreli adetler ve filtreli toplamlar, ayrıca \(\lfloor N/i\rfloor\) biçimindeki büyük argümanlar için aynı bilgiler. Başlangıç değerleri süzülmemiş adetler \(x-1\) ve süzülmemiş toplamlar \(\frac{x(x+1)}{2}-1\)'dir.
Daha sonra \(p=2,3,\dots,v\) üzerinden ilerlenir. Bir konumun asal olduğu, filtreli adedin \(p-1\) ile \(p\) arasında değişmesinden anlaşılır. Her asal için uygulama önce
$$p\left(C_p\!\left(\left\lfloor\frac{N}{p}\right\rfloor\right)-C_p(p-1)\right)$$
ifadesini cevap biriktiricisine ekler; bu, en küçük asal böleni \(p\) olan tüm bileşikleri hesaba katar. Ardından \(C\) ve \(T\) bağıntıları saklanan tüm argümanlara uygulanır; bölüm değeri \(\sqrt N\)'nin altında kalıyorsa küçük tablo, aksi halde büyük tablo kullanılır.
C++ ve Python uygulamaları toplamları süreç boyunca tam sayı olarak tutar ve \(10^9\) moduna yalnızca sonda iner. Java uygulaması ise güncellemeler sırasında toplam tablolarını \(10^9\) modunda tutarken adetleri tam sayıyla saklar; bu geçerlidir çünkü kullanılan tüm işlemler lineerdir ve istenen nihai cevap zaten yalnızca \(10^9\) modundadır. Asal döngüsü bittiğinde elde kalan filtreli toplam, \(N\)'ye kadar olan tüm asalların toplamıdır; biriktiriciye eklenince \(S(N)\) elde edilir.
\(v=\lfloor\sqrt N\rfloor\) olsun. Tablolar \(O(v)=O(\sqrt N)\) bellek kullanır. Her \(p\le v\) asalı için uygulama, büyük alan tablolarında yaklaşık \(\min\!\left(v,\left\lfloor N/p^2\right\rfloor\right)\) uzunlukta bir aralığı ve küçük alan tablolarında yaklaşık \(\max(0,v-p^2+1)\) uzunlukta bir aralığı günceller. Tüm asallar üzerinde toplandığında iş yükü yaklaşık olarak
$$O\!\left(\sum_{p\le v}\left(\min\!\left(v,\frac{N}{p^2}\right)+\max(0,v-p^2)\right)\right)$$
olur; bu da bu tür split-domain sieve için yaklaşık \(O\!\left(N^{3/4}/\log N\right)\) mertebesindedir. Asıl önemli nokta şudur: zaman ve bellek, \(N\)'ye lineer herhangi bir yaklaşımdan çok daha küçüktür; bu sayede \(N=10^{12}\) pratik hale gelir.
Para \(n\ge 2\), sea \(s(n)\) el menor factor primo de \(n\). Debemos calcular
$$S(N)=\sum_{n=2}^{N} s(n), \qquad N=10^{12},$$
y devolver el resultado módulo \(10^9\). Una criba directa hasta \(N\) tendría coste lineal en memoria y tiempo, así que la implementación sigue otra idea: observar cómo van desapareciendo los compuestos cuando los primos se procesan en orden creciente.
La observación central es que cada número compuesto se elimina exactamente una vez, justo cuando se alcanza su menor factor primo, mientras que los primos nunca se eliminan. A partir de ahí se construyen recurrencias acopladas para conteos filtrados y sumas filtradas.
Si \(n\) es primo, entonces \(s(n)=n\). Si \(n\) es compuesto, entonces \(s(n)\le \sqrt n\le \sqrt N\). Por tanto
$$S(N)=\sum_{\substack{q\le N\\ q\text{ primo}}} q+\sum_{p\le \sqrt N} p\,M_p(N),$$
donde \(M_p(N)\) es el número de enteros compuestos \(n\le N\) cuyo menor factor primo es exactamente \(p\). Así, el problema queda reducido a contar esos compuestos con eficiencia y, además, recuperar la suma de todos los primos hasta \(N\).
Para un umbral primo \(p\), definimos el conjunto superviviente
$$\mathcal{R}_p(x)=\left\{m\in\{2,\dots,x\}: s(m)\ge p\right\}\cup\left\{q\le x:q\text{ primo},\ q<p\right\}.$$
Este conjunto contiene dos clases de números: los primos menores que \(p\), que ya quedan preservados, y los números cuyos factores primos son todos al menos \(p\), de modo que todavía no han sido retirados. Definimos entonces
$$C_p(x)=\#\mathcal{R}_p(x), \qquad T_p(x)=\sum_{m\in\mathcal{R}_p(x)} m.$$
Al inicio no se ha filtrado nada, así que para \(p=2\) se tiene
$$C_2(x)=x-1,\qquad T_2(x)=\sum_{m=2}^{x} m=\frac{x(x+1)}{2}-1.$$
Una consecuencia útil es que \(C_p(p)-C_p(p-1)=1\) exactamente cuando \(p\) es primo, porque cualquier compuesto ya desapareció antes de alcanzar su propia posición.
Tomemos un primo \(p\). Cualquier compuesto \(n\le x\) con \(s(n)=p\) puede escribirse de forma única como
$$n=p\,m,$$
donde \(m\ge p\) y todos los factores primos de \(m\) son al menos \(p\). Dicho de otra forma, \(m\) pertenece a \(\mathcal{R}_p(\lfloor x/p\rfloor)\), pero los elementos menores que \(p\) deben excluirse porque son precisamente los primos más pequeños. Por ello
$$M_p(x)=C_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-C_p(p-1).$$
La contribución ponderada de todos esos compuestos es, por tanto,
$$p\,M_p(N)=p\left(C_p\!\left(\left\lfloor\frac{N}{p}\right\rfloor\right)-C_p(p-1)\right).$$
No aparece un término extra \(+p\) porque el propio primo \(p\) permanece en la suma filtrada y se añade al final junto con los demás primos.
Una vez identificados los compuestos cuyo menor factor primo es \(p\), deben eliminarse de las etapas posteriores. La recurrencia de conteo es
$$C_{p^+}(x)=C_p(x)-\left(C_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-C_p(p-1)\right),$$
donde \(p^+\) indica el estado justo después de procesar \(p\). La recurrencia análoga para las sumas elimina los valores compuestos reales \(p\,m\):
$$T_{p^+}(x)=T_p(x)-p\left(T_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-T_p(p-1)\right).$$
Cuando todos los primos \(p\le \sqrt N\) ya han sido procesados, cada compuesto ha sido eliminado exactamente una vez. La suma filtrada que queda es entonces simplemente la suma de todos los primos hasta \(N\):
$$T_{\mathrm{final}}(N)=\sum_{\substack{q\le N\\ q\text{ primo}}} q.$$
Sea
$$v=\left\lfloor\sqrt N\right\rfloor.$$
Cada argumento que aparece en las recurrencias es o bien a lo sumo \(v\), o bien de la forma \(\left\lfloor N/i\right\rfloor\) para algún \(1\le i\le v\). Esta es la compresión clásica por cocientes enteros: el número de valores distintos es solo \(O(\sqrt N)\), no \(O(N)\). Por eso la implementación mantiene dos vistas sincronizadas,
$$C_p(x),\ T_p(x)\quad \text{para }1\le x\le v,$$
y
$$C_p\!\left(\left\lfloor\frac{N}{i}\right\rfloor\right),\ T_p\!\left(\left\lfloor\frac{N}{i}\right\rfloor\right)\quad \text{para }1\le i\le v.$$
Esa es la razón por la que la memoria permanece en \(O(\sqrt N)\).
Los menores factores primos son
$$s(2),\dots,s(10)=2,3,2,5,2,7,2,3,2,$$
de modo que la suma correcta es \(28\).
Al principio, \(T_2(10)=2+3+\cdots+10=54\).
Para \(p=2\),
$$M_2(10)=C_2(5)-C_2(1)=4-0=4,$$
lo que corresponde a \(4,6,8,10\). Su contribución ponderada es \(2\cdot 4=8\), y su suma real \(4+6+8+10=28\) se elimina de la suma filtrada, dejando \(26\).
Para \(p=3\), el conjunto superviviente hasta \(10\) es \(\{2,3,5,7,9\}\). Entonces
$$M_3(10)=C_3(3)-C_3(2)=2-1=1,$$
que corresponde a \(9\). Su contribución ponderada es \(3\), y al retirar \(9\) queda \(17\), exactamente la suma de los primos \(2+3+5+7\).
Por lo tanto,
$$S(10)=17+8+3=28.$$
Las implementaciones en C++, Python y Java comienzan con \(v=\lfloor\sqrt N\rfloor\) y construyen cuatro tablas: conteos filtrados y sumas filtradas para argumentos pequeños \(x\le v\), además de las mismas magnitudes para argumentos grandes de la forma \(\lfloor N/i\rfloor\). Los valores iniciales son los conteos sin filtrar \(x-1\) y las sumas sin filtrar \(\frac{x(x+1)}{2}-1\).
Después recorren \(p=2,3,\dots,v\). Una posición se reconoce como prima exactamente cuando el conteo filtrado cambia entre \(p-1\) y \(p\). Para cada primo, la implementación añade primero
$$p\left(C_p\!\left(\left\lfloor\frac{N}{p}\right\rfloor\right)-C_p(p-1)\right)$$
al acumulador de la respuesta; eso contabiliza todos los compuestos cuyo menor factor primo es \(p\). A continuación aplica la recurrencia de \(C\) y \(T\) a todos los argumentos almacenados, tomando datos de la tabla pequeña o de la grande según si el cociente cae por debajo de \(\sqrt N\).
Las versiones de C++ y Python mantienen sumas enteras exactas durante todo el proceso y solo reducen módulo \(10^9\) al final. La versión de Java conserva las tablas de suma ya módulo \(10^9\) mientras mantiene exactos los conteos; eso sigue siendo correcto porque la recurrencia es lineal y la respuesta final solo se necesita módulo \(10^9\). Al terminar el bucle sobre primos, la suma filtrada restante es la suma de todos los primos hasta \(N\), y al sumarla al acumulador se obtiene \(S(N)\).
Sea \(v=\lfloor\sqrt N\rfloor\). Las tablas usan \(O(v)=O(\sqrt N)\) memoria. Para cada primo \(p\le v\), la implementación actualiza un tramo de longitud aproximada \(\min\!\left(v,\left\lfloor N/p^2\right\rfloor\right)\) en las tablas del dominio grande y un tramo de longitud aproximada \(\max(0,v-p^2+1)\) en las tablas del dominio pequeño. Sumado sobre todos los primos, el trabajo es aproximadamente
$$O\!\left(\sum_{p\le v}\left(\min\!\left(v,\frac{N}{p^2}\right)+\max(0,v-p^2)\right)\right),$$
lo que para esta criba de dominio partido es del orden de \(O\!\left(N^{3/4}/\log N\right)\). El mensaje importante es práctico: tanto el tiempo como la memoria quedan muy por debajo de cualquier método lineal en \(N\), y por eso \(N=10^{12}\) resulta abordable.
对 \(n\ge 2\)，记 \(s(n)\) 为 \(n\) 的最小质因子。题目要求计算
$$S(N)=\sum_{n=2}^{N} s(n), \qquad N=10^{12},$$
并输出其模 \(10^9\) 的结果。若直接做到 \(N\) 的线性筛，时间和空间都会过大，所以实现采用的是另一条思路：按质数从小到大推进，追踪哪些合数会在什么时候被“删掉”。
核心事实是：每个合数只会被删除一次，而且恰好在处理到它的最小质因子时被删除；相反，质数永远不会被删除。围绕这件事，可以建立一套同时维护“过滤后个数”和“过滤后元素和”的递推。
如果 \(n\) 是质数，那么 \(s(n)=n\)。如果 \(n\) 是合数，那么 \(s(n)\le \sqrt n\le \sqrt N\)。因此
$$S(N)=\sum_{\substack{q\le N\\ q\text{ 为质数}}} q+\sum_{p\le \sqrt N} p\,M_p(N),$$
其中 \(M_p(N)\) 表示不超过 \(N\) 的合数中，最小质因子恰好等于 \(p\) 的个数。于是问题被转化为两件事：一是高效求出所有这样的 \(M_p(N)\)，二是得到不超过 \(N\) 的全部质数之和。
对一个质数阈值 \(p\)，定义存活集合
$$\mathcal{R}_p(x)=\left\{m\in\{2,\dots,x\}: s(m)\ge p\right\}\cup\left\{q\le x:q\text{ 为质数},\ q<p\right\}.$$
这个集合里有两类元素。第一类是已经确认的小质数 \(q<p\)，它们以后不会再被删掉。第二类是所有质因子都至少为 \(p\) 的数，也就是当前还没轮到删除的数。接着定义
$$C_p(x)=\#\mathcal{R}_p(x), \qquad T_p(x)=\sum_{m\in\mathcal{R}_p(x)} m.$$
在最开始，什么都还没有筛掉，所以当 \(p=2\) 时有
$$C_2(x)=x-1,\qquad T_2(x)=\sum_{m=2}^{x} m=\frac{x(x+1)}{2}-1.$$
这里还有一个非常有用的判定：当且仅当 \(p\) 是质数时，\(C_p(p)-C_p(p-1)=1\)。原因很简单，任何合数在轮到自己之前就已经会被更小的质因子删除掉。
现在固定一个质数 \(p\)。任意一个满足 \(n\le x\) 且 \(s(n)=p\) 的合数，都可以唯一写成
$$n=p\,m,$$
其中 \(m\ge p\)，并且 \(m\) 的所有质因子都至少是 \(p\)。换句话说，\(m\) 必须属于 \(\mathcal{R}_p(\lfloor x/p\rfloor)\)。不过其中小于 \(p\) 的元素要排除掉，因为那一部分正好就是更小的质数。于是得到
$$M_p(x)=C_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-C_p(p-1).$$
因此，这一批合数对总答案的加权贡献就是
$$p\,M_p(N)=p\left(C_p\!\left(\left\lfloor\frac{N}{p}\right\rfloor\right)-C_p(p-1)\right).$$
这里没有额外的 \(+p\)，因为质数 \(p\) 自己并不会在这一步被删掉，它仍留在过滤后的和里，最后会和其他质数一起统一加入答案。
一旦“最小质因子为 \(p\)”的合数已经识别出来，就必须把它们从后续阶段中删除。对应的个数递推式是
$$C_{p^+}(x)=C_p(x)-\left(C_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-C_p(p-1)\right),$$
这里 \(p^+\) 表示“刚处理完质数 \(p\) 后”的状态。对于和来说，被删除的是实际的合数值 \(p\,m\)，所以递推式变成
$$T_{p^+}(x)=T_p(x)-p\left(T_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-T_p(p-1)\right).$$
当所有满足 \(p\le \sqrt N\) 的质数都处理完之后，每个合数都恰好被删除一次，因此最后剩下的过滤和正好就是所有不超过 \(N\) 的质数之和：
$$T_{\mathrm{final}}(N)=\sum_{\substack{q\le N\\ q\text{ 为质数}}} q.$$
记
$$v=\left\lfloor\sqrt N\right\rfloor.$$
递推中出现的参数只有两种形态：一种是不超过 \(v\) 的小参数，另一种是 \(\left\lfloor N/i\right\rfloor\) 这样的整除商，其中 \(1\le i\le v\)。这就是经典的整除分块压缩思想：不同的整除商只有 \(O(\sqrt N)\) 种，而不是 \(O(N)\) 种。因此实现只维护两组同步表：
$$C_p(x),\ T_p(x)\quad \text{对 }1\le x\le v,$$
以及
$$C_p\!\left(\left\lfloor\frac{N}{i}\right\rfloor\right),\ T_p\!\left(\left\lfloor\frac{N}{i}\right\rfloor\right)\quad \text{对 }1\le i\le v.$$
这就是为什么内存消耗能控制在 \(O(\sqrt N)\) 量级。
此时最小质因子序列为
$$s(2),\dots,s(10)=2,3,2,5,2,7,2,3,2,$$
所以正确答案应为 \(28\)。
一开始，\(T_2(10)=2+3+\cdots+10=54\)。
当 \(p=2\) 时，
$$M_2(10)=C_2(5)-C_2(1)=4-0=4,$$
对应的正是 \(4,6,8,10\)。它们对答案的加权贡献是 \(2\cdot 4=8\)，而它们本身的和 \(4+6+8+10=28\) 会从过滤和中被扣掉，于是过滤和变成 \(26\)。
当 \(p=3\) 时，当前在 \(10\) 以内仍存活的集合是 \(\{2,3,5,7,9\}\)。于是
$$M_3(10)=C_3(3)-C_3(2)=2-1=1,$$
这对应的就是 \(9\)。它对答案的加权贡献是 \(3\)，从过滤和中删去 \(9\) 以后，剩下 \(17\)，这正好是质数 \(2+3+5+7\) 的和。
因此
$$S(10)=17+8+3=28.$$
C++、Python 和 Java 三个实现都会先计算 \(v=\lfloor\sqrt N\rfloor\)，然后建立四张表：针对小参数 \(x\le v\) 的过滤后个数与过滤后和，以及针对大参数 \(\lfloor N/i\rfloor\) 的同类信息。初始值就是未过滤时的结果，也就是个数 \(x-1\) 与总和 \(\frac{x(x+1)}{2}-1\)。
随后程序按 \(p=2,3,\dots,v\) 顺序推进。某个位置是否对应质数，是通过比较 \(p-1\) 与 \(p\) 处的过滤后个数是否发生变化来判断的。对于每个质数，实现先把
$$p\left(C_p\!\left(\left\lfloor\frac{N}{p}\right\rfloor\right)-C_p(p-1)\right)$$
加入答案累加器，这一步恰好统计了“最小质因子为 \(p\)”的全部合数。接着，程序把 \(C\) 与 \(T\) 的递推应用到所有存储的参数上；如果所需商值落在 \(\sqrt N\) 以下，就从小表读取，否则就从大表读取。
C++ 和 Python 实现全程保留精确整数和，只在最后再对 \(10^9\) 取模。Java 实现则在更新过程中就把和表保持在 \(10^9\) 模下，而计数仍然保持精确；这同样正确，因为整个递推只涉及线性组合，最终要求的本来就是模 \(10^9\) 的答案。质数循环结束后，剩余的过滤和就是不超过 \(N\) 的全部质数之和，把它加到累加器上就得到 \(S(N)\)。
设 \(v=\lfloor\sqrt N\rfloor\)。这些表一共使用 \(O(v)=O(\sqrt N)\) 的空间。对每个 \(p\le v\) 的质数，实现都会更新大域表中长度约为 \(\min\!\left(v,\left\lfloor N/p^2\right\rfloor\right)\) 的一段，以及小域表中长度约为 \(\max(0,v-p^2+1)\) 的一段。把所有质数的工作量加起来，大致为
$$O\!\left(\sum_{p\le v}\left(\min\!\left(v,\frac{N}{p^2}\right)+\max(0,v-p^2)\right)\right),$$
对这种 split-domain sieve 来说，大约是 \(O\!\left(N^{3/4}/\log N\right)\) 的量级。更关键的是工程意义：时间和空间都远小于任何按 \(N\) 线性推进的方法，所以 \(N=10^{12}\) 才能实际处理。
Для \(n\ge 2\) обозначим через \(s(n)\) наименьший простой делитель числа \(n\). Требуется вычислить
$$S(N)=\sum_{n=2}^{N} s(n), \qquad N=10^{12},$$
и вернуть ответ по модулю \(10^9\). Прямое просеивание до \(N\) было бы слишком дорогим по памяти и времени, поэтому реализация отслеживает, как составные числа исчезают по мере обработки простых в возрастающем порядке.
Главное наблюдение таково: каждое составное число удаляется ровно один раз, а именно при обработке его наименьшего простого делителя, тогда как простые числа не удаляются никогда. На этой идее строятся связанные рекуррентные формулы для отфильтрованных количеств и отфильтрованных сумм.
Если \(n\) простое, то \(s(n)=n\). Если \(n\) составное, то \(s(n)\le \sqrt n\le \sqrt N\). Следовательно,
$$S(N)=\sum_{\substack{q\le N\\ q\text{ простое}}} q+\sum_{p\le \sqrt N} p\,M_p(N),$$
где \(M_p(N)\) означает число составных \(n\le N\), у которых наименьший простой делитель равен \(p\). Значит, задача сводится к эффективному подсчету этих составных чисел и одновременному восстановлению суммы всех простых до \(N\).
Для порога \(p\), являющегося простым числом, введем множество выживших
$$\mathcal{R}_p(x)=\left\{m\in\{2,\dots,x\}: s(m)\ge p\right\}\cup\left\{q\le x:q\text{ простое},\ q<p\right\}.$$
Здесь находятся два типа чисел: простые числа меньше \(p\), которые уже никогда не будут удалены, и числа, все простые делители которых не меньше \(p\), то есть еще не затронутые фильтрацией. Теперь положим
$$C_p(x)=\#\mathcal{R}_p(x), \qquad T_p(x)=\sum_{m\in\mathcal{R}_p(x)} m.$$
В самом начале никакой фильтрации нет, поэтому при \(p=2\)
$$C_2(x)=x-1,\qquad T_2(x)=\sum_{m=2}^{x} m=\frac{x(x+1)}{2}-1.$$
Отсюда следует удобный критерий: \(C_p(p)-C_p(p-1)=1\) тогда и только тогда, когда \(p\) простое, потому что любое составное число исчезает раньше, чем до него доходит внешний цикл.
Зафиксируем простое \(p\). Любое составное число \(n\le x\) с условием \(s(n)=p\) единственным образом представляется как
$$n=p\,m,$$
где \(m\ge p\), а все простые делители \(m\) не меньше \(p\). Иначе говоря, \(m\) лежит в \(\mathcal{R}_p(\lfloor x/p\rfloor)\), но элементы меньше \(p\) нужно исключить, так как это в точности меньшие простые. Поэтому
$$M_p(x)=C_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-C_p(p-1).$$
Тогда взвешенный вклад всех таких составных чисел равен
$$p\,M_p(N)=p\left(C_p\!\left(\left\lfloor\frac{N}{p}\right\rfloor\right)-C_p(p-1)\right).$$
Дополнительного члена \(+p\) здесь нет, потому что само простое \(p\) остается в фильтрованной сумме и будет добавлено позже вместе с остальными простыми.
После того как составные числа с наименьшим простым делителем \(p\) найдены, их нужно удалить из всех последующих состояний. Рекуррентная формула для количества имеет вид
$$C_{p^+}(x)=C_p(x)-\left(C_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-C_p(p-1)\right),$$
где \(p^+\) означает состояние сразу после обработки \(p\). Для сумм нужно вычесть реальные значения составных чисел \(p\,m\), поэтому
$$T_{p^+}(x)=T_p(x)-p\left(T_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-T_p(p-1)\right).$$
После обработки всех простых \(p\le \sqrt N\) каждое составное число удалено ровно один раз, и оставшаяся фильтрованная сумма равна просто сумме всех простых чисел до \(N\):
$$T_{\mathrm{final}}(N)=\sum_{\substack{q\le N\\ q\text{ простое}}} q.$$
Положим
$$v=\left\lfloor\sqrt N\right\rfloor.$$
Любой аргумент, который возникает в рекуррентных формулах, либо не превосходит \(v\), либо имеет вид \(\left\lfloor N/i\right\rfloor\) при некотором \(1\le i\le v\). Это стандартное сжатие по значениям целой части частного: различных значений всего \(O(\sqrt N)\), а не \(O(N)\). Поэтому реализация хранит две согласованные таблицы,
$$C_p(x),\ T_p(x)\quad \text{для }1\le x\le v,$$
и
$$C_p\!\left(\left\lfloor\frac{N}{i}\right\rfloor\right),\ T_p\!\left(\left\lfloor\frac{N}{i}\right\rfloor\right)\quad \text{для }1\le i\le v.$$
Именно поэтому память остается порядка \(O(\sqrt N)\).
Последовательность наименьших простых делителей равна
$$s(2),\dots,s(10)=2,3,2,5,2,7,2,3,2,$$
так что правильная сумма равна \(28\).
В начале \(T_2(10)=2+3+\cdots+10=54\).
Для \(p=2\) получаем
$$M_2(10)=C_2(5)-C_2(1)=4-0=4,$$
что соответствует числам \(4,6,8,10\). Их взвешенный вклад равен \(2\cdot 4=8\), а их обычная сумма \(4+6+8+10=28\) вычитается из фильтрованной суммы, после чего остается \(26\).
Для \(p=3\) текущее выжившее множество до \(10\) равно \(\{2,3,5,7,9\}\). Тогда
$$M_3(10)=C_3(3)-C_3(2)=2-1=1,$$
то есть речь идет о числе \(9\). Его взвешенный вклад равен \(3\), а после удаления \(9\) остается \(17\), что точно совпадает с суммой простых \(2+3+5+7\).
Следовательно,
$$S(10)=17+8+3=28.$$
Реализации на C++, Python и Java начинают с вычисления \(v=\lfloor\sqrt N\rfloor\) и строят четыре таблицы: фильтрованные количества и фильтрованные суммы для малых аргументов \(x\le v\), а также те же величины для больших аргументов вида \(\lfloor N/i\rfloor\). Начальные значения равны нефильтрованным количествам \(x-1\) и нефильтрованным суммам \(\frac{x(x+1)}{2}-1\).
Затем выполняется проход по \(p=2,3,\dots,v\). Позиция считается простой тогда и только тогда, когда фильтрованное количество меняется между \(p-1\) и \(p\). Для каждого простого числа реализация сначала прибавляет
$$p\left(C_p\!\left(\left\lfloor\frac{N}{p}\right\rfloor\right)-C_p(p-1)\right)$$
к аккумулятору ответа; этим учитываются все составные числа с наименьшим простым делителем \(p\). После этого к каждому сохраненному аргументу применяется рекурсия для \(C\) и \(T\), причем данные берутся из малой или большой таблицы в зависимости от того, лежит ли нужное значение частного ниже \(\sqrt N\).
Реализации на C++ и Python хранят точные целочисленные суммы на всем протяжении вычисления и берут остаток по модулю \(10^9\) только в самом конце. Реализация на Java поддерживает таблицы сумм уже по модулю \(10^9\), сохраняя точность только в таблицах количеств; это корректно, потому что рекурсия линейна, а конечный ответ и так нужен лишь по модулю \(10^9\). После завершения цикла по простым оставшаяся фильтрованная сумма есть сумма всех простых до \(N\); прибавив ее к аккумулятору, программа получает \(S(N)\).
Пусть \(v=\lfloor\sqrt N\rfloor\). Таблицы занимают \(O(v)=O(\sqrt N)\) памяти. Для каждого простого \(p\le v\) реализация обновляет участок длины примерно \(\min\!\left(v,\left\lfloor N/p^2\right\rfloor\right)\) в таблицах большого домена и участок длины примерно \(\max(0,v-p^2+1)\) в таблицах малого домена. В сумме по всем простым это дает приблизительно
$$O\!\left(\sum_{p\le v}\left(\min\!\left(v,\frac{N}{p^2}\right)+\max(0,v-p^2)\right)\right),$$
что для такого split-domain sieve соответствует порядку \(O\!\left(N^{3/4}/\log N\right)\). Но практически важнее другое: и время, и память оказываются существенно меньше, чем у любого метода, линейного по \(N\), поэтому значение \(N=10^{12}\) становится достижимым.
لـ \(n\ge 2\)، نرمز بـ \(s(n)\) إلى أصغر عامل أولي للعدد \(n\). المطلوب هو حساب
$$S(N)=\sum_{n=2}^{N} s(n), \qquad N=10^{12},$$
ثم إرجاع الناتج بترديد \(10^9\). تنفيذ غربال مباشر حتى \(N\) سيكون مكلفًا جدًا في الزمن والذاكرة، لذلك تعتمد الخوارزمية على تتبّع اللحظة التي تختفي فيها الأعداد المركبة أثناء المرور على الأعداد الأولية تصاعديًا.
الفكرة الأساسية هي أن كل عدد مركب يُزال مرة واحدة فقط، وذلك عند معالجة أصغر عامل أولي له، بينما الأعداد الأولية لا تُزال أبدًا. ومن هذه الفكرة نحصل على علاقات تكرارية مترابطة لعدّ العناصر المتبقية ولمجموعها.
إذا كان \(n\) أوليًا فلدينا \(s(n)=n\). وإذا كان \(n\) مركبًا فإن \(s(n)\le \sqrt n\le \sqrt N\). لذلك
$$S(N)=\sum_{\substack{q\le N\\ q\text{ prime}}} q+\sum_{p\le \sqrt N} p\,M_p(N),$$
حيث إن \(M_p(N)\) هو عدد الأعداد المركبة \(n\le N\) التي يساوي أصغر عامل أولي لها \(p\). وهكذا تتحول المسألة إلى حساب هذه الأعداد المركبة بكفاءة، وفي الوقت نفسه استخراج مجموع جميع الأعداد الأولية حتى \(N\).
لعتبة أولية \(p\)، نعرّف مجموعة العناصر الباقية كما يلي:
$$\mathcal{R}_p(x)=\left\{m\in\{2,\dots,x\}: s(m)\ge p\right\}\cup\left\{q\le x:q\text{ prime},\ q<p\right\}.$$
تحتوي هذه المجموعة على نوعين من الأعداد: الأعداد الأولية الأصغر من \(p\) التي تبقى دائمًا، والأعداد التي جميع عواملها الأولية لا تقل عن \(p\)، أي التي لم يحن وقت حذفها بعد. ثم نعرّف
$$C_p(x)=\#\mathcal{R}_p(x), \qquad T_p(x)=\sum_{m\in\mathcal{R}_p(x)} m.$$
في البداية لا تكون أي عملية ترشيح قد حدثت، ولذلك عندما \(p=2\) يكون
$$C_2(x)=x-1,\qquad T_2(x)=\sum_{m=2}^{x} m=\frac{x(x+1)}{2}-1.$$
ومن النتائج المفيدة هنا أن \(C_p(p)-C_p(p-1)=1\) إذا وفقط إذا كان \(p\) عددًا أوليًا، لأن كل عدد مركب يختفي قبل أن يصل الدور إلى فهرسه نفسه.
خذ عددًا أوليًا \(p\). كل عدد مركب \(n\le x\) يحقق \(s(n)=p\) يمكن كتابته بصورة وحيدة على الشكل
$$n=p\,m,$$
حيث \(m\ge p\) وجميع العوامل الأولية لـ \(m\) لا تقل عن \(p\). وهذا يعني أن \(m\) ينتمي إلى \(\mathcal{R}_p(\lfloor x/p\rfloor)\)، لكن يجب استبعاد العناصر الأصغر من \(p\) لأنها تمثل تمامًا الأعداد الأولية الأصغر. ومن ثم نحصل على
$$M_p(x)=C_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-C_p(p-1).$$
وعليه فإن المساهمة الموزونة لجميع هذه الأعداد المركبة تساوي
$$p\,M_p(N)=p\left(C_p\!\left(\left\lfloor\frac{N}{p}\right\rfloor\right)-C_p(p-1)\right).$$
ولا يوجد حد إضافي من نوع \(+p\)، لأن العدد الأولي \(p\) نفسه يبقى ضمن المجموع المصفّى وسيُضاف في النهاية مع بقية الأعداد الأولية.
بعد تحديد الأعداد المركبة التي أصغر عامل أولي لها هو \(p\)، يجب حذفها من جميع المراحل اللاحقة. علاقة التكرار الخاصة بالعدّ هي
$$C_{p^+}(x)=C_p(x)-\left(C_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-C_p(p-1)\right),$$
حيث يرمز \(p^+\) إلى الحالة بعد الانتهاء مباشرة من معالجة \(p\). أما بالنسبة إلى المجاميع فنحن نحذف القيم المركبة الفعلية \(p\,m\)، ولذلك تصبح العلاقة
$$T_{p^+}(x)=T_p(x)-p\left(T_p\!\left(\left\lfloor\frac{x}{p}\right\rfloor\right)-T_p(p-1)\right).$$
وبعد معالجة جميع الأعداد الأولية \(p\le \sqrt N\)، يكون كل عدد مركب قد حُذف مرة واحدة بالضبط، ويصبح المجموع المصفّى المتبقي مساويًا لمجموع جميع الأعداد الأولية حتى \(N\):
$$T_{\mathrm{final}}(N)=\sum_{\substack{q\le N\\ q\text{ prime}}} q.$$
لنضع
$$v=\left\lfloor\sqrt N\right\rfloor.$$
كل وسيط يظهر في علاقات التكرار يكون إما أصغر من أو يساوي \(v\)، أو من الشكل \(\left\lfloor N/i\right\rfloor\) لبعض \(1\le i\le v\). وهذه هي فكرة ضغط قيم القسمة الصحيحة المعروفة: عدد القيم المختلفة ليس \(O(N)\)، بل \(O(\sqrt N)\) فقط. لذلك يحتفظ التنفيذ بعرضين متزامنين هما
$$C_p(x),\ T_p(x)\quad \text{for }1\le x\le v,$$
و
$$C_p\!\left(\left\lfloor\frac{N}{i}\right\rfloor\right),\ T_p\!\left(\left\lfloor\frac{N}{i}\right\rfloor\right)\quad \text{for }1\le i\le v.$$
ولهذا السبب يبقى استهلاك الذاكرة في حدود \(O(\sqrt N)\).
أصغر العوامل الأولية هي
$$s(2),\dots,s(10)=2,3,2,5,2,7,2,3,2,$$
ومن ثم فالمجموع الصحيح هو \(28\).
في البداية لدينا \(T_2(10)=2+3+\cdots+10=54\).
عند \(p=2\)، نجد أن
$$M_2(10)=C_2(5)-C_2(1)=4-0=4,$$
وهذا يوافق الأعداد \(4,6,8,10\). مساهمتها الموزونة هي \(2\cdot 4=8\)، ومجموعها الحقيقي \(4+6+8+10=28\) يُطرح من المجموع المصفّى، فيتبقى \(26\).
وعند \(p=3\)، تصبح المجموعة الباقية حتى \(10\) هي \(\{2,3,5,7,9\}\). وعندها
$$M_3(10)=C_3(3)-C_3(2)=2-1=1,$$
وهذا يوافق العدد \(9\). مساهمته الموزونة هي \(3\)، وبعد حذف \(9\) يتبقى \(17\)، وهو بالضبط مجموع الأعداد الأولية \(2+3+5+7\).
إذن
$$S(10)=17+8+3=28.$$
تبدأ تطبيقات C++ وPython وJava جميعًا بحساب \(v=\lfloor\sqrt N\rfloor\)، ثم تبني أربع جداول: عددًا ومجموعًا مفلترين للقيم الصغيرة \(x\le v\)، ثم المقدارين نفسيهما للقيم الكبيرة من الشكل \(\lfloor N/i\rfloor\). القيم الابتدائية هي العدّ غير المصفّى \(x-1\) والمجموع غير المصفّى \(\frac{x(x+1)}{2}-1\).
بعد ذلك يمر التنفيذ على \(p=2,3,\dots,v\). ويُعرف أن الموضع يمثل عددًا أوليًا إذا تغيّر العدّ المصفّى بين \(p-1\) و\(p\). لكل عدد أولي، يضيف التنفيذ أولًا
$$p\left(C_p\!\left(\left\lfloor\frac{N}{p}\right\rfloor\right)-C_p(p-1)\right)$$
إلى مجمّع الجواب، وبذلك تُحسب جميع الأعداد المركبة التي أصغر عامل أولي لها هو \(p\). ثم تُطبَّق علاقتا \(C\) و\(T\) على كل وسيط مخزّن، مع اختيار الجدول الصغير أو الكبير بحسب ما إذا كانت قيمة القسمة المطلوبة تقع دون \(\sqrt N\) أم لا.
يحتفظ تنفيذا C++ وPython بالمجاميع الدقيقة طوال الحساب، ثم يأخذان الباقي بترديد \(10^9\) في النهاية فقط. أما تنفيذ Java فيحتفظ بجداول المجاميع بترديد \(10^9\) أثناء التحديث، مع إبقاء جداول العدّ دقيقة؛ وهذا صحيح لأن العلاقات خطية ولأن المطلوب النهائي أصلًا هو الجواب modulo \(10^9\). وبعد انتهاء حلقة الأعداد الأولية، يكون المجموع المصفّى المتبقي هو مجموع جميع الأعداد الأولية حتى \(N\)، وبإضافته إلى المجمّع نحصل على \(S(N)\).
ليكن \(v=\lfloor\sqrt N\rfloor\). تستخدم الجداول ذاكرة مقدارها \(O(v)=O(\sqrt N)\). ولكل عدد أولي \(p\le v\)، يحدّث التنفيذ مقطعًا طوله تقريبًا \(\min\!\left(v,\left\lfloor N/p^2\right\rfloor\right)\) في جداول المجال الكبير، ومقطعًا طوله تقريبًا \(\max(0,v-p^2+1)\) في جداول المجال الصغير. وبجمع العمل على جميع الأعداد الأولية نحصل تقريبًا على
$$O\!\left(\sum_{p\le v}\left(\min\!\left(v,\frac{N}{p^2}\right)+\max(0,v-p^2)\right)\right),$$
وهو من رتبة \(O\!\left(N^{3/4}/\log N\right)\) تقريبًا لهذا النوع من الغربلة ذات المجالين. لكن الأهم عمليًا هو أن الزمن والذاكرة أصغر بكثير من أي طريقة خطية في \(N\)، ولذلك يصبح التعامل مع \(N=10^{12}\) ممكنًا.