An abc-hit is a triple \((a,b,c)\) such that \(a \lt b\), \(a+b=c\), \(\gcd(a,b)=1\), and \(\operatorname{rad}(abc) \lt c\). Here \(\operatorname{rad}(n)\) means the product of the distinct prime divisors of \(n\). The task is to add all values of \(c\) for abc-hits with \(c \lt 120{,}000\).
A naive search would try every \(a\) for every \(c\), which is far too much work. The implementations succeed because they exploit the exact multiplicative structure of \(\operatorname{rad}(abc)\), and they scan candidate values in increasing order of radical so that most candidates are rejected very early.
The key point is that once \(c\) is fixed, the whole problem is controlled by the radicals of \(a\), \(b=c-a\), and \(c\). That turns the search from a generic triple loop into a heavily pruned one-parameter scan.
Write
$$\operatorname{rad}(n)=\prod_{p\mid n} p.$$
Because \(c=a+b\), the condition \(\gcd(a,b)=1\) automatically forces the other two gcds to be 1 as well:
$$\gcd(a,c)=\gcd(a,a+b)=\gcd(a,b)=1,\qquad \gcd(b,c)=\gcd(b,a+b)=\gcd(a,b)=1.$$
So in every abc-hit the three numbers are pairwise coprime, and therefore
$$\operatorname{rad}(abc)=\operatorname{rad}(a)\operatorname{rad}(b)\operatorname{rad}(c).$$
This identity is what makes the pruning in the code mathematically sound. The test is not approximate: once coprimality is known, the radical of the product is exactly the product of the radicals.
For a fixed \(c\), the equation \(a+b=c\) determines \(b\) from \(a\):
$$b=c-a.$$
The inequality \(a \lt b\) is equivalent to \(a \lt c/2\), so only values
$$1 \le a \lt \frac{c}{2}$$
need to be checked. For each such \(a\), we test the two conditions
$$\gcd(a,c-a)=1,\qquad \operatorname{rad}(a)\operatorname{rad}(c-a)\operatorname{rad}(c) \lt c.$$
If \(\operatorname{rad}(c)\ge c\), then the radical inequality is already impossible because \(\operatorname{rad}(a)\ge 1\) and \(\operatorname{rad}(b)\ge 1\). That is why many values of \(c\) terminate immediately.
Let \(r_c=\operatorname{rad}(c)\). Any abc-hit must satisfy
$$\operatorname{rad}(a)\operatorname{rad}(b)r_c \lt c.$$
In particular, \(\operatorname{rad}(a)\) must be small. The implementations sort all positive integers below the limit by \(\operatorname{rad}(n)\) and, for each fixed \(c\), scan that list only until the radical gets too large.
The cutoff used in the code is the integer quotient
$$q=\left\lfloor \frac{c}{r_c}\right\rfloor.$$
Once \(\operatorname{rad}(a)\ge q\), the scan can stop. If \(\operatorname{rad}(a) \gt q\), then already \(\operatorname{rad}(a)r_c \gt c\). If \(\operatorname{rad}(a)=q\), then either \(qr_c=c\), which fails the strict inequality immediately, or \(qr_c \lt c \lt (q+1)r_c\). In that second case \(b \gt 1\), so \(\operatorname{rad}(b)\ge 2\), and therefore
$$\operatorname{rad}(a)\operatorname{rad}(b)r_c \ge 2qr_c \ge c.$$
So the radical-sorted list really does allow an early break, not merely a heuristic skip. The extra check \(a \lt c/2\) is still needed, because the list is sorted by radical, not by numeric value.
Take \(c=9\). Then \(\operatorname{rad}(9)=3\), so the radical cutoff is
$$q=\left\lfloor \frac{9}{3}\right\rfloor=3.$$
Only candidates with \(\operatorname{rad}(a) \lt 3\) can matter, and \(a \lt 9/2\) leaves \(a=1,2,4\).
For \(a=1\), we get \(b=8\), and
$$\operatorname{rad}(1)\operatorname{rad}(8)\operatorname{rad}(9)=1\cdot 2\cdot 3=6 \lt 9,$$
with \(\gcd(1,8)=1\). So \((1,8,9)\) is an abc-hit.
For \(a=2\), \(b=7\), and the radical product is \(2\cdot 7\cdot 3=42\), which fails. For \(a=4\), \(b=5\), and the product is \(2\cdot 5\cdot 3=30\), which also fails. This is exactly the pattern used at scale: a cheap radical cutoff finds a short candidate list, then the full radical product and gcd test decide the survivors.
The C++, Python, and Java implementations all follow the same two-stage algorithm: first build radicals efficiently, then enumerate \(c\) and scan only the low-radical values of \(a\).
The implementation starts with an array filled with 1. It then runs a prime sieve. Whenever a prime \(p\) is discovered, every multiple of \(p\) has its radical multiplied by \(p\) exactly once. After this pass, each entry stores the product of the distinct prime factors of its index.
At the same time, the program prepares a collection of all integers \(1,2,\dots,119{,}999\) arranged in increasing order of \(\operatorname{rad}(n)\), with the numeric value used as a tie-breaker. That ordering is the backbone of the later pruning.
For each \(c\) from 3 up to \(119{,}999\), the implementation computes \(r_c=\operatorname{rad}(c)\) and the quotient \(q=\lfloor c/r_c\rfloor\). It then walks through the pre-sorted candidate list and stops as soon as the candidate radical reaches \(q\).
Each candidate still has to pass three exact filters: it must satisfy \(a \lt c/2\), it defines \(b=c-a\), and then the code checks both
$$\operatorname{rad}(a)\operatorname{rad}(b)\operatorname{rad}(c) \lt c$$
and
$$\gcd(a,b)=1.$$
Whenever both tests succeed, the current \(c\) is added to the answer. One implementation also includes a small checkpoint: for the reduced bound \(c \lt 1000\), the partial sum is \(12523\).
Let \(N=120{,}000\). The sieve that computes all radicals costs \(O(N\log\log N)\), and sorting the integers by radical costs \(O(N\log N)\).
The dominant work is the search over candidates. In the worst case, the radical cutoff may still leave many entries, so the main loop is \(O(N^2)\) candidate visits, with an additional \(O(\log N)\) factor for the gcd test if one writes that cost explicitly. In practice it runs much faster than a full quadratic scan because most values of \(c\) have a small quotient \(c/\operatorname{rad}(c)\), so the radical-ordered loop breaks early. Memory usage is \(O(N)\).
Ein abc-hit ist ein Tripel \((a,b,c)\) mit \(a \lt b\), \(a+b=c\), \(\gcd(a,b)=1\) und \(\operatorname{rad}(abc) \lt c\). Dabei bezeichnet \(\operatorname{rad}(n)\) das Produkt aller verschiedenen Primteiler von \(n\). Gesucht ist die Summe aller Werte \(c\) mit \(c \lt 120{,}000\), für die ein abc-hit vorliegt.
Eine naive Suche würde für jedes \(c\) fast alle möglichen Werte von \(a\) prüfen. Das ist zu langsam. Die Implementierungen sind erfolgreich, weil sie die genaue Struktur von \(\operatorname{rad}(abc)\) ausnutzen und mögliche Kandidaten in aufsteigender Reihenfolge ihres Radikals durchsuchen.
Ist \(c\) fest, dann hängt die ganze Entscheidung nur noch von den Radikalen von \(a\), \(b=c-a\) und \(c\) ab. Dadurch wird aus einer unspezifischen Dreifachsuche eine stark beschnittene Suche mit nur einer freien Variablen.
Wir schreiben
$$\operatorname{rad}(n)=\prod_{p\mid n} p.$$
Aus \(c=a+b\) folgt zusammen mit \(\gcd(a,b)=1\) sofort
$$\gcd(a,c)=\gcd(a,a+b)=\gcd(a,b)=1,\qquad \gcd(b,c)=\gcd(b,a+b)=\gcd(a,b)=1.$$
Also sind \(a\), \(b\) und \(c\) in jedem abc-hit paarweise teilerfremd. Daher gilt exakt
$$\operatorname{rad}(abc)=\operatorname{rad}(a)\operatorname{rad}(b)\operatorname{rad}(c).$$
Das ist der zentrale mathematische Schritt hinter der gesamten Optimierung. Sobald die Teilerfremdheit feststeht, ist die Radikalbedingung keine grobe Abschätzung mehr, sondern eine genaue Produktformel.
Für festes \(c\) ist
$$b=c-a.$$
Die Bedingung \(a \lt b\) ist gleichbedeutend mit \(a \lt c/2\). Man muss also nur
$$1 \le a \lt \frac{c}{2}$$
untersuchen. Für jeden solchen Wert sind genau zwei Tests nötig:
$$\gcd(a,c-a)=1,\qquad \operatorname{rad}(a)\operatorname{rad}(c-a)\operatorname{rad}(c) \lt c.$$
Schon \(\operatorname{rad}(c)\ge c\) schließt einen Treffer aus, denn \(\operatorname{rad}(a)\ge 1\) und \(\operatorname{rad}(b)\ge 1\). Darum enden viele Werte von \(c\) sofort ohne weitere Arbeit.
Setze \(r_c=\operatorname{rad}(c)\). Für jeden abc-hit muss gelten
$$\operatorname{rad}(a)\operatorname{rad}(b)r_c \lt c.$$
Insbesondere muss \(\operatorname{rad}(a)\) klein sein. Die Implementierungen sortieren deshalb alle positiven Zahlen unterhalb der Schranke nach \(\operatorname{rad}(n)\) und laufen für jedes feste \(c\) nur so weit durch diese Liste, bis das Radikal zu groß wird.
Der im Code verwendete Schnittpunkt ist
$$q=\left\lfloor \frac{c}{r_c}\right\rfloor.$$
Sobald \(\operatorname{rad}(a)\ge q\), kann die Schleife beendet werden. Für \(\operatorname{rad}(a) \gt q\) gilt bereits \(\operatorname{rad}(a)r_c \gt c\). Für \(\operatorname{rad}(a)=q\) gibt es zwei Fälle: Entweder ist \(qr_c=c\), dann scheitert die strenge Ungleichung sofort, oder \(qr_c \lt c \lt (q+1)r_c\). Im zweiten Fall ist \(b \gt 1\), also \(\operatorname{rad}(b)\ge 2\), und damit
$$\operatorname{rad}(a)\operatorname{rad}(b)r_c \ge 2qr_c \ge c.$$
Die vorzeitig abgebrochene Suche ist also mathematisch exakt. Die zusätzliche Prüfung \(a \lt c/2\) bleibt trotzdem nötig, weil die Liste nach Radikal und nicht nach Zahlenwert sortiert ist.
Nehmen wir \(c=9\). Dann ist \(\operatorname{rad}(9)=3\), also
$$q=\left\lfloor \frac{9}{3}\right\rfloor=3.$$
Es kommen nur Werte mit \(\operatorname{rad}(a) \lt 3\) in Frage, und zusammen mit \(a \lt 9/2\) bleiben \(a=1,2,4\).
Für \(a=1\) erhält man \(b=8\) und damit
$$\operatorname{rad}(1)\operatorname{rad}(8)\operatorname{rad}(9)=1\cdot 2\cdot 3=6 \lt 9,$$
sowie \(\gcd(1,8)=1\). Also ist \((1,8,9)\) ein abc-hit.
Für \(a=2\) gilt \(b=7\) und das Radikalprodukt ist \(2\cdot 7\cdot 3=42\). Für \(a=4\) ist \(b=5\) und das Produkt \(2\cdot 5\cdot 3=30\). Beide scheitern. Genau so arbeitet der Algorithmus im Großen: erst eine billige Radikal-Schranke, dann der exakte Produkttest und der ggT-Test.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Zweiphasenstrategie: zuerst alle Radikale effizient vorberechnen, danach jedes \(c\) betrachten und nur die Zahlen \(a\) mit kleinem Radikal prüfen.
Zu Beginn wird ein Feld mit Einsen gefüllt. Danach läuft ein Primzahlsieb. Immer wenn eine Primzahl \(p\) entdeckt wird, wird bei jedem Vielfachen von \(p\) das gespeicherte Radikal genau einmal mit \(p\) multipliziert. Nach diesem Durchlauf enthält jeder Eintrag das Produkt aller verschiedenen Primteiler seines Index.
Anschließend wird eine Sammlung aller Zahlen \(1,2,\dots,119{,}999\) in aufsteigender Reihenfolge von \(\operatorname{rad}(n)\) aufgebaut, mit dem Zahlenwert als Tie-Breaker. Diese Ordnung ermöglicht später das frühe Abbrechen.
Für jedes \(c\) von 3 bis \(119{,}999\) berechnet die Implementierung \(r_c=\operatorname{rad}(c)\) und \(q=\lfloor c/r_c\rfloor\). Danach wird die vorsortierte Kandidatenliste nur bis zu dem Punkt durchlaufen, an dem das Kandidatenradikal \(q\) erreicht.
Jeder Kandidat muss dann noch drei exakte Filter bestehen: \(a \lt c/2\), dann \(b=c-a\), und danach die Prüfungen
$$\operatorname{rad}(a)\operatorname{rad}(b)\operatorname{rad}(c) \lt c$$
und
$$\gcd(a,b)=1.$$
Wenn beide Bedingungen erfüllt sind, wird der aktuelle Wert \(c\) zur Summe addiert. Eine der Implementierungen enthält außerdem einen kleinen Kontrollwert: Für die reduzierte Schranke \(c \lt 1000\) ist die Teilsumme gleich \(12523\).
Sei \(N=120{,}000\). Das Sieb zur Berechnung aller Radikale kostet \(O(N\log\log N)\), das Sortieren nach dem Radikal \(O(N\log N)\).
Der Hauptaufwand liegt in der Kandidatensuche. Im schlechtesten Fall lässt die Radikalschranke noch viele Einträge zu, sodass die Hauptphase \(O(N^2)\) Kandidatenbesuche benötigt; schreibt man die Kosten des ggT explizit mit, kommt ein zusätzlicher Faktor \(O(\log N)\) hinzu. Praktisch ist das Verfahren deutlich schneller als eine vollständige quadratische Suche, weil für die meisten Werte von \(c\) der Quotient \(c/\operatorname{rad}(c)\) klein ist und die nach Radikal sortierte Schleife früh endet. Der Speicherbedarf ist \(O(N)\).
Bir abc-hit, \(a \lt b\), \(a+b=c\), \(\gcd(a,b)=1\) ve \(\operatorname{rad}(abc) \lt c\) koşullarını sağlayan \((a,b,c)\) üçlüsüdür. Burada \(\operatorname{rad}(n)\), \(n\)'in farklı asal bölenlerinin çarpımıdır. Amaç, \(c \lt 120{,}000\) olan bütün abc-hit'ler için \(c\) değerlerini toplamaktır.
Doğrudan arama yapılırsa her \(c\) için çok sayıda \(a\) denenir ve maliyet hızla büyür. Çözümün çalışmasının nedeni, \(\operatorname{rad}(abc)\) ifadesinin bu problemde tam olarak çarpanlara ayrılabilmesi ve adayların radikal değerine göre sıralanarak çok erken elenebilmesidir.
\(c\) sabitlendiğinde problem aslında yalnızca \(a\), \(b=c-a\) ve \(c\) sayılarına ait radikal değerleriyle kontrol edilir. Böylece üçlü arama, yoğun biçimde budanmış tek parametreli bir taramaya dönüşür.
Tanım olarak
$$\operatorname{rad}(n)=\prod_{p\mid n} p$$
yazarız. \(c=a+b\) olduğu için \(\gcd(a,b)=1\) koşulu diğer iki EBOB'u da zorunlu olarak 1 yapar:
$$\gcd(a,c)=\gcd(a,a+b)=\gcd(a,b)=1,\qquad \gcd(b,c)=\gcd(b,a+b)=\gcd(a,b)=1.$$
Yani bir abc-hit içinde \(a\), \(b\) ve \(c\) ikişer ikişer aralarında asaldır. Bu yüzden
$$\operatorname{rad}(abc)=\operatorname{rad}(a)\operatorname{rad}(b)\operatorname{rad}(c)$$
eşitliği tam olarak geçerlidir. Bu, kullanılan budamanın yalnızca sezgisel değil, doğrudan doğruya problem tanımından çıkan kesin bir eşitlik olduğunu gösterir.
\(c\) sabitken
$$b=c-a$$
olur. \(a \lt b\) koşulu da
$$1 \le a \lt \frac{c}{2}$$
aralığını verir. Dolayısıyla her aday için test edilmesi gereken şeyler şunlardır:
$$\gcd(a,c-a)=1,\qquad \operatorname{rad}(a)\operatorname{rad}(c-a)\operatorname{rad}(c) \lt c.$$
Eğer \(\operatorname{rad}(c)\ge c\) ise hit oluşamaz; çünkü \(\operatorname{rad}(a)\ge 1\) ve \(\operatorname{rad}(b)\ge 1\). Bu yüzden birçok \(c\) değeri daha baştan elenir.
\(r_c=\operatorname{rad}(c)\) olsun. Her abc-hit için
$$\operatorname{rad}(a)\operatorname{rad}(b)r_c \lt c$$
gereklidir. Demek ki \(\operatorname{rad}(a)\) küçük olmak zorundadır. Uygulamalar bu yüzden sınırın altındaki tüm pozitif sayıları \(\operatorname{rad}(n)\) değerine göre sıralar ve her sabit \(c\) için bu listenin yalnızca kısa bir ön ekini tarar.
Kodda kullanılan kesme noktası
$$q=\left\lfloor \frac{c}{r_c}\right\rfloor$$
değeridir. \(\operatorname{rad}(a)\ge q\) olduğu anda döngü sonlandırılır. Eğer \(\operatorname{rad}(a) \gt q\) ise zaten \(\operatorname{rad}(a)r_c \gt c\) olur. Eğer \(\operatorname{rad}(a)=q\) ise iki durum vardır: ya \(qr_c=c\) olur ve sıkı eşitsizlik anında bozulur, ya da \(qr_c \lt c \lt (q+1)r_c\). İkinci durumda \(b \gt 1\) olduğu için \(\operatorname{rad}(b)\ge 2\) ve
$$\operatorname{rad}(a)\operatorname{rad}(b)r_c \ge 2qr_c \ge c$$
elde edilir. Yani erken durdurma matematiksel olarak güvenlidir. Bunun yanında listenin sayısal değere göre değil radikale göre sıralı olması nedeniyle \(a \lt c/2\) filtresi ayrıca korunur.
\(c=9\) alalım. O zaman \(\operatorname{rad}(9)=3\) ve
$$q=\left\lfloor \frac{9}{3}\right\rfloor=3$$
olur. Bu nedenle yalnızca \(\operatorname{rad}(a) \lt 3\) olan adaylar düşünülebilir. \(a \lt 9/2\) şartı ile geriye \(a=1,2,4\) kalır.
\(a=1\) için \(b=8\) olur ve
$$\operatorname{rad}(1)\operatorname{rad}(8)\operatorname{rad}(9)=1\cdot 2\cdot 3=6 \lt 9$$
eşitsizliği sağlanır; ayrıca \(\gcd(1,8)=1\). Dolayısıyla \((1,8,9)\) bir abc-hit'tir.
\(a=2\) için \(b=7\) ve radikal çarpımı \(2\cdot 7\cdot 3=42\) olur. \(a=4\) için \(b=5\) ve çarpım \(2\cdot 5\cdot 3=30\) olur. Her ikisi de başarısızdır. Büyük ölçekte yapılan işlem de aynıdır: önce ucuz radikal kesmesi, sonra tam çarpım ve EBOB kontrolü.
C++, Python ve Java uygulamaları aynı iki aşamalı yöntemi uygular: önce tüm radikal değerlerini hızlıca hazırlar, sonra her \(c\) için yalnızca küçük radikale sahip \(a\) adaylarını tarar.
Başlangıçta bir dizi tamamen 1 ile doldurulur. Sonra asal sayıları belirleyen bir elekten geçilir. Bir asal \(p\) bulunduğunda, \(p\)'nin her katındaki radikal değeri yalnızca bir kez \(p\) ile çarpılır. Böylece her indeks için farklı asal bölenlerin çarpımı elde edilir.
Daha sonra \(1,2,\dots,119{,}999\) sayıları, \(\operatorname{rad}(n)\) değerine göre artan sırada tutulur; eşitlik halinde sayının kendisi bağlayıcı olur. Sonraki aşamadaki erken çıkış tamamen bu sıraya dayanır.
\(3\) ile \(119{,}999\) arasındaki her \(c\) için önce \(r_c=\operatorname{rad}(c)\) ve \(q=\lfloor c/r_c\rfloor\) hesaplanır. Sonra önceden sıralanmış aday listesi, adayın radikali \(q\)'ya ulaşana kadar dolaşılır.
Her aday yine de üç kesin filtreden geçmelidir: \(a \lt c/2\), ardından \(b=c-a\), sonra da
$$\operatorname{rad}(a)\operatorname{rad}(b)\operatorname{rad}(c) \lt c$$
ve
$$\gcd(a,b)=1$$
kontrolleri uygulanır. Her iki test de olumluysa o andaki \(c\) toplam cevaba eklenir. Uygulamalardan biri ayrıca küçük bir doğrulama da içerir: \(c \lt 1000\) için ara toplam \(12523\) eder.
\(N=120{,}000\) olsun. Tüm radikalleri üreten elek \(O(N\log\log N)\), radikale göre sıralama ise \(O(N\log N)\) zaman alır.
Baskın maliyet aday taramasıdır. En kötü durumda radikal kesmesi hâlâ çok sayıda girdiyi bırakabilir; bu nedenle ana döngü için \(O(N^2)\) aday ziyareti düşünülür. EBOB hesabı açıkça yazılırsa buna ek bir \(O(\log N)\) çarpanı gelir. Pratikte tam karesel taramadan çok daha hızlıdır; çünkü çoğu \(c\) için \(c/\operatorname{rad}(c)\) oranı küçüktür ve radikale göre sıralanmış döngü erken biter. Bellek kullanımı \(O(N)\)'dir.
Un abc-hit es una terna \((a,b,c)\) que cumple \(a \lt b\), \(a+b=c\), \(\gcd(a,b)=1\) y \(\operatorname{rad}(abc) \lt c\). Aquí \(\operatorname{rad}(n)\) es el producto de los divisores primos distintos de \(n\). El objetivo es sumar todos los valores de \(c\) para los abc-hits con \(c \lt 120{,}000\).
Una búsqueda ingenua probaría demasiados valores de \(a\) para cada \(c\). Las implementaciones evitan ese coste porque aprovechan la forma exacta de \(\operatorname{rad}(abc)\) cuando hay coprimalidad y porque recorren los candidatos en orden creciente de radical, lo que permite cortar el recorrido muy pronto.
Una vez fijado \(c\), toda la decisión depende solo de los radicales de \(a\), de \(b=c-a\) y de \(c\). Eso transforma la búsqueda en una exploración de un solo parámetro con mucha poda.
Escribimos
$$\operatorname{rad}(n)=\prod_{p\mid n} p.$$
Como \(c=a+b\), la condición \(\gcd(a,b)=1\) obliga también a que
$$\gcd(a,c)=\gcd(a,a+b)=\gcd(a,b)=1,\qquad \gcd(b,c)=\gcd(b,a+b)=\gcd(a,b)=1.$$
Por tanto, en todo abc-hit los tres números son coprimos dos a dos, y entonces
$$\operatorname{rad}(abc)=\operatorname{rad}(a)\operatorname{rad}(b)\operatorname{rad}(c).$$
Esa igualdad es la pieza central del método. No se trata de una cota aproximada: gracias a la coprimalidad, el radical del producto coincide exactamente con el producto de los radicales.
Para un \(c\) fijo, se tiene
$$b=c-a.$$
La condición \(a \lt b\) equivale a
$$1 \le a \lt \frac{c}{2}.$$
Así, para cada candidato basta comprobar
$$\gcd(a,c-a)=1,\qquad \operatorname{rad}(a)\operatorname{rad}(c-a)\operatorname{rad}(c) \lt c.$$
Si \(\operatorname{rad}(c)\ge c\), la desigualdad radical ya es imposible porque \(\operatorname{rad}(a)\ge 1\) y \(\operatorname{rad}(b)\ge 1\). Por eso muchos valores de \(c\) se descartan inmediatamente.
Sea \(r_c=\operatorname{rad}(c)\). Todo abc-hit satisface
$$\operatorname{rad}(a)\operatorname{rad}(b)r_c \lt c.$$
En particular, \(\operatorname{rad}(a)\) tiene que ser pequeño. Por eso las implementaciones ordenan todos los enteros positivos por \(\operatorname{rad}(n)\) y, para cada valor fijo de \(c\), solo recorren el prefijo de esa lista cuyo radical aún puede funcionar.
El corte usado en el código es
$$q=\left\lfloor \frac{c}{r_c}\right\rfloor.$$
Cuando \(\operatorname{rad}(a)\ge q\), el recorrido se detiene. Si \(\operatorname{rad}(a) \gt q\), ya se tiene \(\operatorname{rad}(a)r_c \gt c\). Si \(\operatorname{rad}(a)=q\), entonces o bien \(qr_c=c\), y la desigualdad estricta falla de inmediato, o bien \(qr_c \lt c \lt (q+1)r_c\). En este segundo caso, como \(b \gt 1\), se cumple \(\operatorname{rad}(b)\ge 2\), y por tanto
$$\operatorname{rad}(a)\operatorname{rad}(b)r_c \ge 2qr_c \ge c.$$
Así que el corte temprano es exacto. El filtro adicional \(a \lt c/2\) sigue siendo necesario porque la lista está ordenada por radical y no por valor numérico.
Tomemos \(c=9\). Entonces \(\operatorname{rad}(9)=3\), de modo que
$$q=\left\lfloor \frac{9}{3}\right\rfloor=3.$$
Solo pueden importar los candidatos con \(\operatorname{rad}(a) \lt 3\), y la condición \(a \lt 9/2\) deja \(a=1,2,4\).
Para \(a=1\), resulta \(b=8\), y
$$\operatorname{rad}(1)\operatorname{rad}(8)\operatorname{rad}(9)=1\cdot 2\cdot 3=6 \lt 9,$$
además de \(\gcd(1,8)=1\). Por lo tanto, \((1,8,9)\) es un abc-hit.
Para \(a=2\), se obtiene \(b=7\) y el producto radical es \(2\cdot 7\cdot 3=42\). Para \(a=4\), \(b=5\) y el producto es \(2\cdot 5\cdot 3=30\). Ambos fallan. Ese pequeño ejemplo reproduce exactamente la lógica del algoritmo completo.
Las implementaciones en C++, Python y Java siguen el mismo plan en dos fases: primero calculan todos los radicales con un tamiz, y después recorren cada \(c\) probando solo los valores de \(a\) con radical pequeño.
El programa empieza con un arreglo lleno de 1. Luego ejecuta un tamiz de primos. Cuando detecta un primo \(p\), multiplica por \(p\) exactamente una vez el radical almacenado en cada múltiplo de \(p\). Al terminar, cada posición contiene el producto de los factores primos distintos de su índice.
También se prepara una colección con todos los enteros \(1,2,\dots,119{,}999\) ordenados por \(\operatorname{rad}(n)\), usando el propio entero como desempate. Esa ordenación es la que permite salir pronto del bucle interior.
Para cada \(c\) desde 3 hasta \(119{,}999\), la implementación calcula \(r_c=\operatorname{rad}(c)\) y \(q=\lfloor c/r_c\rfloor\). A continuación, recorre la lista preordenada y la detiene en cuanto el radical del candidato alcanza \(q\).
Cada candidato todavía debe superar tres filtros exactos: cumplir \(a \lt c/2\), definir \(b=c-a\), y después verificar
$$\operatorname{rad}(a)\operatorname{rad}(b)\operatorname{rad}(c) \lt c$$
y
$$\gcd(a,b)=1.$$
Cuando ambas comprobaciones son verdaderas, el valor actual de \(c\) se añade a la suma. Una de las implementaciones incorpora además un pequeño control: para el límite reducido \(c \lt 1000\), la suma parcial es \(12523\).
Sea \(N=120{,}000\). El tamiz para calcular los radicales requiere \(O(N\log\log N)\), y ordenar los enteros por su radical cuesta \(O(N\log N)\).
La parte dominante es el barrido de candidatos. En el peor caso, la poda por radical todavía puede dejar muchos elementos, así que la fase principal realiza \(O(N^2)\) visitas de candidatos; si se contabiliza explícitamente el coste del gcd, aparece además un factor \(O(\log N)\). En la práctica, el tiempo es mucho menor que el de una búsqueda cuadrática completa porque la mayoría de los valores de \(c\) tienen un cociente \(c/\operatorname{rad}(c)\) pequeño y el recorrido ordenado por radical se corta muy pronto. El uso de memoria es \(O(N)\).
abc-hit 是满足 \(a \lt b\)、\(a+b=c\)、\(\gcd(a,b)=1\) 且 \(\operatorname{rad}(abc) \lt c\) 的三元组 \((a,b,c)\)。这里 \(\operatorname{rad}(n)\) 表示 \(n\) 的所有不同质因子的乘积。题目要求把所有满足 \(c \lt 120{,}000\) 的 abc-hit 的 \(c\) 全部加起来。
如果直接枚举，每个 \(c\) 都要尝试大量的 \(a\)，代价会非常高。真正可行的做法并不是暴力遍历所有三元组，而是利用这个问题中特有的结构：一旦 \(\gcd(a,b)=1\)，\(\operatorname{rad}(abc)\) 就能精确拆成三个 radical 的乘积；再配合按 radical 排序的候选表，就可以在很早的时候终止内层扫描。
固定 \(c\) 以后，问题的核心其实只剩下三个量：\(\operatorname{rad}(a)\)、\(\operatorname{rad}(b)\) 和 \(\operatorname{rad}(c)\)，其中 \(b=c-a\)。因此这不是一个真正的三变量搜索，而是一个带有强力剪枝的一维扫描问题。
定义
$$\operatorname{rad}(n)=\prod_{p\mid n} p.$$
由于 \(c=a+b\)，条件 \(\gcd(a,b)=1\) 会自动推出另外两组最大公因数也等于 1：
$$\gcd(a,c)=\gcd(a,a+b)=\gcd(a,b)=1,\qquad \gcd(b,c)=\gcd(b,a+b)=\gcd(a,b)=1.$$
所以在任何 abc-hit 中，\(a\)、\(b\)、\(c\) 两两互素。于是可以得到完全精确的公式
$$\operatorname{rad}(abc)=\operatorname{rad}(a)\operatorname{rad}(b)\operatorname{rad}(c).$$
这是整个算法最关键的数学事实。代码里的乘积判定不是近似估计，而是直接来自两两互素后的严格等式。
对固定的 \(c\)，有
$$b=c-a.$$
又因为 \(a \lt b\)，所以只需要枚举
$$1 \le a \lt \frac{c}{2}.$$
对每个这样的 \(a\)，要检查的条件只有两个：
$$\gcd(a,c-a)=1,\qquad \operatorname{rad}(a)\operatorname{rad}(c-a)\operatorname{rad}(c) \lt c.$$
如果 \(\operatorname{rad}(c)\ge c\)，那后一个不等式立刻不可能成立，因为 \(\operatorname{rad}(a)\ge 1\)、\(\operatorname{rad}(b)\ge 1\)。这解释了为什么很多 \(c\) 根本不需要深入搜索。
记 \(r_c=\operatorname{rad}(c)\)。任何 abc-hit 都必须满足
$$\operatorname{rad}(a)\operatorname{rad}(b)r_c \lt c.$$
这说明 \(\operatorname{rad}(a)\) 必须足够小。三种实现都会先把所有正整数按 \(\operatorname{rad}(n)\) 从小到大排好，然后对每个固定的 \(c\) 只扫描这张表的一个前缀。
代码采用的截断值是
$$q=\left\lfloor \frac{c}{r_c}\right\rfloor.$$
一旦 \(\operatorname{rad}(a)\ge q\)，当前 \(c\) 的内层扫描就可以终止。若 \(\operatorname{rad}(a) \gt q\)，显然已有 \(\operatorname{rad}(a)r_c \gt c\)。若 \(\operatorname{rad}(a)=q\)，则要么 \(qr_c=c\)，严格不等式马上失败；要么 \(qr_c \lt c \lt (q+1)r_c\)。在后一种情况下，由于 \(b \gt 1\)，所以 \(\operatorname{rad}(b)\ge 2\)，从而
$$\operatorname{rad}(a)\operatorname{rad}(b)r_c \ge 2qr_c \ge c.$$
因此，这个提前停止并不是经验性技巧，而是有严格证明的剪枝。与此同时，还必须保留 \(a \lt c/2\) 这个过滤条件，因为候选表是按 radical 排序，不是按整数大小排序。
取 \(c=9\)。此时 \(\operatorname{rad}(9)=3\)，所以截断值为
$$q=\left\lfloor \frac{9}{3}\right\rfloor=3.$$
也就是说，只有 \(\operatorname{rad}(a) \lt 3\) 的候选才有可能成功。再结合 \(a \lt 9/2\)，只剩下 \(a=1,2,4\)。
当 \(a=1\) 时，\(b=8\)，并且
$$\operatorname{rad}(1)\operatorname{rad}(8)\operatorname{rad}(9)=1\cdot 2\cdot 3=6 \lt 9,$$
同时 \(\gcd(1,8)=1\)。所以 \((1,8,9)\) 是一个 abc-hit。
当 \(a=2\) 时，\(b=7\)，radical 乘积为 \(2\cdot 7\cdot 3=42\)。当 \(a=4\) 时，\(b=5\)，乘积为 \(2\cdot 5\cdot 3=30\)。二者都失败。这个例子清楚展示了实现的节奏：先用便宜的 radical 上界缩短候选列表，再用完整乘积与 gcd 做精确判断。
C++、Python 和 Java 实现都遵循同一条主线：先批量预处理所有 radical，再逐个枚举 \(c\)，只检查 radical 很小的那些 \(a\)。
程序先建立一个全部填成 1 的数组，然后运行素数筛。每发现一个素数 \(p\)，就把所有 \(p\) 的倍数对应位置各乘一次 \(p\)。这样处理结束后，每个位置存放的就是该整数所有不同质因子的乘积。
同时，程序还会把 \(1,2,\dots,119{,}999\) 按 \(\operatorname{rad}(n)\) 递增排序；若 radical 相同，则按整数本身排序。后面的内层循环是否能很快停止，完全依赖这份有序列表。
对每个 \(3 \le c \lt 120{,}000\)，实现先计算 \(r_c=\operatorname{rad}(c)\) 和 \(q=\lfloor c/r_c\rfloor\)。随后沿着预排序列表向前扫描，一旦候选的 radical 达到 \(q\) 就停止。
每个候选还必须通过三道精确过滤：先满足 \(a \lt c/2\)，再设 \(b=c-a\)，然后检查
$$\operatorname{rad}(a)\operatorname{rad}(b)\operatorname{rad}(c) \lt c$$
以及
$$\gcd(a,b)=1.$$
只有这两个条件都满足时，当前的 \(c\) 才会加入总和。其中一个实现还带有一个小型校验点：当上界改成 \(c \lt 1000\) 时，部分和应为 \(12523\)。
设 \(N=120{,}000\)。预处理所有 radical 的筛法复杂度是 \(O(N\log\log N)\)，按 radical 排序需要 \(O(N\log N)\)。
主耗时来自候选扫描。最坏情况下，某些 \(c\) 的截断值仍然较大，因此主循环可以达到 \(O(N^2)\) 级别的候选访问；若把 gcd 的代价单独写出，还会多一个 \(O(\log N)\) 因子。不过实际运行要快得多，因为大多数 \(c\) 的比值 \(c/\operatorname{rad}(c)\) 很小，按 radical 排序的内层循环会很早结束。空间复杂度为 \(O(N)\)。
abc-hit - это тройка \((a,b,c)\), для которой выполняются условия \(a \lt b\), \(a+b=c\), \(\gcd(a,b)=1\) и \(\operatorname{rad}(abc) \lt c\). Здесь \(\operatorname{rad}(n)\) означает произведение всех различных простых делителей числа \(n\). Нужно просуммировать все значения \(c\) для abc-hit при \(c \lt 120{,}000\).
Прямой перебор оказался бы слишком дорогим: для каждого \(c\) пришлось бы проверять слишком много значений \(a\). Рабочее решение использует точную структуру радикала произведения и перебирает кандидаты в порядке возрастания \(\operatorname{rad}(n)\), так что внутренняя проверка обычно обрывается очень рано.
После фиксации \(c\) задача полностью определяется радикалами чисел \(a\), \(b=c-a\) и самого \(c\). Поэтому вместо полного перебора тройки мы получаем сильно отсеченный перебор по одной свободной переменной.
Используем определение
$$\operatorname{rad}(n)=\prod_{p\mid n} p.$$
Из равенства \(c=a+b\) и условия \(\gcd(a,b)=1\) сразу следует, что и остальные пары тоже взаимно просты:
$$\gcd(a,c)=\gcd(a,a+b)=\gcd(a,b)=1,\qquad \gcd(b,c)=\gcd(b,a+b)=\gcd(a,b)=1.$$
Значит, в любом abc-hit числа \(a\), \(b\) и \(c\) попарно взаимно просты, а потому
$$\operatorname{rad}(abc)=\operatorname{rad}(a)\operatorname{rad}(b)\operatorname{rad}(c).$$
Это главный факт, на котором держится весь алгоритм. После установления взаимной простоты радикал произведения вычисляется точно как произведение радикалов сомножителей.
При фиксированном \(c\) имеем
$$b=c-a.$$
Условие \(a \lt b\) равносильно
$$1 \le a \lt \frac{c}{2}.$$
Следовательно, для каждого кандидата нужно проверить только
$$\gcd(a,c-a)=1,\qquad \operatorname{rad}(a)\operatorname{rad}(c-a)\operatorname{rad}(c) \lt c.$$
Если \(\operatorname{rad}(c)\ge c\), то второе неравенство уже невозможно, поскольку \(\operatorname{rad}(a)\ge 1\) и \(\operatorname{rad}(b)\ge 1\). Поэтому многие значения \(c\) отбрасываются мгновенно.
Обозначим \(r_c=\operatorname{rad}(c)\). Для любого abc-hit необходимо
$$\operatorname{rad}(a)\operatorname{rad}(b)r_c \lt c.$$
Значит, \(\operatorname{rad}(a)\) обязан быть маленьким. Поэтому реализации заранее сортируют все положительные числа ниже предела по \(\operatorname{rad}(n)\) и для каждого фиксированного \(c\) просматривают только начальный кусок этого списка.
В коде используется порог
$$q=\left\lfloor \frac{c}{r_c}\right\rfloor.$$
Как только \(\operatorname{rad}(a)\ge q\), внутренний перебор можно завершить. Если \(\operatorname{rad}(a) \gt q\), то уже \(\operatorname{rad}(a)r_c \gt c\). Если \(\operatorname{rad}(a)=q\), то либо \(qr_c=c\), и строгая оценка немедленно нарушается, либо \(qr_c \lt c \lt (q+1)r_c\). Во втором случае \(b \gt 1\), значит \(\operatorname{rad}(b)\ge 2\), и потому
$$\operatorname{rad}(a)\operatorname{rad}(b)r_c \ge 2qr_c \ge c.$$
Таким образом, ранняя остановка полностью оправдана математически. Дополнительный фильтр \(a \lt c/2\) все равно нужен, потому что список отсортирован по радикалу, а не по величине числа.
Возьмем \(c=9\). Тогда \(\operatorname{rad}(9)=3\), и порог равен
$$q=\left\lfloor \frac{9}{3}\right\rfloor=3.$$
Значит, могут подойти только значения с \(\operatorname{rad}(a) \lt 3\). Условие \(a \lt 9/2\) оставляет \(a=1,2,4\).
Для \(a=1\) получаем \(b=8\), и
$$\operatorname{rad}(1)\operatorname{rad}(8)\operatorname{rad}(9)=1\cdot 2\cdot 3=6 \lt 9,$$
причем \(\gcd(1,8)=1\). Следовательно, \((1,8,9)\) является abc-hit.
Для \(a=2\) имеем \(b=7\), а произведение радикалов равно \(2\cdot 7\cdot 3=42\). Для \(a=4\) получается \(b=5\) и произведение \(2\cdot 5\cdot 3=30\). Оба случая не подходят. Именно так работает полный алгоритм: сначала грубое, но строгое отсечение по радикалу, потом точная проверка произведения и gcd.
Реализации на C++, Python и Java используют один и тот же двухэтапный план: сначала быстро вычисляют все радикалы, затем перебирают \(c\) и рассматривают только те значения \(a\), у которых радикал мал.
Сначала создается массив, заполненный единицами. Затем запускается решето по простым числам. Каждый раз, когда находится простое \(p\), значение радикала у каждого кратного числа умножается на \(p\) ровно один раз. После этого прохода в каждой позиции стоит произведение различных простых делителей соответствующего числа.
Дополнительно строится коллекция чисел \(1,2,\dots,119{,}999\), отсортированная по \(\operatorname{rad}(n)\), а при равенстве радикалов - по самому числу. Именно этот порядок делает возможным ранний выход из внутреннего цикла.
Для каждого \(c\) от 3 до \(119{,}999\) программа вычисляет \(r_c=\operatorname{rad}(c)\) и \(q=\lfloor c/r_c\rfloor\). Затем она идет по заранее отсортированному списку и останавливается, как только радикал кандидата достигает \(q\).
После этого каждый кандидат проходит еще три точных фильтра: проверяется условие \(a \lt c/2\), затем задается \(b=c-a\), а потом выполняются проверки
$$\operatorname{rad}(a)\operatorname{rad}(b)\operatorname{rad}(c) \lt c$$
и
$$\gcd(a,b)=1.$$
Если обе проверки успешны, текущий \(c\) прибавляется к ответу. Одна из реализаций также содержит небольшой контрольный ориентир: при ограничении \(c \lt 1000\) частичная сумма должна быть равна \(12523\).
Пусть \(N=120{,}000\). Решето для вычисления радикалов требует \(O(N\log\log N)\), а сортировка по радикалу требует \(O(N\log N)\).
Основная стоимость приходится на перебор кандидатов. В худшем случае отсечение по радикалу все еще может оставлять много элементов, так что главная фаза дает \(O(N^2)\) посещений кандидатов; если явно учитывать стоимость gcd, добавляется множитель \(O(\log N)\). На практике алгоритм заметно быстрее полного квадратичного перебора, потому что у большинства значений \(c\) отношение \(c/\operatorname{rad}(c)\) невелико, и внутренняя петля, отсортированная по радикалу, обрывается рано. Память имеет порядок \(O(N)\).
الـ abc-hit هو ثلاثي \((a,b,c)\) يحقق الشروط \(a \lt b\)، و\(a+b=c\)، و\(\gcd(a,b)=1\)، و\(\operatorname{rad}(abc) \lt c\). هنا \(\operatorname{rad}(n)\) تعني حاصل ضرب العوامل الأولية المختلفة للعدد \(n\). المطلوب هو جمع جميع قيم \(c\) التي تحقق هذه الشروط عندما يكون \(c \lt 120{,}000\).
البحث المباشر سيجرب عددا كبيرا جدا من القيم \(a\) لكل \(c\)، ولذلك يكون بطيئا جدا. الفكرة الفعالة هي استغلال البنية الدقيقة للتعبير \(\operatorname{rad}(abc)\) في هذه المسألة، ثم ترتيب المرشحين بحسب قيمة radical حتى يمكن إيقاف الحلقة الداخلية مبكرا في معظم الحالات.
بعد تثبيت \(c\)، تصبح المسألة محكومة فقط بقيم radicals للأعداد \(a\) و\(b=c-a\) و\(c\) نفسه. لذلك لا نحتاج إلى فحص ثلاثي عام، بل إلى مسح أحادي المتغير مع قدر كبير من القطع.
نكتب
$$\operatorname{rad}(n)=\prod_{p\mid n} p.$$
وبما أن \(c=a+b\)، فإن الشرط \(\gcd(a,b)=1\) يفرض تلقائيا أن الزوجين الآخرين متوافقان أوليا أيضا:
$$\gcd(a,c)=\gcd(a,a+b)=\gcd(a,b)=1,\qquad \gcd(b,c)=\gcd(b,a+b)=\gcd(a,b)=1.$$
إذن الأعداد \(a\) و\(b\) و\(c\) متباينة أوليا زوجا زوجا داخل أي abc-hit، ومن ثم نحصل على العلاقة الدقيقة
$$\operatorname{rad}(abc)=\operatorname{rad}(a)\operatorname{rad}(b)\operatorname{rad}(c).$$
هذه هي الحقيقة الرياضية الأساسية في الحل كله. بعد إثبات التوافق الأولي زوجيا يصبح radical للجداء مساويا تماما لجداء radicals، لا مجرد حد تقريبي.
عند تثبيت \(c\) يكون
$$b=c-a.$$
كما أن الشرط \(a \lt b\) يكافئ
$$1 \le a \lt \frac{c}{2}.$$
إذن كل ما نحتاج إلى فحصه لكل مرشح هو
$$\gcd(a,c-a)=1,\qquad \operatorname{rad}(a)\operatorname{rad}(c-a)\operatorname{rad}(c) \lt c.$$
إذا كان \(\operatorname{rad}(c)\ge c\)، فإن المتباينة الثانية تصبح مستحيلة مباشرة لأن \(\operatorname{rad}(a)\ge 1\) و\(\operatorname{rad}(b)\ge 1\). لذلك يتم استبعاد عدد كبير من قيم \(c\) منذ البداية.
لنرمز إلى \(\operatorname{rad}(c)\) بالرمز \(r_c\). أي abc-hit لا بد أن يحقق
$$\operatorname{rad}(a)\operatorname{rad}(b)r_c \lt c.$$
وهذا يعني أن \(\operatorname{rad}(a)\) يجب أن تكون صغيرة. لذلك ترتب التطبيقات جميع الأعداد الموجبة تحت الحد الأعلى بحسب \(\operatorname{rad}(n)\)، ثم تفحص لكل قيمة ثابتة من \(c\) مقدمة هذه القائمة فقط.
حد الإيقاف المستخدم في الكود هو
$$q=\left\lfloor \frac{c}{r_c}\right\rfloor.$$
بمجرد أن تصبح \(\operatorname{rad}(a)\ge q\)، يمكن إنهاء المسح الداخلي. إذا كانت \(\operatorname{rad}(a) \gt q\)، فلدينا بالفعل \(\operatorname{rad}(a)r_c \gt c\). وإذا كانت \(\operatorname{rad}(a)=q\)، فإما أن \(qr_c=c\)، وعندها تفشل المتباينة الصارمة فورا، أو أن \(qr_c \lt c \lt (q+1)r_c\). في الحالة الثانية يكون \(b \gt 1\)، ولذلك \(\operatorname{rad}(b)\ge 2\)، ومن ثم
$$\operatorname{rad}(a)\operatorname{rad}(b)r_c \ge 2qr_c \ge c.$$
إذن الإيقاف المبكر مبرهن رياضيا وليس حيلة تجريبية. ومع ذلك يبقى الشرط \(a \lt c/2\) ضروريا لأن الترتيب في القائمة مبني على radical وليس على قيمة العدد نفسه.
لنأخذ \(c=9\). عندئذ \(\operatorname{rad}(9)=3\)، وبالتالي
$$q=\left\lfloor \frac{9}{3}\right\rfloor=3.$$
إذن لا يمكن أن تنجح إلا القيم التي تحقق \(\operatorname{rad}(a) \lt 3\). ومع الشرط \(a \lt 9/2\) تبقى القيم \(a=1,2,4\).
عند \(a=1\) نحصل على \(b=8\)، ويكون
$$\operatorname{rad}(1)\operatorname{rad}(8)\operatorname{rad}(9)=1\cdot 2\cdot 3=6 \lt 9,$$
وكذلك \(\gcd(1,8)=1\). لذلك فإن \((1,8,9)\) يمثل abc-hit صحيحا.
أما عند \(a=2\)، فلدينا \(b=7\) ويصبح حاصل ضرب radicals مساويا \(2\cdot 7\cdot 3=42\). وعند \(a=4\)، يكون \(b=5\) والحاصل \(2\cdot 5\cdot 3=30\). كلاهما يفشل. هذا المثال الصغير يوضح تماما آلية الحل الكامل: قطع سريع باستخدام radical، ثم فحص دقيق للجداء ولقيمة gcd.
تتبع تطبيقات C++ وPython وJava الخطة نفسها على مرحلتين: أولا تحسب جميع radicals بكفاءة، ثم تمر على كل \(c\) ولا تفحص إلا القيم \(a\) ذات radical الصغيرة.
يبدأ التنفيذ بمصفوفة مملوءة بالقيمة 1. بعد ذلك يطبق منخلا للأعداد الأولية. كلما اكتشف عددا أوليا \(p\)، يضرب radical المخزنة عند كل مضاعف لـ \(p\) في \(p\) مرة واحدة فقط. بعد انتهاء هذه المرحلة، يحتوي كل موضع على حاصل ضرب العوامل الأولية المختلفة لذلك العدد.
ثم تبنى قائمة بالأعداد \(1,2,\dots,119{,}999\) مرتبة تصاعديا بحسب \(\operatorname{rad}(n)\)، ومع التعادل يستخدم العدد نفسه كفاصل. هذه القائمة المرتبة هي ما يجعل الإيقاف المبكر ممكنا في المرحلة التالية.
لكل \(c\) من 3 حتى \(119{,}999\)، يحسب التنفيذ \(r_c=\operatorname{rad}(c)\) و\(q=\lfloor c/r_c\rfloor\). بعد ذلك يسير عبر القائمة المرتبة مسبقا ويتوقف بمجرد أن تصل radical الخاصة بالمرشح إلى \(q\).
كل مرشح يجب أن ينجح بعد ذلك في ثلاثة مرشحات دقيقة: أولا الشرط \(a \lt c/2\)، ثم تعريف \(b=c-a\)، ثم التحقق من
$$\operatorname{rad}(a)\operatorname{rad}(b)\operatorname{rad}(c) \lt c$$
و
$$\gcd(a,b)=1.$$
إذا نجح الشرطان الأخيران، تضاف قيمة \(c\) الحالية إلى المجموع. ويتضمن أحد التطبيقات أيضا نقطة تحقق صغيرة: عندما يكون الحد المختزل هو \(c \lt 1000\)، فإن المجموع الجزئي يساوي \(12523\).
لنفرض أن \(N=120{,}000\). المنخل الذي يحسب جميع radicals يحتاج إلى \(O(N\log\log N)\)، أما ترتيب الأعداد بحسب radical فيحتاج إلى \(O(N\log N)\).
الكلفة الأساسية تأتي من مسح المرشحين. في أسوأ الحالات قد يترك حد القطع عددا كبيرا من العناصر، ولذلك تصل المرحلة الرئيسية إلى \(O(N^2)\) زيارة لمرشحين؛ وإذا كتبنا كلفة gcd صراحة أضفنا عاملا قدره \(O(\log N)\). عمليا يكون الأداء أفضل بكثير من مسح تربيعي كامل، لأن معظم قيم \(c\) تعطي نسبة \(c/\operatorname{rad}(c)\) صغيرة، فتتوقف الحلقة الداخلية المرتبة حسب radical بسرعة. استهلاك الذاكرة هو \(O(N)\).