For \(n \ge 2\), let \(P(n)\) denote the largest prime factor of \(n\). We must compute
$$S(N)=\sum_{n=2}^{N} P(n)$$
for \(N=201820182018\), modulo \(10^9\). A direct sieve up to \(N\) is completely impractical, so the solution reorganizes the sum by largest prime factor and evaluates the resulting prime sums with a Min_25-style prime-sum transform plus a sparse recursion over prime powers.
Every integer contributes exactly one prime, namely its largest prime factor. The key is to separate that terminal prime from the rest of the factorization and then count the remaining cofactor in a structured way.
If \(P(n)=p\), then \(n\) can be written as
$$n=p\,m,$$
where every prime factor of \(m\) is at most \(p\). Conversely, any product \(p\,m\) with \(p\) prime and all prime factors of \(m\) at most \(p\) has largest prime factor \(p\).
Therefore
$$S(N)=\sum_{p\le N} p\,\Psi\left(\left\lfloor\frac{N}{p}\right\rfloor,p\right),$$
where \(\Psi(x,y)\) is the number of positive integers \(\le x\) whose prime factors are all \(\le y\). So the whole problem becomes a weighted count of smooth cofactors.
Write the cofactor in increasing prime order:
$$m=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t},\qquad r_1<r_2<\cdots<r_t\le p.$$
Then every \(n\le N\) has a unique representation
$$n=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t}p,$$
where \(p=P(n)\). This uniqueness is the reason the recursion can enumerate factorizations without double counting: primes are introduced strictly in increasing order.
If the largest prime appears with exponent \(b\ge 1\), then the cofactor contains \(p^{b-1}\), while the final factor \(p\) is the one that contributes to the sum.
Let \(p_1<p_2<\cdots\) be the primes. For a fixed index \(j\), define
$$\Sigma_j(x)=\sum_{p_j\le q\le x,\ q\text{ prime}} q.$$
Now suppose we have already fixed a prefix made of smaller prime powers, and the remaining quotient bound is \(R\). Let \(F(R,j)\) be the total contribution from this state when the next admissible prime is \(p_j\). Then
$$F(R,j)=\Sigma_j(R)+\sum_{i\ge j,\ p_i^2\le R}\ \sum_{e\ge 1,\ p_i^{e+1}\le R}\left(F\left(\left\lfloor\frac{R}{p_i^e}\right\rfloor,i+1\right)+p_i\right).$$
The first term counts the case where we stop immediately with one terminal prime \(q\ge p_j\). The double sum chooses the next prime \(p_i\), inserts \(p_i^e\) into the smooth part, and leaves one more copy of \(p_i\) as the possible largest prime. The extra \(+p_i\) is exactly the contribution from numbers whose largest prime factor is \(p_i\) itself.
The final answer is
$$S(N)=F(N,1).$$
The recursion constantly needs values of \(\Sigma_j(R)\), so it must be able to query prime sums up to many different bounds very quickly. The implementation prepares two synchronized table families:
one indexed directly by \(x\le \lfloor\sqrt N\rfloor\), and one indexed by quotient values \(\left\lfloor N/x\right\rfloor\).
They start from the naive quantities
$$C(x)=x-1,\qquad T(x)=\sum_{k=2}^{x}k=\frac{x(x+1)}{2}-1,$$
and then remove composite contributions prime by prime in the standard Min_25 manner. After preprocessing, the tables can return both the number of primes up to \(x\) and the sum of primes up to \(x\):
$$\pi(x)=\#\{q\le x:q\text{ prime}\},\qquad \Sigma(x)=\sum_{q\le x,\ q\text{ prime}} q.$$
Interval prime sums are obtained by subtraction:
$$\Sigma_j(R)=\Sigma(R)-\Sigma(p_j-1).$$
Take any \(n\le N\) with factorization
$$n=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t}p^b,\qquad r_1<r_2<\cdots<r_t<p.$$
The recursion follows one and only one path: it picks \(r_1^{a_1}\), then \(r_2^{a_2}\), and so on, always moving to larger primes. After all smaller primes have been fixed, the terminal prime \(p\) is counted either by an interval prime-sum term when \(b=1\), or by one of the direct \(+p\) terms when \(b\ge 2\). No other path can create the same factorization because the prime order is strictly increasing.
The largest prime factors are
$$P(2)=2,\ P(3)=3,\ P(4)=2,\ P(5)=5,\ P(6)=3,\ P(7)=7,\ P(8)=2,\ P(9)=3,\ P(10)=5,$$
so
$$S(10)=2+3+2+5+3+7+2+3+5=32.$$
The recursion sees the same total as follows. The root prime-sum term gives
$$\Sigma(10)=2+3+5+7=17.$$
Then the branch for \(2\) contributes \(2\) for \(4=2^2\), another \(2\) for \(8=2^3\), and \(3+5\) for \(6=2\cdot 3\) and \(10=2\cdot 5\). The branch for \(3\) contributes \(3\) for \(9=3^2\). Hence
$$17+2+2+(3+5)+3=32.$$
The C++, Python, and Java implementations follow the same algorithmic structure. They first set \(M=\lfloor\sqrt N\rfloor\) and build two families of tables, one for direct arguments \(x\le M\) and one for quotient arguments \(\lfloor N/x\rfloor\). These tables are initialized with counts of integers from \(2\) onward and with the corresponding arithmetic-series sums.
Next, the implementation sweeps through the primes up to \(M\). Each newly discovered prime updates both families of tables so that composite contributions created by that prime are removed. After this preprocessing, the implementation can answer prime-count and prime-sum queries for every bound that appears later in the recursion.
The recursive stage then explores prime powers in increasing prime order. For a current bound \(R\), it first adds the sum of all admissible terminal primes in the interval \([p_j,R]\). It then tries each next prime \(p_i\) with \(p_i^2\le R\), repeatedly divides the bound by \(p_i\), recurses on the reduced bound with a stricter lower bound on the next prime, and adds one direct contribution of \(p_i\) for each extra copy of that prime. Every addition is reduced modulo \(10^9\).
The Python implementation is only a thin bridge to the same compiled algorithm, so the mathematics and the execution strategy are identical in all three languages.
Let \(M=\lfloor\sqrt N\rfloor\). The preprocessing stores \(O(M)\) values. Its running time follows the usual Min_25-style profile: it is sublinear in \(N\) and grows roughly like \(O(N^{3/4}/\log N)\) for this kind of frontier update. The recursive prime-power search is sparse because it only continues while \(p^2\le R\), so it is far smaller than a full scan up to \(N\). The overall memory usage is \(O(\sqrt N)\).
Für \(n \ge 2\) bezeichne \(P(n)\) den größten Primfaktor von \(n\). Gesucht ist
$$S(N)=\sum_{n=2}^{N} P(n)$$
für \(N=201820182018\) modulo \(10^9\). Ein direktes Sieb bis \(N\) ist unmöglich, daher ordnet die Lösung die Summe nach dem größten Primfaktor um und wertet die entstehenden Primzahlsummen mit einer Min_25-artigen Transformation plus einer dünnen Rekursion über Primzahlpotenzen aus.
Jede ganze Zahl trägt genau eine Primzahl zur Summe bei, nämlich ihren größten Primfaktor. Deshalb trennt man diesen letzten Primfaktor vom restlichen Anteil der Zerlegung.
Gilt \(P(n)=p\), so kann man schreiben
$$n=p\,m,$$
wobei alle Primfaktoren von \(m\) höchstens \(p\) sind. Umgekehrt hat jedes Produkt \(p\,m\) mit primem \(p\) und nur Primfaktoren \(\le p\) im Kofaktor tatsächlich den größten Primfaktor \(p\).
Also gilt
$$S(N)=\sum_{p\le N} p\,\Psi\left(\left\lfloor\frac{N}{p}\right\rfloor,p\right),$$
wobei \(\Psi(x,y)\) die Anzahl positiver ganzer Zahlen \(\le x\) bezeichnet, deren Primfaktoren alle \(\le y\) sind. Das Problem wird damit zu einer gewichteten Zählung glatter Kofaktoren.
Schreibe den Kofaktor in aufsteigender Primordnung:
$$m=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t},\qquad r_1<r_2<\cdots<r_t\le p.$$
Dann besitzt jedes \(n\le N\) die eindeutige Darstellung
$$n=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t}p,$$
wobei \(p=P(n)\) ist. Genau diese Eindeutigkeit verhindert Doppelzählungen: Die Rekursion fügt Primzahlen strikt in wachsender Reihenfolge hinzu.
Tritt der größte Primfaktor mit Exponent \(b\ge 1\) auf, dann enthält der Kofaktor \(p^{b-1}\), während das letzte \(p\) der eigentliche Summand ist.
Seien \(p_1<p_2<\cdots\) die Primzahlen. Für einen festen Index \(j\) definieren wir
$$\Sigma_j(x)=\sum_{p_j\le q\le x,\ q\text{ prim}} q.$$
Nun sei bereits ein Präfix aus kleineren Primzahlpotenzen festgelegt, und \(R\) sei die verbleibende Quotientenschranke. Bezeichne \(F(R,j)\) den Gesamtbeitrag aus diesem Zustand, wenn die nächste zulässige Primzahl \(p_j\) ist. Dann gilt
$$F(R,j)=\Sigma_j(R)+\sum_{i\ge j,\ p_i^2\le R}\ \sum_{e\ge 1,\ p_i^{e+1}\le R}\left(F\left(\left\lfloor\frac{R}{p_i^e}\right\rfloor,i+1\right)+p_i\right).$$
Der erste Term zählt den Fall, dass man sofort mit einer letzten Primzahl \(q\ge p_j\) stoppt. Die Doppelsumme wählt die nächste Primzahl \(p_i\), legt \(p_i^e\) in den glatten Teil und lässt noch eine weitere Kopie von \(p_i\) als möglichen größten Primfaktor übrig. Das zusätzliche \(+p_i\) ist genau der Beitrag der Zahlen, deren größter Primfaktor \(p_i\) selbst ist.
Die gesuchte Summe ist daher
$$S(N)=F(N,1).$$
Die Rekursion benötigt ständig Werte von \(\Sigma_j(R)\). Deshalb muss die Summe der Primzahlen bis zu vielen verschiedenen Schranken sehr schnell verfügbar sein. Die Implementierung baut zwei gekoppelte Tabellenfamilien auf:
eine für direkte Argumente \(x\le \lfloor\sqrt N\rfloor\) und eine für Quotientenwerte \(\left\lfloor N/x\right\rfloor\).
Ausgangspunkt sind die naiven Größen
$$C(x)=x-1,\qquad T(x)=\sum_{k=2}^{x}k=\frac{x(x+1)}{2}-1,$$
von denen dann Primfaktor für Primfaktor die zusammengesetzten Beiträge entfernt werden. Nach dieser Vorverarbeitung liefern die Tabellen sowohl die Anzahl der Primzahlen bis \(x\) als auch deren Summe:
$$\pi(x)=\#\{q\le x:q\text{ prim}\},\qquad \Sigma(x)=\sum_{q\le x,\ q\text{ prim}} q.$$
Intervallsummen erhält man durch Subtraktion:
$$\Sigma_j(R)=\Sigma(R)-\Sigma(p_j-1).$$
Sei
$$n=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t}p^b,\qquad r_1<r_2<\cdots<r_t<p.$$
Dann folgt die Rekursion genau einem Pfad: erst \(r_1^{a_1}\), dann \(r_2^{a_2}\) und so weiter, immer zu größeren Primzahlen. Sind alle kleineren Primzahlen festgelegt, wird die letzte Primzahl \(p\) entweder über einen Primzahlintervall-Term gezählt, falls \(b=1\), oder über einen der direkten \(+p\)-Terme, falls \(b\ge 2\). Ein zweiter Pfad ist unmöglich, weil die Primreihenfolge strikt wachsend bleibt.
Die größten Primfaktoren sind
$$P(2)=2,\ P(3)=3,\ P(4)=2,\ P(5)=5,\ P(6)=3,\ P(7)=7,\ P(8)=2,\ P(9)=3,\ P(10)=5,$$
also
$$S(10)=2+3+2+5+3+7+2+3+5=32.$$
Die Rekursion sieht dieselbe Summe so: Der Primzahlintervall-Term an der Wurzel liefert
$$\Sigma(10)=2+3+5+7=17.$$
Dann liefert der Zweig für \(2\) den Beitrag \(2\) für \(4=2^2\), nochmals \(2\) für \(8=2^3\) sowie \(3+5\) für \(6=2\cdot 3\) und \(10=2\cdot 5\). Der Zweig für \(3\) liefert \(3\) für \(9=3^2\). Insgesamt also
$$17+2+2+(3+5)+3=32.$$
Die Implementierungen in C++, Python und Java verwenden dieselbe Struktur. Zuerst wird \(M=\lfloor\sqrt N\rfloor\) gesetzt und es werden zwei Tabellenfamilien aufgebaut, eine für direkte Argumente \(x\le M\) und eine für Quotientenwerte \(\lfloor N/x\rfloor\). Diese Tabellen starten mit der Anzahl der ganzen Zahlen ab \(2\) und mit den zugehörigen arithmetischen Summen.
Danach durchläuft die Implementierung alle Primzahlen bis \(M\). Jede neu entdeckte Primzahl aktualisiert beide Tabellenfamilien so, dass die durch diese Primzahl erzeugten zusammengesetzten Beiträge entfernt werden. Nach diesem Schritt stehen Primzahlanzahlen und Primzahlsummen für alle später benötigten Schranken bereit.
Die Rekursion verarbeitet dann Primzahlpotenzen in aufsteigender Primordnung. Für eine aktuelle Schranke \(R\) addiert sie zuerst die Summe aller zulässigen End-Primzahlen im Intervall \([p_j,R]\). Anschließend probiert sie jede nächste Primzahl \(p_i\) mit \(p_i^2\le R\), dividiert die Schranke wiederholt durch \(p_i\), ruft sich mit kleinerer Schranke und strengerer Untergrenze für die nächste Primzahl selbst auf und addiert für jede zusätzliche Kopie dieser Primzahl einmal direkt \(p_i\). Alle Summen werden modulo \(10^9\) geführt.
Die Python-Implementierung ist nur eine schlanke Brücke zur selben kompilierten Methode; mathematisch und algorithmisch verhalten sich daher alle drei Sprachversionen identisch.
Mit \(M=\lfloor\sqrt N\rfloor\) speichert die Vorverarbeitung \(O(M)\) Werte. Die Laufzeit folgt dem üblichen Min_25-artigen Muster: Sie ist sublinear in \(N\) und wächst für diese Art von Frontenaktualisierung grob wie \(O(N^{3/4}/\log N)\). Die Rekursion über Primzahlpotenzen ist dünn, weil sie nur solange fortgesetzt wird, wie \(p^2\le R\) gilt, und ist daher sehr viel kleiner als ein vollständiger Durchlauf bis \(N\). Der Speicherbedarf beträgt insgesamt \(O(\sqrt N)\).
\(n \ge 2\) için \(P(n)\), \(n\)'in en büyük asal çarpanı olsun. Hesaplanması istenen toplam
$$S(N)=\sum_{n=2}^{N} P(n)$$
ifadesidir; burada \(N=201820182018\) ve sonuç \(10^9\) modunda alınır. \(N\)'ye kadar doğrudan eleme yapmak gerçekçi olmadığı için çözüm, toplamı en büyük asal çarpana göre yeniden düzenler ve ortaya çıkan asal toplamlarını Min_25 benzeri bir asal-toplam dönüşümü ile seyrek bir asal kuvvet rekürsiyonu üzerinden hesaplar.
Her tam sayı toplama tam olarak bir asal sayı ekler: kendi en büyük asal çarpanını. Bu yüzden temel fikir, son asal çarpanı çarpanlaşmanın geri kalan kısmından ayırmaktır.
Eğer \(P(n)=p\) ise
$$n=p\,m$$
yazabiliriz ve \(m\)'nin tüm asal çarpanları en fazla \(p\) olur. Tersine, \(p\) asal olmak üzere \(p\,m\) biçimindeki ve \(m\)'nin tüm asal çarpanları \(\le p\) olan her sayı gerçekten en büyük asal çarpan olarak \(p\)'ye sahiptir.
Dolayısıyla
$$S(N)=\sum_{p\le N} p\,\Psi\left(\left\lfloor\frac{N}{p}\right\rfloor,p\right),$$
burada \(\Psi(x,y)\), asal çarpanlarının tamamı \(\le y\) olan ve \(x\)'i aşmayan pozitif tamsayıların sayısını gösterir. Problem böylece, ağırlıklı bir smooth sayı kofaktörü sayımına dönüşür.
Kofaktörü artan asal sırasıyla yazalım:
$$m=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t},\qquad r_1<r_2<\cdots<r_t\le p.$$
O zaman her \(n\le N\) sayısı
$$n=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t}p$$
şeklinde tek bir gösterime sahiptir; burada \(p=P(n)\)'dir. Rekürsiyonun çift sayım yapmamasının nedeni tam olarak bu tekliktir: asallar her zaman sıkı biçimde artan sırayla eklenir.
En büyük asal çarpan \(b\ge 1\) kuvvetiyle geliyorsa, kofaktör tarafında \(p^{b-1}\) bulunur; toplama eklenen son çarpan ise yalnızca bir adet \(p\)'dir.
\(p_1<p_2<\cdots\) asal dizisi olsun. Sabit bir \(j\) indeksi için
$$\Sigma_j(x)=\sum_{p_j\le q\le x,\ q\text{ asal}} q$$
tanımını yapalım. Şimdi daha küçük asal kuvvetlerden oluşan bir önek zaten seçilmiş olsun ve kalan bölüm sınırı \(R\) olsun. Sonraki izinli asal \(p_j\) iken bu durumdan gelen toplam katkıyı \(F(R,j)\) ile gösterelim. O zaman
$$F(R,j)=\Sigma_j(R)+\sum_{i\ge j,\ p_i^2\le R}\ \sum_{e\ge 1,\ p_i^{e+1}\le R}\left(F\left(\left\lfloor\frac{R}{p_i^e}\right\rfloor,i+1\right)+p_i\right).$$
İlk terim, hemen durup tek bir son asal \(q\ge p_j\) seçtiğimiz durumu sayar. Çift toplam ise sıradaki asal \(p_i\)'yi seçer, \(p_i^e\)'yi smooth kısma ekler ve bir kopya daha \(p_i\)'yi muhtemel en büyük asal olarak bırakır. Eklenen \(+p_i\), en büyük asal çarpanı doğrudan \(p_i\) olan sayıların katkısıdır.
Sonuç olarak aranan cevap
$$S(N)=F(N,1)$$
olur.
Rekürsiyon sürekli \(\Sigma_j(R)\) değerlerine ihtiyaç duyduğu için, çok sayıda farklı sınır için asal toplamlarını hızlı sorgulamak gerekir. Uygulama iki eşzamanlı tablo ailesi kurar:
biri doğrudan \(x\le \lfloor\sqrt N\rfloor\) değerleri için, diğeri de bölüm değerleri \(\left\lfloor N/x\right\rfloor\) için.
Bu tablolar başlangıçta şu ham büyüklükleri taşır:
$$C(x)=x-1,\qquad T(x)=\sum_{k=2}^{x}k=\frac{x(x+1)}{2}-1.$$
Daha sonra standart Min_25 mantığıyla, her asal için bileşik katkılar tablolardan temizlenir. Ön işleme tamamlandığında tablolar hem \(x\)'e kadar olan asal sayısını hem de asal toplamını verebilir:
$$\pi(x)=\#\{q\le x:q\text{ asal}\},\qquad \Sigma(x)=\sum_{q\le x,\ q\text{ asal}} q.$$
Aralık toplamı çıkarma ile elde edilir:
$$\Sigma_j(R)=\Sigma(R)-\Sigma(p_j-1).$$
Şimdi
$$n=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t}p^b,\qquad r_1<r_2<\cdots<r_t<p$$
olsun. Rekürsiyon tek bir yolu izler: önce \(r_1^{a_1}\), sonra \(r_2^{a_2}\) ve böyle devam eder; her adımda daha büyük bir asala geçer. Bütün küçük asallar yerleşince, son asal \(p\) ya \(b=1\) ise bir asal-aralık toplamından gelir ya da \(b\ge 2\) ise doğrudan \(+p\) terimlerinden biriyle sayılır. Asal sırası sıkı biçimde arttığı için aynı çarpanlaşmayı üreten ikinci bir yol yoktur.
En büyük asal çarpanlar şöyledir:
$$P(2)=2,\ P(3)=3,\ P(4)=2,\ P(5)=5,\ P(6)=3,\ P(7)=7,\ P(8)=2,\ P(9)=3,\ P(10)=5,$$
dolayısıyla
$$S(10)=2+3+2+5+3+7+2+3+5=32.$$
Rekürsiyon aynı sonucu şu şekilde görür. Kök düğümdeki asal-toplam terimi
$$\Sigma(10)=2+3+5+7=17$$
değerini verir. Sonra \(2\) dalı \(4=2^2\) için \(2\), \(8=2^3\) için bir \(2\) daha ve \(6=2\cdot 3\) ile \(10=2\cdot 5\) için \(3+5\) katkısını getirir. \(3\) dalı ise \(9=3^2\) için \(3\) katkısı verir. Toplam
$$17+2+2+(3+5)+3=32$$
olur.
C++, Python ve Java implementasyonları aynı algoritmik yapıyı kullanır. Önce \(M=\lfloor\sqrt N\rfloor\) alınır ve iki tablo ailesi hazırlanır: biri \(x\le M\) doğrudan argümanları için, diğeri de \(\lfloor N/x\rfloor\) bölüm argümanları için. Bu tablolar başlangıçta \(2\)'den başlayan sayı adetleri ve karşılık gelen aritmetik seri toplamlarıyla doldurulur.
Daha sonra uygulama \(M\)'ye kadar olan asalları tarar. Her yeni asal, bu iki tablo ailesini güncelleyerek o asaldan kaynaklanan bileşik katkıları çıkarır. Bu adım bittikten sonra rekürsiyonun ihtiyaç duyduğu bütün sınırlar için asal sayısı ve asal toplamı sorguları hazır hale gelir.
Rekürsif aşama, asal kuvvetleri artan asal sırasıyla dolaşır. Güncel sınır \(R\) için önce \([p_j,R]\) aralığındaki uygun son asalların toplamı eklenir. Ardından \(p_i^2\le R\) koşulunu sağlayan her sonraki asal \(p_i\) denenir; sınır art arda \(p_i\)'ye bölünür, daha sıkı bir asal alt sınırıyla küçülmüş duruma yeniden girilir ve bu asalın her ek kopyası için bir kez doğrudan \(p_i\) eklenir. Tüm işlemler \(10^9\) modunda yürütülür.
Python tarafı yalnızca aynı derlenmiş algoritmaya bağlanan ince bir köprüdür; dolayısıyla matematik ve yürütme stratejisi üç dilde de aynıdır.
\(M=\lfloor\sqrt N\rfloor\) için ön işleme \(O(M)\) adet değer saklar. Çalışma süresi tipik Min_25 profilini izler: \(N\)'de doğrusal değildir ve bu tür sınır-güncelleme yaklaşımı için yaklaşık \(O(N^{3/4}/\log N)\) büyür. Asal kuvvet rekürsiyonu yalnızca \(p^2\le R\) oldukça ilerlediği için seyrektir ve \(N\)'ye kadar tam taramadan çok daha küçüktür. Toplam bellek kullanımı \(O(\sqrt N)\) düzeyindedir.
Para \(n \ge 2\), sea \(P(n)\) el mayor factor primo de \(n\). Debemos calcular
$$S(N)=\sum_{n=2}^{N} P(n)$$
para \(N=201820182018\), módulo \(10^9\). Una criba directa hasta \(N\) es imposible en la práctica, así que la solución reordena la suma por mayor factor primo y evalúa las sumas de primos resultantes mediante una transformación tipo Min_25 junto con una recursión dispersa sobre potencias primas.
Cada entero aporta exactamente un primo a la suma: su mayor factor primo. Por eso conviene separar ese primo terminal del resto de la factorización.
Si \(P(n)=p\), entonces
$$n=p\,m,$$
donde todos los factores primos de \(m\) son \(\le p\). A la inversa, cualquier producto \(p\,m\) con \(p\) primo y con todos los factores primos de \(m\) acotados por \(p\) tiene como mayor factor primo precisamente a \(p\).
Así,
$$S(N)=\sum_{p\le N} p\,\Psi\left(\left\lfloor\frac{N}{p}\right\rfloor,p\right),$$
donde \(\Psi(x,y)\) cuenta los enteros positivos \(\le x\) cuyos factores primos son todos \(\le y\). El problema pasa a ser un conteo ponderado de cofactors smooth.
Escribimos el cofactor en orden creciente de primos:
$$m=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t},\qquad r_1<r_2<\cdots<r_t\le p.$$
Entonces cada \(n\le N\) posee la representación única
$$n=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t}p,$$
con \(p=P(n)\). Esa unicidad es la razón por la cual la recursión no duplica casos: los primos se introducen siempre en orden estrictamente creciente.
Si el mayor factor primo aparece con exponente \(b\ge 1\), entonces el cofactor contiene \(p^{b-1}\), mientras que el último \(p\) es el que realmente contribuye a la suma.
Sean \(p_1<p_2<\cdots\) los números primos. Para un índice fijo \(j\), definimos
$$\Sigma_j(x)=\sum_{p_j\le q\le x,\ q\text{ primo}} q.$$
Supongamos ahora que ya fijamos un prefijo formado por potencias de primos menores y que el límite restante del cociente es \(R\). Sea \(F(R,j)\) la contribución total desde ese estado cuando el siguiente primo permitido es \(p_j\). Entonces
$$F(R,j)=\Sigma_j(R)+\sum_{i\ge j,\ p_i^2\le R}\ \sum_{e\ge 1,\ p_i^{e+1}\le R}\left(F\left(\left\lfloor\frac{R}{p_i^e}\right\rfloor,i+1\right)+p_i\right).$$
El primer término cuenta el caso en que terminamos de inmediato con un primo final \(q\ge p_j\). La suma doble elige el siguiente primo \(p_i\), introduce \(p_i^e\) en la parte smooth y deja una copia adicional de \(p_i\) como posible mayor primo. El término extra \(+p_i\) es exactamente la contribución de los números cuyo mayor factor primo es el propio \(p_i\).
La respuesta final es
$$S(N)=F(N,1).$$
La recursión necesita continuamente valores de \(\Sigma_j(R)\), así que debe consultar sumas de primos hasta muchos límites distintos con gran rapidez. La implementación prepara dos familias sincronizadas de tablas:
una indexada directamente por \(x\le \lfloor\sqrt N\rfloor\), y otra por valores cociente \(\left\lfloor N/x\right\rfloor\).
Se parte de las cantidades ingenuas
$$C(x)=x-1,\qquad T(x)=\sum_{k=2}^{x}k=\frac{x(x+1)}{2}-1,$$
y luego se eliminan contribuciones compuestas primo por primo con la mecánica clásica de Min_25. Al terminar el preprocesamiento, las tablas devuelven tanto el número de primos hasta \(x\) como la suma de esos primos:
$$\pi(x)=\#\{q\le x:q\text{ primo}\},\qquad \Sigma(x)=\sum_{q\le x,\ q\text{ primo}} q.$$
Las sumas en intervalos se obtienen por resta:
$$\Sigma_j(R)=\Sigma(R)-\Sigma(p_j-1).$$
Tomemos
$$n=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t}p^b,\qquad r_1<r_2<\cdots<r_t<p.$$
La recursión sigue un único camino: elige \(r_1^{a_1}\), luego \(r_2^{a_2}\), y así sucesivamente, avanzando siempre hacia primos mayores. Cuando ya se fijaron todos los primos menores, el primo terminal \(p\) se cuenta mediante un término de suma de primos si \(b=1\), o mediante uno de los términos directos \(+p\) si \(b\ge 2\). Ningún otro camino puede producir la misma factorización porque el orden de los primos es estrictamente creciente.
Los mayores factores primos son
$$P(2)=2,\ P(3)=3,\ P(4)=2,\ P(5)=5,\ P(6)=3,\ P(7)=7,\ P(8)=2,\ P(9)=3,\ P(10)=5,$$
por lo que
$$S(10)=2+3+2+5+3+7+2+3+5=32.$$
La recursión ve el mismo total así. El término inicial de suma de primos aporta
$$\Sigma(10)=2+3+5+7=17.$$
Después, la rama de \(2\) añade \(2\) por \(4=2^2\), otro \(2\) por \(8=2^3\), y \(3+5\) por \(6=2\cdot 3\) y \(10=2\cdot 5\). La rama de \(3\) añade \(3\) por \(9=3^2\). En total,
$$17+2+2+(3+5)+3=32.$$
Las implementaciones en C++, Python y Java siguen la misma estructura algorítmica. Primero fijan \(M=\lfloor\sqrt N\rfloor\) y construyen dos familias de tablas, una para argumentos directos \(x\le M\) y otra para argumentos cociente \(\lfloor N/x\rfloor\). Esas tablas se inicializan con el conteo de enteros desde \(2\) y con las sumas de progresión aritmética correspondientes.
Después, la implementación recorre los primos hasta \(M\). Cada nuevo primo actualiza ambas familias de tablas para eliminar las contribuciones compuestas generadas por ese primo. Tras este preprocesamiento, ya se pueden consultar conteos de primos y sumas de primos para todos los límites que aparecerán más tarde en la recursión.
La fase recursiva explora potencias primas en orden creciente de primos. Para un límite actual \(R\), primero añade la suma de todos los primos terminales admisibles en el intervalo \([p_j,R]\). Luego prueba cada primo siguiente \(p_i\) con \(p_i^2\le R\), divide repetidamente el límite por \(p_i\), recurre sobre el límite reducido con una cota inferior más estricta para el próximo primo y añade una contribución directa \(p_i\) por cada copia adicional de ese primo. Todas las operaciones se reducen módulo \(10^9\).
La versión en Python es solo un puente ligero hacia el mismo algoritmo compilado, así que el método matemático y la estrategia de ejecución son idénticos en los tres lenguajes.
Sea \(M=\lfloor\sqrt N\rfloor\). El preprocesamiento almacena \(O(M)\) valores. Su tiempo sigue el perfil habitual de Min_25: es sublineal en \(N\) y crece aproximadamente como \(O(N^{3/4}/\log N)\) para este tipo de actualización por fronteras. La búsqueda recursiva sobre potencias primas es dispersa porque solo continúa mientras \(p^2\le R\), así que es mucho menor que un recorrido completo hasta \(N\). El uso total de memoria es \(O(\sqrt N)\).
对 \(n \ge 2\)，记 \(P(n)\) 为 \(n\) 的最大素因子。要求计算
$$S(N)=\sum_{n=2}^{N} P(n)$$
其中 \(N=201820182018\)，结果对 \(10^9\) 取模。若直接筛到 \(N\)，无论时间还是空间都不可接受，因此必须把求和方式改写成“按最大素因子分组”的形式，再配合 Min_25 风格的素数前缀和变换与稀疏的素数幂递归来完成计算。
每个整数只向总和贡献一个素数，也就是它自己的最大素因子。核心思想是把这个“最后出现的素数”从其余因子中剥离出来，然后对剩余部分做结构化计数。
如果 \(P(n)=p\)，那么一定可以写成
$$n=p\,m,$$
并且 \(m\) 的所有素因子都不超过 \(p\)。反过来，只要 \(p\) 是素数且 \(m\) 的所有素因子都满足 \(\le p\)，那么 \(p\,m\) 的最大素因子就一定是 \(p\)。
因此有
$$S(N)=\sum_{p\le N} p\,\Psi\left(\left\lfloor\frac{N}{p}\right\rfloor,p\right),$$
这里 \(\Psi(x,y)\) 表示不超过 \(x\) 的正整数中，所有素因子都不超过 \(y\) 的那些数的个数，也就是常说的 \(y\)-smooth 数计数。于是原题变成了一个带权的 smooth 余因子计数问题。
把余因子 \(m\) 按素数从小到大写成
$$m=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t},\qquad r_1<r_2<\cdots<r_t\le p.$$
于是每个 \(n\le N\) 都有唯一表示
$$n=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t}p,$$
其中 \(p=P(n)\)。这个唯一性非常关键，因为它说明递归只要始终按照素数递增的顺序加入新因子，就不会重复计数。
如果最大素因子在 \(n\) 中出现了 \(b\ge 1\) 次，那么余因子里会带有 \(p^{b-1}\)，而最后单独拿出来参与求和的那一份仍然只有一个 \(p\)。这正好对应实现中的“继续递归”和“直接加上当前素数”两种动作。
设素数序列为 \(p_1<p_2<\cdots\)。对固定的下标 \(j\)，定义
$$\Sigma_j(x)=\sum_{p_j\le q\le x,\ q\text{ 为素数}} q.$$
现在假设较小素数构成的前缀部分已经确定，剩余可用的商界为 \(R\)。令 \(F(R,j)\) 表示在“下一枚允许出现的素数是 \(p_j\)”这个条件下，当前状态所能贡献的总和。那么有
$$F(R,j)=\Sigma_j(R)+\sum_{i\ge j,\ p_i^2\le R}\ \sum_{e\ge 1,\ p_i^{e+1}\le R}\left(F\left(\left\lfloor\frac{R}{p_i^e}\right\rfloor,i+1\right)+p_i\right).$$
第一个项 \(\Sigma_j(R)\) 表示“前缀已经固定，此时直接选一个不小于 \(p_j\) 的末尾素数并结束”。双重求和表示“先选下一个素数 \(p_i\)，再把 \(p_i^e\) 塞进 smooth 部分”，这样还保留一份额外的 \(p_i\) 作为候选最大素因子。式子里的 \(+p_i\) 正是“最大素因子恰好就是 \(p_i\)”这一类数的贡献。
最终答案就是
$$S(N)=F(N,1).$$
上面的递归反复需要 \(\Sigma_j(R)\)，因此必须能够对很多不同的上界快速求“到该上界为止的素数和”。实现使用两组同步维护的表：
一组按直接参数 \(x\le \lfloor\sqrt N\rfloor\) 编号，另一组按商值 \(\left\lfloor N/x\right\rfloor\) 编号。
它们先从最朴素的量开始：
$$C(x)=x-1,\qquad T(x)=\sum_{k=2}^{x}k=\frac{x(x+1)}{2}-1,$$
也就是先把 \(2,3,\dots,x\) 全部看成候选。然后按照 Min_25 的标准思路，随着素数逐个加入，把由这些素数生成的合数贡献从表中剔除。处理结束后，表里保存的就是各种需要的素数统计信息，可以得到
$$\pi(x)=\#\{q\le x:q\text{ 为素数}\},\qquad \Sigma(x)=\sum_{q\le x,\ q\text{ 为素数}} q.$$
于是区间素数和可由差分给出：
$$\Sigma_j(R)=\Sigma(R)-\Sigma(p_j-1).$$
任取一个不超过 \(N\) 的整数，设其分解为
$$n=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t}p^b,\qquad r_1<r_2<\cdots<r_t<p.$$
递归只能沿着一条路径得到它：先选 \(r_1^{a_1}\)，再选 \(r_2^{a_2}\)，依此类推，每一步都把“下一枚可用素数”的下界向上推进。等所有较小素数都固定以后，如果 \(b=1\)，末尾的 \(p\) 会出现在某个区间素数和项里；如果 \(b\ge 2\)，则会在某个直接的 \(+p\) 项里被计入。由于素数顺序始终严格递增，不可能存在第二条不同路径生成同一个因子分解。
各个数的最大素因子为
$$P(2)=2,\ P(3)=3,\ P(4)=2,\ P(5)=5,\ P(6)=3,\ P(7)=7,\ P(8)=2,\ P(9)=3,\ P(10)=5,$$
所以
$$S(10)=2+3+2+5+3+7+2+3+5=32.$$
递归视角下也是同样的结果。根状态先给出
$$\Sigma(10)=2+3+5+7=17.$$
接着，素数 \(2\) 的分支贡献 \(4=2^2\) 的 \(2\)、\(8=2^3\) 的另一个 \(2\)，以及 \(6=2\cdot 3\)、\(10=2\cdot 5\) 对应的 \(3+5\)。素数 \(3\) 的分支再贡献 \(9=3^2\) 的 \(3\)。于是总和为
$$17+2+2+(3+5)+3=32.$$
C++、Python 和 Java 三个实现采用同一套算法结构。首先取 \(M=\lfloor\sqrt N\rfloor\)，建立两族表，一族面向直接参数 \(x\le M\)，另一族面向商参数 \(\lfloor N/x\rfloor\)。这些表最初存放的是从 \(2\) 开始的整数个数以及对应的等差级数和。
随后，实现依次扫描所有不超过 \(M\) 的素数。每发现一个新素数，就同时更新这两族表，把由该素数产生的合数贡献剔除掉。经过这一步后，递归阶段所需的所有上界都已经可以快速查询“素数个数”和“素数和”。
递归阶段按素数递增的顺序枚举素数幂。对于当前界 \(R\)，先加入区间 \([p_j,R]\) 内所有可作为末尾素数的总和；然后尝试每个满足 \(p_i^2\le R\) 的后继素数 \(p_i\)，不断把界除以 \(p_i\)，对更小的界和更严格的素数下界继续递归，并且对该素数的每一份额外拷贝都直接加上一份 \(p_i\)。所有加法都在模 \(10^9\) 下进行。
Python 版本本身只是对同一套已编译算法的轻量封装，所以三种语言在数学内容和执行策略上完全一致。
令 \(M=\lfloor\sqrt N\rfloor\)。预处理阶段存储 \(O(M)\) 个值。其时间复杂度符合典型的 Min_25 风格轮廓：相对于 \(N\) 是次线性的，对这种前沿更新写法而言通常可视为大约 \(O(N^{3/4}/\log N)\)。素数幂递归因为只有在 \(p^2\le R\) 时才会继续展开，所以非常稀疏，远小于直接从 \(2\) 扫到 \(N\) 的做法。总空间复杂度为 \(O(\sqrt N)\)。
Для \(n \ge 2\) обозначим через \(P(n)\) наибольший простой делитель числа \(n\). Требуется вычислить
$$S(N)=\sum_{n=2}^{N} P(n)$$
для \(N=201820182018\) по модулю \(10^9\). Прямое просеивание до \(N\) здесь нереалистично, поэтому решение перестраивает сумму по наибольшему простому делителю и затем вычисляет возникающие суммы простых чисел с помощью Min_25-подобного преобразования и разреженной рекурсии по простым степеням.
Каждое целое число добавляет в сумму ровно одно простое число, а именно свой наибольший простой делитель. Поэтому нужно отделить этот последний простой множитель от остальной части разложения.
Если \(P(n)=p\), то число \(n\) можно представить в виде
$$n=p\,m,$$
где все простые делители числа \(m\) не превосходят \(p\). Обратно, любое произведение \(p\,m\), где \(p\) простое, а все простые делители \(m\) удовлетворяют условию \(\le p\), имеет наибольший простой делитель ровно \(p\).
Следовательно,
$$S(N)=\sum_{p\le N} p\,\Psi\left(\left\lfloor\frac{N}{p}\right\rfloor,p\right),$$
где \(\Psi(x,y)\) обозначает количество положительных целых чисел \(\le x\), все простые делители которых не превосходят \(y\). Тем самым задача сводится к взвешенному подсчету smooth-кофакторов.
Запишем кофактор в возрастающем порядке простых:
$$m=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t},\qquad r_1<r_2<\cdots<r_t\le p.$$
Тогда каждое \(n\le N\) имеет единственное представление
$$n=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t}p,$$
где \(p=P(n)\). Именно эта единственность позволяет рекурсии обходить все разложения без повторов: простые числа добавляются строго по возрастанию.
Если наибольший простой делитель входит в \(n\) с показателем \(b\ge 1\), то в кофакторе присутствует \(p^{b-1}\), а последняя отдельная копия \(p\) и дает вклад в сумму.
Пусть \(p_1<p_2<\cdots\) - последовательность простых чисел. Для фиксированного индекса \(j\) определим
$$\Sigma_j(x)=\sum_{p_j\le q\le x,\ q\text{ простое}} q.$$
Предположим теперь, что некоторый префикс из степеней меньших простых уже выбран, а оставшаяся граница частного равна \(R\). Обозначим через \(F(R,j)\) суммарный вклад из такого состояния, если следующий допустимый простой равен \(p_j\). Тогда
$$F(R,j)=\Sigma_j(R)+\sum_{i\ge j,\ p_i^2\le R}\ \sum_{e\ge 1,\ p_i^{e+1}\le R}\left(F\left(\left\lfloor\frac{R}{p_i^e}\right\rfloor,i+1\right)+p_i\right).$$
Первый член соответствует случаю, когда мы сразу завершаем построение одним последним простым \(q\ge p_j\). Двойная сумма выбирает следующий простой \(p_i\), помещает \(p_i^e\) в smooth-часть и оставляет еще одну копию \(p_i\) как возможный наибольший простой делитель. Добавка \(+p_i\) и есть вклад чисел, у которых наибольший простой делитель равен самому \(p_i\).
Итак, окончательный ответ равен
$$S(N)=F(N,1).$$
Рекурсия постоянно нуждается в значениях \(\Sigma_j(R)\), поэтому сумма простых до многих разных границ должна вычисляться очень быстро. Реализация строит две синхронные семейства таблиц:
одно индексируется напрямую значениями \(x\le \lfloor\sqrt N\rfloor\), а другое - частными \(\left\lfloor N/x\right\rfloor\).
Изначально используются наивные величины
$$C(x)=x-1,\qquad T(x)=\sum_{k=2}^{x}k=\frac{x(x+1)}{2}-1,$$
после чего составные вклады последовательно вычитаются по простым, как в стандартной схеме Min_25. После этой подготовки таблицы умеют возвращать и количество простых до \(x\), и их сумму:
$$\pi(x)=\#\{q\le x:q\text{ простое}\},\qquad \Sigma(x)=\sum_{q\le x,\ q\text{ простое}} q.$$
Сумма простых на интервале получается вычитанием:
$$\Sigma_j(R)=\Sigma(R)-\Sigma(p_j-1).$$
Пусть
$$n=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t}p^b,\qquad r_1<r_2<\cdots<r_t<p.$$
Рекурсия проходит ровно по одному пути: сначала выбирает \(r_1^{a_1}\), затем \(r_2^{a_2}\) и так далее, каждый раз переходя только к большим простым. После того как все меньшие простые зафиксированы, последний простой \(p\) учитывается либо интервалом сумм простых, если \(b=1\), либо одним из прямых членов \(+p\), если \(b\ge 2\). Второго пути для той же факторизации не существует, потому что порядок простых строго возрастает.
Наибольшие простые делители равны
$$P(2)=2,\ P(3)=3,\ P(4)=2,\ P(5)=5,\ P(6)=3,\ P(7)=7,\ P(8)=2,\ P(9)=3,\ P(10)=5,$$
поэтому
$$S(10)=2+3+2+5+3+7+2+3+5=32.$$
Рекурсия видит ту же сумму так. Корневой член суммы простых дает
$$\Sigma(10)=2+3+5+7=17.$$
Далее ветвь для \(2\) добавляет \(2\) за \(4=2^2\), еще \(2\) за \(8=2^3\), а также \(3+5\) за \(6=2\cdot 3\) и \(10=2\cdot 5\). Ветвь для \(3\) добавляет \(3\) за \(9=3^2\). Итого
$$17+2+2+(3+5)+3=32.$$
Реализации на C++, Python и Java следуют одной и той же структуре. Сначала выбирается \(M=\lfloor\sqrt N\rfloor\), после чего строятся две семейства таблиц: для прямых аргументов \(x\le M\) и для аргументов вида \(\lfloor N/x\rfloor\). В начале в них лежат количества чисел, начиная с \(2\), и соответствующие суммы арифметической прогрессии.
Затем реализация проходит по всем простым до \(M\). Каждый вновь найденный простой обновляет обе семейства таблиц, удаляя составные вклады, порождаемые этим простым. После такого препроцессинга можно быстро получать количество простых и сумму простых для всех границ, которые потом встречаются в рекурсии.
На рекурсивной стадии перебираются простые степени в порядке возрастания простых. Для текущей границы \(R\) сначала добавляется сумма всех допустимых конечных простых на интервале \([p_j,R]\). Затем перебираются все следующие простые \(p_i\), удовлетворяющие \(p_i^2\le R\); граница многократно делится на \(p_i\), выполняется рекурсивный вызов с меньшей границей и более строгим нижним порогом для следующего простого, и для каждой дополнительной копии \(p_i\) сразу прибавляется одно \(p_i\). Все действия ведутся по модулю \(10^9\).
Версия на Python является лишь тонкой оберткой над тем же скомпилированным алгоритмом, поэтому математический метод и стратегия выполнения полностью совпадают во всех трех языках.
Пусть \(M=\lfloor\sqrt N\rfloor\). Предобработка хранит \(O(M)\) значений. Ее время соответствует обычному профилю Min_25-подобных методов: оно сублинейно по \(N\) и для такой схемы обновления фронтов обычно оценивается примерно как \(O(N^{3/4}/\log N)\). Рекурсивный перебор простых степеней разрежен, поскольку продолжается только пока \(p^2\le R\), и потому намного меньше полного прохода по всем числам до \(N\). Общая память равна \(O(\sqrt N)\).
لـ \(n \ge 2\)، نرمز بـ \(P(n)\) إلى أكبر عامل أولي للعدد \(n\). المطلوب هو حساب
$$S(N)=\sum_{n=2}^{N} P(n)$$
عند \(N=201820182018\) مع الأخذ بترديد \(10^9\). تنفيذ غربال مباشر حتى \(N\) غير عملي إطلاقًا، لذلك يعيد الحل تنظيم المجموع بحسب أكبر عامل أولي، ثم يحسب مجاميع الأعداد الأولية الناتجة باستخدام تحويل من نمط Min_25 مع عودية متناثرة على قوى الأعداد الأولية.
كل عدد صحيح يضيف إلى المجموع عددًا أوليًا واحدًا فقط، وهو أكبر عامل أولي له. لذلك فالفكرة الأساسية هي فصل هذا العامل الأولي الأخير عن بقية التحليل إلى عوامل.
إذا كان \(P(n)=p\)، فيمكن كتابة
$$n=p\,m,$$
بحيث تكون جميع العوامل الأولية في \(m\) أصغر من أو تساوي \(p\). وبالعكس، فإن أي عدد على الصورة \(p\,m\)، حيث \(p\) أولي وجميع العوامل الأولية في \(m\) لا تتجاوز \(p\)، يكون أكبر عامل أولي له هو \(p\) فعلًا.
إذن نحصل على
$$S(N)=\sum_{p\le N} p\,\Psi\left(\left\lfloor\frac{N}{p}\right\rfloor,p\right),$$
حيث إن \(\Psi(x,y)\) تمثل عدد الأعداد الصحيحة الموجبة التي لا تتجاوز \(x\) وجميع عواملها الأولية لا تتجاوز \(y\). وهكذا تتحول المسألة إلى عد مرجح لعوامل مرافقة من نوع smooth.
لنكتب العامل المرافق بترتيب أولي تصاعدي:
$$m=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t},\qquad r_1<r_2<\cdots<r_t\le p.$$
عندئذ يملك كل عدد \(n\le N\) تمثيلًا وحيدًا من الشكل
$$n=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t}p,$$
حيث \(p=P(n)\). هذه الوحدانية هي السبب في أن العودية لا تكرر العد: فالأوليات تدخل دائمًا بترتيب تصاعدي صارم.
إذا ظهر أكبر عامل أولي بأس \(b\ge 1\)، فإن الجزء المرافق يحتوي على \(p^{b-1}\)، بينما النسخة الأخيرة المنفصلة من \(p\) هي التي تساهم في المجموع.
لتكن \(p_1<p_2<\cdots\) هي الأعداد الأولية. ولأجل فهرس ثابت \(j\)، نعرف
$$\Sigma_j(x)=\sum_{p_j\le q\le x,\ q\text{ prime}} q.$$
افترض الآن أننا ثبتنا بالفعل بادئة مكونة من قوى أولية أصغر، وأن الحد المتبقي للقسمة هو \(R\). لنعرف \(F(R,j)\) بأنه مجموع المساهمات الناتجة من هذه الحالة عندما يكون أول أولي مسموح تالٍ هو \(p_j\). عندئذ
$$F(R,j)=\Sigma_j(R)+\sum_{i\ge j,\ p_i^2\le R}\ \sum_{e\ge 1,\ p_i^{e+1}\le R}\left(F\left(\left\lfloor\frac{R}{p_i^e}\right\rfloor,i+1\right)+p_i\right).$$
الحد الأول يحسب الحالة التي نتوقف فيها مباشرة مع أولي نهائي واحد \(q\ge p_j\). أما الجمع المزدوج فيختار الأولي التالي \(p_i\)، ويضع \(p_i^e\) داخل الجزء smooth، ويترك نسخة إضافية من \(p_i\) بوصفها المرشح لأكبر عامل أولي. أما \(+p_i\) فهي بالضبط مساهمة الأعداد التي يكون أكبر عامل أولي فيها هو \(p_i\) نفسه.
وعليه فإن الجواب النهائي هو
$$S(N)=F(N,1).$$
تحتاج العودية مرارًا إلى قيم \(\Sigma_j(R)\)، ولذلك يجب أن تكون مجاميع الأوليات حتى حدود كثيرة مختلفة متاحة بسرعة عالية. يبني التنفيذ عائلتين متزامنتين من الجداول:
إحداهما مفهرسة مباشرة بالقيم \(x\le \lfloor\sqrt N\rfloor\)، والأخرى مفهرسة بقيم خارج القسمة \(\left\lfloor N/x\right\rfloor\).
وتبدأ هذه الجداول من الكميات الأولية الساذجة
$$C(x)=x-1,\qquad T(x)=\sum_{k=2}^{x}k=\frac{x(x+1)}{2}-1,$$
ثم تُزال المساهمات المركبة أوليًا بعد أولي وفق الفكرة القياسية في Min_25. بعد اكتمال التمهيد تستطيع الجداول إرجاع كل من عدد الأوليات حتى \(x\) ومجموعها:
$$\pi(x)=\#\{q\le x:q\text{ prime}\},\qquad \Sigma(x)=\sum_{q\le x,\ q\text{ prime}} q.$$
أما مجموع الأوليات على مجال فيحصل عليه بالطرح:
$$\Sigma_j(R)=\Sigma(R)-\Sigma(p_j-1).$$
خذ أي عدد
$$n=r_1^{a_1}r_2^{a_2}\cdots r_t^{a_t}p^b,\qquad r_1<r_2<\cdots<r_t<p.$$
تسير العودية في مسار وحيد فقط: تختار أولًا \(r_1^{a_1}\)، ثم \(r_2^{a_2}\)، وهكذا مع الانتقال دائمًا إلى أوليات أكبر. وبعد تثبيت جميع الأوليات الأصغر، يُحتسب الأولي النهائي \(p\) إما من حد مجموع أوليات على مجال عندما يكون \(b=1\)، أو من أحد حدود \(+p\) المباشرة عندما يكون \(b\ge 2\). لا يوجد مسار آخر ينتج التحليل نفسه لأن ترتيب الأوليات يبقى تصاعديًا بشكل صارم.
أكبر العوامل الأولية هي
$$P(2)=2,\ P(3)=3,\ P(4)=2,\ P(5)=5,\ P(6)=3,\ P(7)=7,\ P(8)=2,\ P(9)=3,\ P(10)=5,$$
ومن ثم
$$S(10)=2+3+2+5+3+7+2+3+5=32.$$
وترى العودية المجموع نفسه بهذه الصورة. حد مجموع الأوليات في الجذر يعطي
$$\Sigma(10)=2+3+5+7=17.$$
ثم يضيف فرع \(2\) القيمة \(2\) للعدد \(4=2^2\)، وقيمة \(2\) أخرى للعدد \(8=2^3\)، ويضيف \(3+5\) للعددين \(6=2\cdot 3\) و\(10=2\cdot 5\). ويضيف فرع \(3\) القيمة \(3\) للعدد \(9=3^2\). لذلك يكون المجموع
$$17+2+2+(3+5)+3=32.$$
تتبع تطبيقات C++ وPython وJava البنية الخوارزمية نفسها. في البداية تحدد \(M=\lfloor\sqrt N\rfloor\)، ثم تبني عائلتين من الجداول: واحدة للوسائط المباشرة \(x\le M\)، وأخرى لوسائط القسمة \(\lfloor N/x\rfloor\). وتبدأ هذه الجداول بعدد الأعداد الصحيحة بدءًا من \(2\) وبمجاميع المتتاليات الحسابية الموافقة.
بعد ذلك يمر التنفيذ على جميع الأوليات حتى \(M\). وكل أولي جديد يحدث العائلتين معًا بحيث تُحذف المساهمات المركبة الناتجة عن ذلك الأولي. وبعد اكتمال هذه المرحلة تصبح استعلامات عدد الأوليات ومجموع الأوليات متاحة لكل حد ستحتاجه العودية لاحقًا.
في المرحلة العودية، تُستكشف قوى الأوليات بترتيب أولي متزايد. من أجل حد حالي \(R\)، يضيف التنفيذ أولًا مجموع جميع الأوليات النهائية المسموح بها في المجال \([p_j,R]\). ثم يجرب كل أولي تالٍ \(p_i\) يحقق \(p_i^2\le R\)، ويقسم الحد مرارًا على \(p_i\)، ويستدعي الحالة الأصغر بحد أدنى أعلى للأولي التالي، ويضيف مساهمة مباشرة مقدارها \(p_i\) لكل نسخة إضافية من هذا الأولي. وتُجرى جميع العمليات بترديد \(10^9\).
نسخة Python ليست سوى جسر خفيف إلى الخوارزمية المترجمة نفسها، ولذلك فإن المنهج الرياضي واستراتيجية التنفيذ متماثلان في اللغات الثلاث.
إذا وضعنا \(M=\lfloor\sqrt N\rfloor\)، فإن مرحلة التمهيد تخزن \(O(M)\) قيمة. ويأخذ الزمن النمط المعتاد لطرق Min_25: فهو دون خطي بالنسبة إلى \(N\)، وينمو تقريبًا مثل \(O(N^{3/4}/\log N)\) لهذا النوع من تحديث الحدود. أما البحث العودي في قوى الأوليات فهو متناثر لأنه لا يتابع إلا عندما يتحقق الشرط \(p^2\le R\)، ولذلك فهو أصغر بكثير من مسح كامل حتى \(N\). والاستهلاك الكلي للذاكرة هو \(O(\sqrt N)\).