For this problem we set \(L=64{,}000{,}000\) and study the divisor-square-sum function
$$\sigma_2(n)=\sum_{d\mid n} d^2.$$
The goal is to compute
$$\sum_{\substack{1 \le n \lt L \\ \exists r\in \mathbb{Z}_{\ge 0}:\ \sigma_2(n)=r^2}} n.$$
The condition is arithmetical rather than combinatorial: we are not counting divisors, but adding their squares and then testing whether the resulting integer is itself a square. Since \(\sigma_2(1)=1\), the sum already includes \(n=1\); the real work is to find all larger \(n\) below the limit that survive the same test.
The common structure behind all three implementations is the prime-factor description of \(\sigma_2\). Once that formula is available, the problem becomes: generate or evaluate integers \(n\lt L\), compute \(\sigma_2(n)\) exactly, and keep only those for which the value is a square.
If \(a\) and \(b\) are coprime, then every divisor of \(ab\) can be written uniquely as \(d_1d_2\) with \(d_1\mid a\) and \(d_2\mid b\). Therefore
$$\sigma_2(ab)=\sum_{d\mid ab} d^2=\sum_{d_1\mid a}\sum_{d_2\mid b}(d_1d_2)^2=\left(\sum_{d_1\mid a} d_1^2\right)\left(\sum_{d_2\mid b} d_2^2\right)=\sigma_2(a)\sigma_2(b).$$
So \(\sigma_2\) is multiplicative. If
$$n=\prod_{i=1}^r p_i^{e_i},$$
then
$$\sigma_2(n)=\prod_{i=1}^r \sigma_2\!\left(p_i^{e_i}\right)=\prod_{i=1}^r \left(1+p_i^2+p_i^4+\cdots+p_i^{2e_i}\right).$$
This is the key formula used everywhere in the page: the square test for \(\sigma_2(n)\) is controlled completely by the prime-power factors of \(n\).
For a fixed prime \(p\), define
$$G_p(e)=1+p^2+p^4+\cdots+p^{2e}=\frac{p^{2(e+1)}-1}{p^2-1}.$$
Then the factorization above becomes
$$\sigma_2(n)=\prod_i G_{p_i}(e_i).$$
The closed form is mathematically convenient, but the implementations use an even simpler iterative identity:
$$G_p(0)=1,\qquad G_p(e+1)=p^2\,G_p(e)+1.$$
Indeed, multiplying \(1+p^2+\cdots+p^{2e}\) by \(p^2\) and then adding 1 produces \(1+p^2+\cdots+p^{2e}+p^{2e+2}\). This recurrence is exactly what lets the recursive search extend an exponent from \(e\) to \(e+1\) without recomputing a geometric series from scratch.
A concrete example shows why the multiplicative viewpoint is so effective. Since
$$42=2\cdot 3\cdot 7,$$
we get
$$\sigma_2(42)=\left(1+2^2\right)\left(1+3^2\right)\left(1+7^2\right)=5\cdot 10\cdot 50=2500=50^2.$$
So \(42\) is one of the integers that must be included in the final sum. The important point is that no divisor list had to be generated explicitly: prime factorization plus multiplicativity already gives the answer.
The C++ and Python implementations maintain a state of the form
$$n_0=\prod_{i=1}^k p_i^{e_i},\qquad s_0=\sigma_2(n_0),$$
with strictly increasing primes \(p_1<p_2<\cdots<p_k\). To extend the state, they choose a larger prime \(q\) and an exponent \(f\ge 1\), then form
$$n=n_0q^f,\qquad \sigma_2(n)=s_0\,G_q(f).$$
Because each new prime is introduced only after all smaller chosen primes are fixed, every integer below the limit is generated exactly once, namely in the order dictated by its unique prime factorization. The pruning condition \(n<L\) is monotone, so as soon as a prime power pushes \(n\) past the limit, all larger exponents for that prime can be discarded immediately.
The Java implementation uses the same mathematics in a different way. Write
$$n=mp^e,\qquad p\nmid m,$$
where \(p\) is the smallest prime dividing \(n\). Then
$$\sigma_2(n)=\sigma_2(m)\,G_p(e).$$
This gives a recurrence from a smaller integer \(m\) to the current integer \(n\). Once the smallest prime factor of every number is known, the algorithm can strip off the full \(p\)-power, build the geometric factor \(G_p(e)\), and recover \(\sigma_2(n)\) from a previously computed value. In other words, one family of implementations explores valid factorizations directly, while the other fills the entire table of \(\sigma_2(n)\) values from \(1\) up to \(L-1\).
These implementations first build the prime list up to \(L-1\). They then recurse over increasing primes, carrying two exact integers: the current candidate \(n_0\) and the already-known value \(\sigma_2(n_0)\). For each newly chosen prime \(p\), they try exponents \(1,2,3,\dots\) as long as the product stays below the limit, update the prime-power factor with the recurrence \(G_p(e+1)=p^2G_p(e)+1\), and multiply it into the current \(\sigma_2\) value.
Whenever the new value of \(\sigma_2(n)\) is a perfect square, the corresponding \(n\) is added to the running total. Since the recursion visits each admissible factorization once, no deduplication structure is needed. The C++ version also splits the outermost prime choices across several worker threads so that separate branches of the factorization tree can be processed independently.
The Java implementation takes an array-based route. It first computes the smallest prime factor of every integer below the limit. Then it processes \(n=2,3,\dots,L-1\) in order. If \(n\) is prime, the formula is immediate:
$$\sigma_2(n)=1+n^2.$$
If \(n\) is composite, the implementation extracts the full power \(p^e\) of its smallest prime factor, forms \(G_p(e)=1+p^2+\cdots+p^{2e}\), and multiplies that by the previously known value of \(\sigma_2(m)\) for the cofactor \(m\). After the array is filled, one final pass tests each \(\sigma_2(n)\) for being a square and accumulates the valid \(n\).
The square test must be exact. Python uses the integer square-root routine directly. The C++ and Java implementations begin with a floating-point square-root estimate, but then adjust the candidate root upward or downward until \(r^2\le \sigma_2(n) < (r+1)^2\). This correction step avoids false positives from rounding and guarantees that the acceptance test really means
$$\sigma_2(n)=r^2\quad\text{for some integer }r.$$
The three implementations share the same number theory but not the same cost profile. The recursive C++ and Python approach is output-sensitive: its running time is proportional to the number of prime-exponent states visited under the bound \(n<L\). The recursion depth is the number of distinct prime factors currently chosen, so it is small in practice and at worst \(O(\log L)\). Memory is dominated by the prime list plus the recursion stack.
The Java approach uses more memory but has a very regular control flow. It stores arrays indexed by all integers below \(L\), so its space usage is \(O(L)\). Time is dominated by the smallest-prime-factor sieve, the pass that reconstructs each \(\sigma_2(n)\), and the final square test sweep. For this fixed Project Euler limit, both strategies are practical: one saves memory by exploring only factorization states, while the other spends memory to make the arithmetic on each \(n\) very direct.
In dieser Aufgabe ist \(L=64{,}000{,}000\) fest vorgegeben, und betrachtet wird die Quadratsummen-Teilerfunktion
$$\sigma_2(n)=\sum_{d\mid n} d^2.$$
Gesucht ist also
$$\sum_{\substack{1 \le n \lt L \\ \exists r\in \mathbb{Z}_{\ge 0}:\ \sigma_2(n)=r^2}} n.$$
Die Schwierigkeit liegt nicht im Auflisten der Teiler selbst, sondern darin, die Summe ihrer Quadrate effizient aus der Primfaktorzerlegung von \(n\) zu gewinnen. Da \(\sigma_2(1)=1\), gehört \(n=1\) sofort zur Summe; entscheidend ist, welche weiteren Zahlen unterhalb der Grenze dieselbe Eigenschaft besitzen.
Alle drei Implementierungen beruhen auf derselben zahlentheoretischen Struktur. Sobald man \(\sigma_2(n)\) über Primfaktoren beschreibt, kann man das Problem entweder als rekursive Erzeugung zulässiger Faktorisierungen oder als tabellarische Auswertung aller Zahlen bis \(L-1\) formulieren.
Sind \(a\) und \(b\) teilerfremd, dann besitzt jeder Teiler von \(ab\) eindeutig die Form \(d_1d_2\) mit \(d_1\mid a\) und \(d_2\mid b\). Daher gilt
$$\sigma_2(ab)=\sum_{d\mid ab} d^2=\sum_{d_1\mid a}\sum_{d_2\mid b}(d_1d_2)^2=\sigma_2(a)\sigma_2(b).$$
Damit ist \(\sigma_2\) multiplikativ. Für
$$n=\prod_{i=1}^r p_i^{e_i}$$
folgt also
$$\sigma_2(n)=\prod_{i=1}^r\left(1+p_i^2+p_i^4+\cdots+p_i^{2e_i}\right).$$
Genau diese Zerlegung macht das Problem beherrschbar: Die Quadratbedingung für \(\sigma_2(n)\) hängt vollständig von den Beiträgen der einzelnen Primpotenzen ab.
Für eine feste Primzahl \(p\) definieren wir
$$G_p(e)=1+p^2+p^4+\cdots+p^{2e}=\frac{p^{2(e+1)}-1}{p^2-1}.$$
Dann schreibt sich
$$\sigma_2(n)=\prod_i G_{p_i}(e_i).$$
Wichtiger als die geschlossene Formel ist in den Programmen die Iteration
$$G_p(0)=1,\qquad G_p(e+1)=p^2\,G_p(e)+1.$$
Damit kann man den Beitrag einer Primzahlpotenz Schritt für Schritt erweitern, ohne die ganze geometrische Reihe jedes Mal neu zu berechnen. Genau diese Rekurrenz wird in der rekursiven Suche und in der Zerlegung nach dem kleinsten Primfaktor ausgenutzt.
Für
$$42=2\cdot 3\cdot 7$$
erhält man unmittelbar
$$\sigma_2(42)=\left(1+2^2\right)\left(1+3^2\right)\left(1+7^2\right)=5\cdot 10\cdot 50=2500=50^2.$$
Also wird \(42\) zur Endsumme addiert. Das Beispiel zeigt den eigentlichen Vorteil des Ansatzes: Man braucht die Teiler von 42 gar nicht einzeln zu erzeugen, weil die Primfaktorzerlegung die Quadratsumme bereits vollständig bestimmt.
Die C++- und Python-Implementierungen verwalten Zustände der Form
$$n_0=\prod_{i=1}^k p_i^{e_i},\qquad s_0=\sigma_2(n_0),$$
wobei die Primzahlen streng aufsteigend sind. Ein Zustand wird durch eine größere Primzahl \(q\) und einen Exponenten \(f\ge 1\) erweitert:
$$n=n_0q^f,\qquad \sigma_2(n)=s_0\,G_q(f).$$
Weil neue Primzahlen nur in aufsteigender Reihenfolge eingeführt werden, entsteht jede Zahl \(n<L\) genau einmal, nämlich gemäß ihrer eindeutigen Primfaktorzerlegung. Außerdem ist die Schranke \(n<L\) monoton: Sobald eine Primzahlpotenz die Grenze überschreitet, können alle größeren Exponenten desselben Primfaktors sofort verworfen werden.
Die Java-Implementierung verwendet dieselbe Formel, aber in anderer Form. Schreibe
$$n=mp^e,\qquad p\nmid m,$$
wobei \(p\) der kleinste Primfaktor von \(n\) ist. Dann gilt
$$\sigma_2(n)=\sigma_2(m)\,G_p(e).$$
Hat man also den kleinsten Primfaktor jeder Zahl vorab bestimmt, dann lässt sich \(n\) in einen kleineren Kofaktor \(m\) und eine volle \(p\)-Potenz zerlegen. Daraus wird der geometrische Faktor \(G_p(e)\) aufgebaut, und \(\sigma_2(n)\) folgt aus einem bereits bekannten kleineren Wert. So erkundet die eine Implementationsfamilie direkte Faktorisierungen, während die andere eine komplette Tabelle der Werte \(\sigma_2(1),\dots,\sigma_2(L-1)\) füllt.
Diese Implementierungen erzeugen zunächst alle Primzahlen bis \(L-1\). Danach laufen sie rekursiv über wachsende Primzahlen und tragen dabei zwei exakte Ganzzahlen mit: den aktuellen Kandidaten \(n_0\) und den bereits bekannten Wert \(\sigma_2(n_0)\). Für jede neu gewählte Primzahl \(p\) werden die Exponenten \(1,2,3,\dots\) ausprobiert, solange das Produkt unterhalb der Grenze bleibt; gleichzeitig wird der Primzahlpotenzfaktor über \(G_p(e+1)=p^2G_p(e)+1\) fortgeschrieben.
Immer wenn der neue Wert \(\sigma_2(n)\) ein perfektes Quadrat ist, wird das zugehörige \(n\) zur Summe addiert. Weil jede zulässige Faktorisierung nur einmal besucht wird, braucht man keine Menge zur Dublettenkontrolle. Die C++-Version verteilt zusätzlich die äußersten Startzweige über mehrere Threads, damit voneinander unabhängige Teilbäume parallel abgearbeitet werden können.
Die Java-Implementierung wählt einen arraybasierten Weg. Zuerst wird für jede Zahl unterhalb der Grenze ihr kleinster Primfaktor berechnet. Danach werden die Zahlen \(n=2,3,\dots,L-1\) der Reihe nach verarbeitet. Ist \(n\) prim, dann gilt sofort
$$\sigma_2(n)=1+n^2.$$
Ist \(n\) zusammengesetzt, so wird die volle Potenz \(p^e\) des kleinsten Primfaktors abgespalten, daraus \(G_p(e)=1+p^2+\cdots+p^{2e}\) gebildet und anschließend mit dem schon bekannten Wert \(\sigma_2(m)\) des Restfaktors multipliziert. Nach dem Füllen des Arrays genügt ein letzter Durchlauf, der jeden Wert auf Perfektes-Quadrat-Eigenschaft prüft und die passenden \(n\) aufsummiert.
Der Test auf Quadratzahlen muss exakt sein. Python benutzt direkt eine ganzzahlige Quadratwurzel. C++ und Java beginnen mit einer Fließkomma-Näherung für \(\sqrt{\sigma_2(n)}\), korrigieren den Kandidaten aber anschließend nach oben oder unten, bis sicher
$$r^2\le \sigma_2(n) < (r+1)^2$$
gilt. Erst dann wird geprüft, ob wirklich \(r^2=\sigma_2(n)\) ist. Dadurch werden Rundungsfehler zuverlässig ausgeschlossen.
Obwohl alle Implementierungen dieselbe Mathematik verwenden, unterscheiden sich ihre Kostenprofile. Der rekursive Ansatz in C++ und Python ist ausgabesensitiv: Die Laufzeit ist proportional zur Anzahl der tatsächlich besuchten Primzahl-Exponenten-Zustände unter der Schranke \(n<L\). Die Rekursionstiefe entspricht der Zahl verschiedener gewählter Primfaktoren und ist daher klein; im Allgemeinen liegt sie höchstens bei \(O(\log L)\). Der Speicherbedarf wird von Primzahlliste und Rekursionsstack bestimmt.
Der Java-Ansatz verwendet mehr Speicher, arbeitet dafür sehr gleichmäßig. Er hält Arrays für alle Zahlen unterhalb von \(L\), also ist der Platzbedarf \(O(L)\). Die Laufzeit wird vom Sieb für kleinste Primfaktoren, vom Aufbau aller \(\sigma_2(n)\)-Werte und vom abschließenden Durchlauf für den Quadrat-Test dominiert. Für die feste Grenze des Problems sind beide Strategien praktikabel: die eine spart Speicher durch direkte Faktorisierungssuche, die andere investiert Speicher in eine sehr direkte Auswertung jeder einzelnen Zahl.
Bu soruda sınır \(L=64{,}000{,}000\) olarak verilir ve şu fonksiyon incelenir:
$$\sigma_2(n)=\sum_{d\mid n} d^2.$$
Aranan toplam şudur:
$$\sum_{\substack{1 \le n \lt L \\ \exists r\in \mathbb{Z}_{\ge 0}:\ \sigma_2(n)=r^2}} n.$$
Zorluk, bölenleri tek tek üretmekte değil; bölen kareleri toplamını asal çarpan yapısından hızlı biçimde çıkarmaktadır. \(\sigma_2(1)=1\) olduğundan \(n=1\) zaten sonuca dahildir. Esas mesele, sınırın altında kalan hangi daha büyük sayıların aynı testi geçtiğini bulmaktır.
Üç uygulamanın ortak zemini aynıdır: \(\sigma_2\) fonksiyonunu asal üsler üzerinden yazmak. Bu formül elde edilince problem ya uygun çarpanlaşmaları özyinelemeli olarak gezmeye ya da \(1\)'den \(L-1\)'e kadar bütün \(\sigma_2(n)\) değerlerini tablo halinde üretmeye indirgenir.
\(a\) ve \(b\) aralarında asal ise, \(ab\)'nin her böleni tekil olarak \(d_1d_2\) biçiminde yazılır; burada \(d_1\mid a\) ve \(d_2\mid b\). Bu yüzden
$$\sigma_2(ab)=\sum_{d\mid ab} d^2=\sum_{d_1\mid a}\sum_{d_2\mid b}(d_1d_2)^2=\sigma_2(a)\sigma_2(b).$$
Yani \(\sigma_2\) çarpımsal bir fonksiyondur. Eğer
$$n=\prod_{i=1}^r p_i^{e_i}$$
ise
$$\sigma_2(n)=\prod_{i=1}^r\left(1+p_i^2+p_i^4+\cdots+p_i^{2e_i}\right).$$
Bütün çözüm burada düğümleniyor: \(\sigma_2(n)\)'nin tam kare olup olmaması, \(n\)'nin asal üs katkılarıyla tamamen belirleniyor.
Sabit bir asal \(p\) için
$$G_p(e)=1+p^2+p^4+\cdots+p^{2e}=\frac{p^{2(e+1)}-1}{p^2-1}$$
tanımını yapalım. O zaman
$$\sigma_2(n)=\prod_i G_{p_i}(e_i)$$
olur. Matematiksel olarak kapalı form kullanışlıdır, fakat uygulamaların asıl kullandığı ifade şu artımlı bağıntıdır:
$$G_p(0)=1,\qquad G_p(e+1)=p^2\,G_p(e)+1.$$
Gerçekten de \(1+p^2+\cdots+p^{2e}\) ifadesini \(p^2\) ile çarpıp 1 eklerseniz bir sonraki üs seviyesinin toplamı elde edilir. Böylece yeni bir asal üstü denenirken geometrik seri baştan hesaplanmaz; önceki değer doğrudan genişletilir.
Somut bir örnek yöntemin neden etkili olduğunu hemen gösterir. Çünkü
$$42=2\cdot 3\cdot 7,$$
dolayısıyla
$$\sigma_2(42)=\left(1+2^2\right)\left(1+3^2\right)\left(1+7^2\right)=5\cdot 10\cdot 50=2500=50^2.$$
Demek ki \(42\) son toplama mutlaka eklenir. Dikkat edilirse bölen listesini hiç yazmadık; asal çarpanlara ayırma ve çarpımsallık tek başına sonucu verdi.
C++ ve Python uygulamaları şu tür bir durum taşır:
$$n_0=\prod_{i=1}^k p_i^{e_i},\qquad s_0=\sigma_2(n_0),$$
burada asal sayılar sıkı biçimde artandır. Bu durum, daha büyük bir asal \(q\) ve \(f\ge 1\) üssü seçilerek
$$n=n_0q^f,\qquad \sigma_2(n)=s_0\,G_q(f)$$
şeklinde genişletilir. Yeni asal yalnızca artan sırada eklendiği için \(L\) altındaki her \(n\) tam olarak bir kez üretilir; bu da asal çarpanlara ayırmanın tekliğinden gelir. Ayrıca \(n<L\) koşulu monoton olduğundan, bir asalın belli bir kuvveti sınırı aşınca daha yüksek kuvvetlerin de aynı dalda elenebileceği hemen anlaşılır.
Java uygulaması aynı matematiği farklı bir örgüyle kullanır. Şöyle yazalım:
$$n=mp^e,\qquad p\nmid m,$$
burada \(p\), \(n\)'yi bölen en küçük asaldır. O zaman
$$\sigma_2(n)=\sigma_2(m)\,G_p(e).$$
Dolayısıyla her sayının en küçük asal böleni biliniyorsa, \(n\) sayısı daha küçük bir ortak çarpan \(m\) ve tam bir \(p\)-kuvvetine ayrılır; ardından \(G_p(e)\) kurulur ve \(\sigma_2(n)\), daha önce bulunmuş \(\sigma_2(m)\) ile çarpılarak elde edilir. Böylece bir uygulama ailesi geçerli çarpanlaşmaları doğrudan gezerken, diğeri \(1\) ile \(L-1\) arasındaki bütün \(\sigma_2\) değerlerini tablo halinde doldurur.
Bu uygulamalar önce \(L-1\)'e kadar olan asalları üretir. Sonra artan asallar üzerinde özyinelemeli biçimde ilerler ve her durumda iki tam sayı taşır: mevcut aday \(n_0\) ve zaten bilinen \(\sigma_2(n_0)\). Yeni seçilen her asal \(p\) için, çarpım sınırın altında kaldığı sürece \(1,2,3,\dots\) üsleri denenir; aynı anda asal-kuvvet katkısı \(G_p(e+1)=p^2G_p(e)+1\) bağıntısıyla güncellenir.
Yeni oluşan \(\sigma_2(n)\) tam kare ise ilgili \(n\) doğrudan toplama eklenir. Her izinli çarpanlaşma yalnızca bir kez ziyaret edildiğinden, tekrar kontrolü için ek bir veri yapısına gerek yoktur. C++ sürümü ayrıca en dış seviyedeki asal seçimlerini birkaç iş parçacığına bölerek bağımsız dalları paralel işler.
Java sürümü dizi tabanlı bir yol seçer. Önce sınır altındaki her tamsayının en küçük asal bölenini hesaplar. Sonra \(n=2,3,\dots,L-1\) sırasıyla işlenir. Eğer \(n\) asal ise
$$\sigma_2(n)=1+n^2$$
hemen elde edilir. Eğer bileşikse, en küçük asal bölenin tam kuvveti \(p^e\) ayrıştırılır, \(G_p(e)=1+p^2+\cdots+p^{2e}\) hesaplanır ve bu değer daha küçük ortak çarpan için önceden bilinen \(\sigma_2(m)\) ile çarpılır. Dizi tamamlandıktan sonra son bir tarama bütün \(\sigma_2(n)\) değerlerini tam kare testinden geçirir ve uygun \(n\)'leri toplar.
Tam kare testi yaklaşık değil, kesin olmalıdır. Python doğrudan tamsayı karekökünü kullanır. C++ ve Java ise önce kayan noktalı bir \(\sqrt{\sigma_2(n)}\) tahmini alır, ardından adayı aşağı ya da yukarı düzelterek
$$r^2\le \sigma_2(n) < (r+1)^2$$
aralığını garanti eder. Kabul ancak gerçekten \(r^2=\sigma_2(n)\) olduğunda yapılır; böylece yuvarlama hataları sonucu bozmaz.
Aynı matematik kullanılmasına rağmen maliyet profilleri aynı değildir. C++ ve Python'daki özyinelemeli yaklaşım çıktı-duyarlıdır: çalışma süresi, \(n<L\) kısıtı altında gerçekten ziyaret edilen asal-üs durumlarının sayısıyla orantılıdır. Özyineleme derinliği seçilmiş farklı asal sayısı kadardır; pratikte küçüktür ve genel olarak en fazla \(O(\log L)\) mertebesindedir. Bellek kullanımı esas olarak asal listesi ve özyineleme yığınıdır.
Java yaklaşımı daha çok bellek kullanır ama akışı daha düzenlidir. \(L\)'nin altındaki bütün sayılar için diziler tuttuğu için alan maliyeti \(O(L)\)'dir. Zaman maliyeti ise en küçük asal bölen eleği, tüm \(\sigma_2(n)\) değerlerinin kurulması ve son kare testi taraması tarafından belirlenir. Bu sabit Project Euler sınırında iki yaklaşım da pratiktir: biri yalnızca çarpanlaşma durumlarını gezerek belleği korur, diğeri ise belleğe yüklenip her \(n\) üzerindeki hesabı çok doğrudan yapar.
En este problema se fija \(L=64{,}000{,}000\) y se estudia la función suma de cuadrados de divisores
$$\sigma_2(n)=\sum_{d\mid n} d^2.$$
Lo que hay que calcular es
$$\sum_{\substack{1 \le n \lt L \\ \exists r\in \mathbb{Z}_{\ge 0}:\ \sigma_2(n)=r^2}} n.$$
La condición no depende de listar divisores uno por uno, sino de entender cómo se construye \(\sigma_2(n)\) a partir de la factorización prima de \(n\). Como \(\sigma_2(1)=1\), el número \(1\) ya pertenece a la suma; la parte interesante es descubrir qué otros enteros menores que el límite también cumplen la condición.
Las tres implementaciones comparten la misma base teórica. Una vez que \(\sigma_2\) se escribe en términos de potencias primas, el problema se convierte en una tarea de generación o de tabulación exacta: producir candidatos \(n\), obtener \(\sigma_2(n)\) sin error y comprobar si el valor es un cuadrado.
Si \(a\) y \(b\) son coprimos, cada divisor de \(ab\) se escribe de forma única como \(d_1d_2\), con \(d_1\mid a\) y \(d_2\mid b\). Por tanto,
$$\sigma_2(ab)=\sum_{d\mid ab} d^2=\sum_{d_1\mid a}\sum_{d_2\mid b}(d_1d_2)^2=\sigma_2(a)\sigma_2(b).$$
Así, \(\sigma_2\) es multiplicativa. Si
$$n=\prod_{i=1}^r p_i^{e_i},$$
entonces
$$\sigma_2(n)=\prod_{i=1}^r\left(1+p_i^2+p_i^4+\cdots+p_i^{2e_i}\right).$$
Esta fórmula es el centro de toda la solución: el test de cuadrado perfecto para \(\sigma_2(n)\) queda totalmente determinado por las contribuciones de las potencias primas.
Para una prima fija \(p\), definimos
$$G_p(e)=1+p^2+p^4+\cdots+p^{2e}=\frac{p^{2(e+1)}-1}{p^2-1}.$$
Entonces
$$\sigma_2(n)=\prod_i G_{p_i}(e_i).$$
La forma cerrada es cómoda para la derivación, pero el código se apoya sobre todo en la identidad incremental
$$G_p(0)=1,\qquad G_p(e+1)=p^2\,G_p(e)+1.$$
Eso permite pasar de un exponente al siguiente sin recomputar la suma geométrica completa. En otras palabras, al extender una factorización con una potencia más alta de \(p\), basta multiplicar el factor actual por \(p^2\) y sumar 1.
Un ejemplo concreto aclara enseguida el mecanismo. Como
$$42=2\cdot 3\cdot 7,$$
tenemos
$$\sigma_2(42)=\left(1+2^2\right)\left(1+3^2\right)\left(1+7^2\right)=5\cdot 10\cdot 50=2500=50^2.$$
Por tanto, \(42\) sí debe contarse en la suma final. Lo importante es que no hizo falta generar explícitamente todos sus divisores; la factorización prima y la multiplicatividad bastaron.
Las implementaciones en C++ y Python mantienen estados de la forma
$$n_0=\prod_{i=1}^k p_i^{e_i},\qquad s_0=\sigma_2(n_0),$$
con \(p_1<p_2<\cdots<p_k\). Para extender ese estado se elige una prima mayor \(q\) y un exponente \(f\ge 1\), y se construye
$$n=n_0q^f,\qquad \sigma_2(n)=s_0\,G_q(f).$$
Como las primas solo se introducen en orden creciente, cada entero \(n<L\) aparece exactamente una vez, siguiendo su factorización prima única. Además, la poda es monotónica: si cierta potencia \(q^f\) ya hace que \(n\) sobrepase el límite, entonces todas las potencias mayores de esa misma prima también quedan descartadas.
La implementación en Java usa la misma fórmula de otra manera. Escribimos
$$n=mp^e,\qquad p\nmid m,$$
donde \(p\) es la menor prima que divide a \(n\). Entonces
$$\sigma_2(n)=\sigma_2(m)\,G_p(e).$$
Si ya se conoce el menor factor primo de cada entero, se puede separar de \(n\) toda la potencia \(p^e\), formar el factor geométrico \(G_p(e)\) y multiplicarlo por el valor previamente calculado de \(\sigma_2(m)\). De ese modo, una familia de implementaciones recorre directamente las factorizaciones válidas, mientras que la otra rellena la tabla completa de \(\sigma_2(n)\) desde \(1\) hasta \(L-1\).
Estas implementaciones comienzan construyendo la lista de primos hasta \(L-1\). Después recorren recursivamente primos crecientes y mantienen dos enteros exactos: el candidato actual \(n_0\) y el valor ya conocido \(\sigma_2(n_0)\). Para cada nuevo primo \(p\), prueban exponentes \(1,2,3,\dots\) mientras el producto siga por debajo del límite y actualizan el factor de potencia prima con la recurrencia \(G_p(e+1)=p^2G_p(e)+1\).
Cada vez que el nuevo valor \(\sigma_2(n)\) resulta ser un cuadrado perfecto, el entero correspondiente se suma al acumulado. Como cada factorización admisible se visita una sola vez, no hace falta ninguna estructura adicional para eliminar duplicados. La versión en C++ además reparte las ramas exteriores del árbol entre varios hilos, porque esas ramas son independientes entre sí.
La versión de Java sigue un camino basado en arreglos. Primero calcula el menor factor primo de cada entero menor que el límite. Luego procesa \(n=2,3,\dots,L-1\) en orden. Si \(n\) es primo, entonces
$$\sigma_2(n)=1+n^2.$$
Si \(n\) es compuesto, se extrae la potencia completa \(p^e\) del menor factor primo, se forma \(G_p(e)=1+p^2+\cdots+p^{2e}\) y se multiplica por el valor ya conocido \(\sigma_2(m)\) del cofactor restante. Después de llenar el arreglo, un último barrido detecta cuáles valores son cuadrados perfectos y suma los \(n\) válidos.
La comprobación de cuadrado debe ser exacta. Python usa la raíz cuadrada entera directamente. C++ y Java parten de una aproximación de \(\sqrt{\sigma_2(n)}\) en coma flotante, pero luego corrigen el candidato hacia arriba o hacia abajo hasta asegurar que
$$r^2\le \sigma_2(n) < (r+1)^2.$$
Solo entonces aceptan el número cuando realmente \(r^2=\sigma_2(n)\). Así se evita que un error de redondeo produzca un falso positivo.
Las tres implementaciones comparten la misma matemática, pero no el mismo perfil de coste. El enfoque recursivo de C++ y Python es sensible al número de estados generados: su tiempo es proporcional a la cantidad de combinaciones de primos y exponentes visitadas bajo la restricción \(n<L\). La profundidad de la recursión coincide con el número de factores primos distintos elegidos, por lo que es pequeña en la práctica y, en general, está acotada por \(O(\log L)\). La memoria queda dominada por la lista de primos y la pila recursiva.
El enfoque de Java consume más memoria, pero ofrece un flujo de trabajo muy regular. Como mantiene arreglos indexados por todos los enteros menores que \(L\), su uso de espacio es \(O(L)\). El tiempo está dominado por la criba de factores primos mínimos, la construcción de todos los valores \(\sigma_2(n)\) y el barrido final del test de cuadrados. Para el límite fijo del problema, ambos caminos son prácticos: uno ahorra memoria explorando solo factorizaciones, y el otro invierte memoria para simplificar el cálculo de cada entero.
本题固定上界 \(L=64{,}000{,}000\)，研究的对象是因子平方和函数
$$\sigma_2(n)=\sum_{d\mid n} d^2.$$
要求计算的是
$$\sum_{\substack{1 \le n \lt L \\ \exists r\in \mathbb{Z}_{\ge 0}:\ \sigma_2(n)=r^2}} n.$$
难点不在于把一个整数的所有因子逐个列出来，而在于怎样利用素因子分解直接得到 \(\sigma_2(n)\)。因为 \(\sigma_2(1)=1\)，所以 \(n=1\) 一定计入答案；真正需要解决的是，在 \(64{,}000{,}000\) 以下还有哪些整数也满足同样的平方条件。
三个实现共享同一套数论骨架：先把 \(\sigma_2(n)\) 写成素数幂贡献的乘积，再据此决定是按因式分解树去枚举候选，还是按从小到大的顺序把所有 \(\sigma_2(n)\) 值整张表填出来。无论采用哪种程序结构，真正起作用的都是同一个公式。
如果 \(a\) 与 \(b\) 互素，那么 \(ab\) 的每个因子都能唯一写成 \(d_1d_2\)，其中 \(d_1\mid a\)，\(d_2\mid b\)。于是
$$\sigma_2(ab)=\sum_{d\mid ab} d^2=\sum_{d_1\mid a}\sum_{d_2\mid b}(d_1d_2)^2=\left(\sum_{d_1\mid a} d_1^2\right)\left(\sum_{d_2\mid b} d_2^2\right)=\sigma_2(a)\sigma_2(b).$$
这说明 \(\sigma_2\) 是乘法函数。若
$$n=\prod_{i=1}^r p_i^{e_i},$$
则有
$$\sigma_2(n)=\prod_{i=1}^r\left(1+p_i^2+p_i^4+\cdots+p_i^{2e_i}\right).$$
这一步是整道题的核心，因为 \(\sigma_2(n)\) 是否为完全平方数，已经完全由各个素数幂因子的贡献决定了。
对固定素数 \(p\)，定义
$$G_p(e)=1+p^2+p^4+\cdots+p^{2e}=\frac{p^{2(e+1)}-1}{p^2-1}.$$
于是可以写成
$$\sigma_2(n)=\prod_i G_{p_i}(e_i).$$
从推导角度看，闭式表达很自然；但从实现角度看，更有用的是下面这个递推：
$$G_p(0)=1,\qquad G_p(e+1)=p^2\,G_p(e)+1.$$
原因很简单：把 \(1+p^2+\cdots+p^{2e}\) 先乘以 \(p^2\)，再加上 1，就得到下一层 \(1+p^2+\cdots+p^{2e}+p^{2e+2}\)。这样程序在把某个素数的指数从 \(e\) 扩展到 \(e+1\) 时，不必重新求整段等比级数，只需在旧值上做一次常数时间更新。
看一个真正有代表性的例子。因为
$$42=2\cdot 3\cdot 7,$$
所以
$$\sigma_2(42)=\left(1+2^2\right)\left(1+3^2\right)\left(1+7^2\right)=5\cdot 10\cdot 50=2500=50^2.$$
因此 \(42\) 必须被计入最终答案。这个例子说明了为什么乘法性如此关键：根本不需要先列出 42 的所有因子，再逐个平方后求和；只要知道素因子分解，就能立刻得到 \(\sigma_2(42)\)。
C++ 和 Python 实现维护的状态可以写成
$$n_0=\prod_{i=1}^k p_i^{e_i},\qquad s_0=\sigma_2(n_0),$$
其中 \(p_1<p_2<\cdots<p_k\) 严格递增。扩展这个状态时，程序只会再选一个更大的素数 \(q\) 以及指数 \(f\ge 1\)，构造
$$n=n_0q^f,\qquad \sigma_2(n)=s_0\,G_q(f).$$
由于素数只按递增顺序引入，所以每个 \(n<L\) 都恰好沿着自己的唯一素因子分解出现一次，不会重复生成。并且约束 \(n<L\) 具有单调性：一旦某个 \(q^f\) 已经让乘积超界，那么同一素数的更高次幂只会更大，因此可以整段剪枝。
Java 实现使用的是同一公式的另一种展开方式。把 \(n\) 写成
$$n=mp^e,\qquad p\nmid m,$$
其中 \(p\) 是 \(n\) 的最小素因子。于是
$$\sigma_2(n)=\sigma_2(m)\,G_p(e).$$
这意味着，只要预先知道每个整数的最小素因子，就能先把 \(n\) 中完整的 \(p^e\) 剥离出来，再构造等比因子 \(G_p(e)\)，最后用已经算出的较小值 \(\sigma_2(m)\) 恢复 \(\sigma_2(n)\)。也就是说，一组实现是沿着因式分解树直接搜索，另一组实现则把从 \(1\) 到 \(L-1\) 的全部 \(\sigma_2\) 值逐个填入数组。
这两种实现先生成不超过 \(L-1\) 的素数表。随后它们以递归方式沿着递增素数展开，并在每个状态中携带两个精确整数：当前候选 \(n_0\) 与已知的 \(\sigma_2(n_0)\)。对每个新选择的素数 \(p\)，程序依次尝试指数 \(1,2,3,\dots\)，只要乘积仍小于上界就继续扩展；与此同时，素数幂贡献通过 \(G_p(e+1)=p^2G_p(e)+1\) 这个递推直接更新。
只要新的 \(\sigma_2(n)\) 是完全平方数，对应的 \(n\) 就立刻加入累计和。因为每个合法因式分解只会被访问一次，所以不需要额外的去重结构。C++ 实现还把最外层的若干起始素数分给多个线程处理，从而让互不依赖的递归子树并行运行。
Java 实现选择了数组化方案。首先计算每个小于上界的整数的最小素因子。然后按顺序处理 \(n=2,3,\dots,L-1\)。如果 \(n\) 本身是素数，那么立即有
$$\sigma_2(n)=1+n^2.$$
如果 \(n\) 是合数，程序就提取出最小素因子的完整幂 \(p^e\)，形成 \(G_p(e)=1+p^2+\cdots+p^{2e}\)，再与剩余因子对应的已知值 \(\sigma_2(m)\) 相乘。数组全部填完之后，再做一次线性扫描，检查哪些 \(\sigma_2(n)\) 是完全平方数，并把对应的 \(n\) 累加起来。
平方测试不能依赖近似值。Python 直接使用整数平方根。C++ 与 Java 则先取得一个浮点平方根近似，再向上或向下微调，直到保证
$$r^2\le \sigma_2(n) < (r+1)^2.$$
只有在真正满足 \(r^2=\sigma_2(n)\) 时才接受这个 \(n\)。这样做可以彻底消除浮点舍入把非平方数误判成平方数的风险。
虽然三份实现使用的是同一数学公式，但代价结构并不相同。C++ 与 Python 的递归方法是状态敏感的：运行时间与满足 \(n<L\) 的素数-指数状态数量成正比。递归深度就是当前选择的不同素因子个数，因此在实际数据下很小，理论上也至多是 \(O(\log L)\) 量级。内存主要消耗在素数表和递归栈上。
Java 的方法则用更多内存换取更规则的流程。因为它为所有小于 \(L\) 的整数保存数组，所以空间复杂度是 \(O(L)\)。时间主要花在最小素因子筛、所有 \(\sigma_2(n)\) 值的构造，以及最后一遍完全平方检测上。对于本题固定的 Project Euler 上界，这两条路线都可行：一种通过只探索因式分解状态来节省空间，另一种通过整表计算让每个整数的处理逻辑非常直接。
В этой задаче задан предел \(L=64{,}000{,}000\) и рассматривается функция суммы квадратов делителей
$$\sigma_2(n)=\sum_{d\mid n} d^2.$$
Нужно вычислить
$$\sum_{\substack{1 \le n \lt L \\ \exists r\in \mathbb{Z}_{\ge 0}:\ \sigma_2(n)=r^2}} n.$$
Суть задачи не в том, чтобы выписывать делители каждого числа по одному, а в том, чтобы выразить \(\sigma_2(n)\) через простую факторизацию числа \(n\). Поскольку \(\sigma_2(1)=1\), число \(1\) сразу входит в искомую сумму; далее нужно найти все остальные \(n\lt L\), для которых значение \(\sigma_2(n)\) тоже оказывается квадратом.
Во всех трех реализациях используется одна и та же арифметическая идея. Как только \(\sigma_2(n)\) переписана через простые степени, задача сводится либо к точному перебору допустимых факторизаций, либо к последовательному построению всех значений \(\sigma_2(n)\) от \(1\) до \(L-1\).
Если числа \(a\) и \(b\) взаимно просты, то каждый делитель числа \(ab\) единственным образом представим в виде \(d_1d_2\), где \(d_1\mid a\) и \(d_2\mid b\). Поэтому
$$\sigma_2(ab)=\sum_{d\mid ab} d^2=\sum_{d_1\mid a}\sum_{d_2\mid b}(d_1d_2)^2=\sigma_2(a)\sigma_2(b).$$
Значит, \(\sigma_2\) является мультипликативной функцией. Если
$$n=\prod_{i=1}^r p_i^{e_i},$$
то отсюда следует
$$\sigma_2(n)=\prod_{i=1}^r\left(1+p_i^2+p_i^4+\cdots+p_i^{2e_i}\right).$$
Именно эта формула лежит в центре решения: условие квадрата для \(\sigma_2(n)\) полностью определяется вкладом степеней простых чисел.
Для фиксированного простого \(p\) введем обозначение
$$G_p(e)=1+p^2+p^4+\cdots+p^{2e}=\frac{p^{2(e+1)}-1}{p^2-1}.$$
Тогда
$$\sigma_2(n)=\prod_i G_{p_i}(e_i).$$
В вычислениях особенно важна не столько замкнутая формула, сколько простая рекурсия
$$G_p(0)=1,\qquad G_p(e+1)=p^2\,G_p(e)+1.$$
Она позволяет при переходе от степени \(e\) к \(e+1\) обновлять соответствующий множитель за константное время. Именно этим пользуются реализации, когда расширяют факторизацию еще одной степенью простого числа.
Полезно посмотреть на конкретный пример. Так как
$$42=2\cdot 3\cdot 7,$$
то
$$\sigma_2(42)=\left(1+2^2\right)\left(1+3^2\right)\left(1+7^2\right)=5\cdot 10\cdot 50=2500=50^2.$$
Следовательно, число \(42\) обязательно входит в итоговую сумму. Здесь хорошо видно основное преимущество подхода: не нужно строить список делителей числа 42, достаточно знать его простое разложение.
Реализации на C++ и Python поддерживают состояние вида
$$n_0=\prod_{i=1}^k p_i^{e_i},\qquad s_0=\sigma_2(n_0),$$
где простые числа упорядочены строго по возрастанию. Далее выбирается большее простое \(q\) и показатель \(f\ge 1\), после чего строится
$$n=n_0q^f,\qquad \sigma_2(n)=s_0\,G_q(f).$$
Поскольку новые простые добавляются только в возрастающем порядке, каждое число \(n<L\) появляется ровно один раз, согласно своей единственной простой факторизации. Условие \(n<L\) монотонно: если какая-то степень \(q^f\) уже выводит число за предел, то все более высокие степени того же простого тоже можно сразу отсечь.
Java-реализация использует ту же математику, но организует вычисление иначе. Представим число как
$$n=mp^e,\qquad p\nmid m,$$
где \(p\) есть наименьший простой делитель числа \(n\). Тогда
$$\sigma_2(n)=\sigma_2(m)\,G_p(e).$$
Если для каждого числа заранее известен его минимальный простой делитель, то можно отделить полную степень \(p^e\), восстановить множитель \(G_p(e)\) и получить \(\sigma_2(n)\) из уже вычисленного меньшего значения \(\sigma_2(m)\). Иными словами, одна группа реализаций напрямую обходит дерево факторизаций, а другая последовательно заполняет таблицу значений \(\sigma_2(n)\) для всех \(n\) ниже границы.
Сначала эти реализации строят список простых чисел до \(L-1\). Затем они рекурсивно проходят по возрастающим простым и несут с собой две точные величины: текущий кандидат \(n_0\) и уже вычисленное значение \(\sigma_2(n_0)\). Для каждого нового простого \(p\) последовательно пробуются показатели \(1,2,3,\dots\), пока произведение не превышает границу; при этом вклад простой степени обновляется по рекурсии \(G_p(e+1)=p^2G_p(e)+1\).
Как только новое значение \(\sigma_2(n)\) оказывается полным квадратом, соответствующее число \(n\) добавляется в сумму. Поскольку каждая допустимая факторизация посещается только один раз, отдельная структура для удаления повторов не нужна. C++-версия дополнительно распараллеливает верхние ветви дерева по нескольким потокам, так как эти подзадачи независимы друг от друга.
Java-версия идет по пути массивов. Сначала она вычисляет минимальный простой делитель для каждого числа ниже предела. Затем числа \(n=2,3,\dots,L-1\) обрабатываются по порядку. Если \(n\) простое, то сразу выполняется
$$\sigma_2(n)=1+n^2.$$
Если \(n\) составное, из него выделяется полная степень \(p^e\) минимального простого делителя, формируется множитель \(G_p(e)=1+p^2+\cdots+p^{2e}\), и затем этот множитель умножается на уже известное значение \(\sigma_2(m)\) для оставшегося кофактора. После заполнения массива остается один линейный проход, который проверяет каждое \(\sigma_2(n)\) на квадратность и суммирует подходящие \(n\).
Проверка должна быть строгой, а не приблизительной. Python использует целочисленный квадратный корень напрямую. В C++ и Java сначала берется приближенное значение \(\sqrt{\sigma_2(n)}\) в плавающей арифметике, а затем кандидат корректируется вверх или вниз, пока не станет верно
$$r^2\le \sigma_2(n) < (r+1)^2.$$
Только после этого число принимается, если действительно выполняется равенство \(r^2=\sigma_2(n)\). Такой шаг устраняет риск ложного срабатывания из-за округления.
Хотя математическая основа одинакова, вычислительные профили различаются. Рекурсивный подход в C++ и Python чувствителен к числу реально посещенных состояний: время работы пропорционально количеству допустимых комбинаций простых и показателей, которые укладываются в условие \(n<L\). Глубина рекурсии равна числу различных выбранных простых множителей, поэтому на практике она мала и в общем случае не превосходит \(O(\log L)\). Память в основном уходит на список простых и стек рекурсии.
Подход Java расходует больше памяти, но зато имеет очень ровный поток выполнения. Поскольку он хранит массивы для всех целых чисел ниже \(L\), объем памяти равен \(O(L)\). Время определяется решетом минимальных простых делителей, построением всех значений \(\sigma_2(n)\) и заключительным проходом проверки на квадрат. Для фиксированного предела из задачи оба подхода практичны: один экономит память за счет обхода только дерева факторизаций, другой платит памятью за прямое вычисление для каждого \(n\).
في هذه المسألة يكون الحد \(L=64{,}000{,}000\)، وندرس دالة مجموع مربعات القواسم
$$\sigma_2(n)=\sum_{d\mid n} d^2.$$
والمطلوب هو حساب
$$\sum_{\substack{1 \le n \lt L \\ \exists r\in \mathbb{Z}_{\ge 0}:\ \sigma_2(n)=r^2}} n.$$
الصعوبة ليست في توليد قواسم كل عدد واحدًا واحدًا، بل في فهم كيف تتحدد \(\sigma_2(n)\) مباشرة من التحليل الأولي للعدد \(n\). وبما أن \(\sigma_2(1)=1\)، فإن \(1\) يدخل في المجموع تلقائيًا؛ أما العمل الحقيقي فهو تحديد الأعداد الأخرى الأصغر من الحد والتي تحقق الشرط نفسه.
الهيكل الرياضي المشترك بين جميع التطبيقات هو وصف \(\sigma_2\) بدلالة قوى الأعداد الأولية. بعد الوصول إلى هذه الصيغة، تتحول المسألة إلى أحد مسارين: إما تعداد التحليلات الأولية الممكنة مباشرة، أو بناء جميع قيم \(\sigma_2(n)\) من \(1\) حتى \(L-1\) بشكل جدولي.
إذا كان \(a\) و\(b\) أوليين فيما بينهما، فإن كل قاسم للعدد \(ab\) يكتب بصورة وحيدة على شكل \(d_1d_2\)، حيث \(d_1\mid a\) و\(d_2\mid b\). ولذلك
$$\sigma_2(ab)=\sum_{d\mid ab} d^2=\sum_{d_1\mid a}\sum_{d_2\mid b}(d_1d_2)^2=\sigma_2(a)\sigma_2(b).$$
إذًا \(\sigma_2\) دالة ضربية. وإذا كتبنا
$$n=\prod_{i=1}^r p_i^{e_i},$$
فإننا نحصل على
$$\sigma_2(n)=\prod_{i=1}^r\left(1+p_i^2+p_i^4+\cdots+p_i^{2e_i}\right).$$
وهذه هي النقطة المركزية في الحل كله: كون \(\sigma_2(n)\) مربعًا كاملًا يتحدد بالكامل من مساهمات قوى العوامل الأولية.
لعدد أولي ثابت \(p\)، نعرّف
$$G_p(e)=1+p^2+p^4+\cdots+p^{2e}=\frac{p^{2(e+1)}-1}{p^2-1}.$$
وعندها يصبح
$$\sigma_2(n)=\prod_i G_{p_i}(e_i).$$
الصيغة المغلقة مفيدة في الشرح، لكن التطبيقات تعتمد عمليًا على العلاقة الأبسط
$$G_p(0)=1,\qquad G_p(e+1)=p^2\,G_p(e)+1.$$
فهذه العلاقة تسمح بزيادة الأس من \(e\) إلى \(e+1\) من دون إعادة حساب المتسلسلة الهندسية كاملة من البداية. لذلك عندما يمدد البرنامج فرعًا جديدًا في شجرة التحليل، فإنه يحدّث العامل الخاص بذلك العدد الأولي تحديثًا مباشرًا وبسيطًا.
المثال التالي يوضح الفكرة بوضوح. بما أن
$$42=2\cdot 3\cdot 7,$$
فإن
$$\sigma_2(42)=\left(1+2^2\right)\left(1+3^2\right)\left(1+7^2\right)=5\cdot 10\cdot 50=2500=50^2.$$
إذن العدد \(42\) يدخل في المجموع النهائي. والمغزى هنا أن البرنامج لا يحتاج إلى بناء قائمة جميع قواسم 42 صراحة؛ يكفي التحليل الأولي مع خاصية الضرب للوصول إلى النتيجة مباشرة.
تحتفظ تطبيقات C++ وPython بحالة من الشكل
$$n_0=\prod_{i=1}^k p_i^{e_i},\qquad s_0=\sigma_2(n_0),$$
بحيث تكون الأعداد الأولية مرتبة ترتيبًا تصاعديًا صارمًا. وعند توسيع هذه الحالة، يُختار عدد أولي أكبر \(q\) مع أس \(f\ge 1\)، ثم يُبنى
$$n=n_0q^f,\qquad \sigma_2(n)=s_0\,G_q(f).$$
وبما أن كل عدد أولي جديد لا يدخل إلا بعد تثبيت جميع الأصغر منه، فإن كل عدد \(n<L\) يُولد مرة واحدة تمامًا وفق تحليله الأولي الوحيد. كما أن شرط \(n<L\) شرط رتيب: فإذا جعلت قوة معينة \(q^f\) العدد يتجاوز الحد، فإن جميع القوى الأعلى للعدد الأولي نفسه ستتجاوز الحد أيضًا، ولذلك يمكن قطع ذلك الفرع كله مباشرة.
تطبيق Java يستخدم الرياضيات نفسها لكن بأسلوب مختلف. نكتب
$$n=mp^e,\qquad p\nmid m,$$
حيث \(p\) هو أصغر عدد أولي يقسم \(n\). عندئذ
$$\sigma_2(n)=\sigma_2(m)\,G_p(e).$$
وهذا يعني أنه إذا عُرف أصغر عامل أولي لكل عدد مسبقًا، أمكن فصل القوة الكاملة \(p^e\) عن \(n\)، وبناء العامل الهندسي \(G_p(e)\)، ثم استرجاع \(\sigma_2(n)\) من القيمة الأصغر المحسوبة سابقًا وهي \(\sigma_2(m)\). بهذا المعنى، هناك عائلة من التطبيقات تستكشف شجرة التحليل الأولي مباشرة، وعائلة أخرى تملأ جدولًا كاملًا للقيم \(\sigma_2(1),\dots,\sigma_2(L-1)\).
تبدأ هذه التطبيقات ببناء قائمة الأعداد الأولية حتى \(L-1\). بعد ذلك تسير عوديًا عبر أعداد أولية متزايدة، وتحمل في كل حالة عددين صحيحين دقيقين: المرشح الحالي \(n_0\) والقيمة المعروفة \(\sigma_2(n_0)\). ولكل عدد أولي جديد \(p\)، تُجرَّب الأسس \(1,2,3,\dots\) ما دام حاصل الضرب يبقى دون الحد، وفي الوقت نفسه يُحدَّث عامل القوة الأولية بواسطة العلاقة \(G_p(e+1)=p^2G_p(e)+1\).
كلما أصبحت القيمة الجديدة \(\sigma_2(n)\) مربعًا كاملًا، يضاف العدد الموافق \(n\) إلى المجموع الجاري. ولأن كل تحليل أولي مقبول يُزار مرة واحدة فقط، فلا حاجة إلى بنية إضافية لإزالة التكرار. كما أن نسخة C++ توزع الفروع العليا من الشجرة على عدة خيوط، لأن هذه الفروع مستقلة عن بعضها.
أما تنفيذ Java فيسلك طريقًا يعتمد على المصفوفات. فهو يحسب أولًا أصغر عامل أولي لكل عدد أصغر من الحد، ثم يعالج الأعداد \(n=2,3,\dots,L-1\) بالترتيب. إذا كان \(n\) أوليًا، فلدينا مباشرة
$$\sigma_2(n)=1+n^2.$$
وإذا كان مركبًا، فإنه يستخرج القوة الكاملة \(p^e\) لأصغر عامل أولي، ويكوّن \(G_p(e)=1+p^2+\cdots+p^{2e}\)، ثم يضرب هذا العامل في القيمة المحسوبة مسبقًا \(\sigma_2(m)\) لعامل المرافقة المتبقي. وبعد اكتمال بناء المصفوفة، يُجرى مرور أخير لاختبار القيم التي تمثل مربعات كاملة، ثم تُجمع الأعداد الصحيحة الموافقة لها.
اختبار المربع يجب أن يكون دقيقًا تمامًا. Python يستخدم الجذر التربيعي الصحيح مباشرة. أما C++ وJava فيبدآن بتقدير عشري لـ \(\sqrt{\sigma_2(n)}\)، ثم يصححان المرشح صعودًا أو هبوطًا حتى يضمنا أن
$$r^2\le \sigma_2(n) < (r+1)^2.$$
وبعد ذلك فقط يُقبل العدد إذا تحقق فعلًا أن \(r^2=\sigma_2(n)\). هذا يمنع الأخطاء الناتجة عن التقريب العشري من أن تنتج قبولًا خاطئًا.
مع أن الأساس الرياضي واحد، فإن الكلفة الحسابية ليست متطابقة. المنهج العودي في C++ وPython حساس لعدد الحالات التي تُزار فعلًا: زمن التنفيذ يتناسب مع عدد حالات الأسس الأولية التي تقع تحت القيد \(n<L\). وعمق العودية يساوي عدد العوامل الأولية المختلفة المختارة في الحالة الحالية، ولذلك يبقى صغيرًا عمليًا، وهو نظريًا لا يزيد على رتبة \(O(\log L)\). أما الذاكرة فتتحدد أساسًا بقائمة الأعداد الأولية ومكدس العودية.
منهج Java يستهلك ذاكرة أكبر لكنه يتمتع بتدفق منتظم جدًا. فهو يحتفظ بمصفوفات مفهرسة بجميع الأعداد الصحيحة الأصغر من \(L\)، لذا يكون استهلاك الذاكرة \(O(L)\). ويهيمن على الزمن كل من غربال أصغر عامل أولي، وبناء جميع قيم \(\sigma_2(n)\)، ثم المرور النهائي لاختبار المربعات. وعند الحد الثابت الخاص بهذه المسألة، يكون النهجان عمليين: الأول يوفر الذاكرة لأنه يستكشف فقط حالات التحليل، والثاني يدفع كلفة ذاكرة أكبر مقابل حساب مباشر ومنتظم لكل عدد.