We want the number of integers \(x\le n\) that have exactly eight positive divisors. For the target scale \(n=10^{12}\), testing each integer separately would be far too slow, so the solution classifies every valid number by its prime-factor pattern and turns the problem into a small set of prime-counting formulas.
Let
$$f(n)=\#\{x\in \mathbb{Z}_{>0}:x\le n,\ d(x)=8\},$$
where \(d(x)\) is the divisor-counting function. If
$$x=\prod_i p_i^{a_i},$$
then
$$d(x)=\prod_i (a_i+1).$$
So the entire problem is to find all exponent patterns whose contribution to \(d(x)\) is exactly \(8\), and then count how many numbers of each pattern lie below \(n\).
The multiplicative partitions of \(8\) are
$$8,\qquad 4\cdot 2,\qquad 2\cdot 2\cdot 2.$$
Therefore every integer with exactly eight divisors has one of the three mutually exclusive shapes
$$x=p^7,\qquad x=p^3q,\qquad x=pqr,$$
where \(p,q,r\) are primes, \(p\ne q\) in the middle case, and \(p\lt q\lt r\) in the last case. No other factorization type is possible, because any other exponent list would make \(\prod (a_i+1)\neq 8\).
Fix ordered primes \(p\lt q\lt r\) with
$$pqr\le n.$$
For a fixed pair \((p,q)\), the third prime must satisfy
$$q\lt r\le \left\lfloor\frac{n}{pq}\right\rfloor.$$
Hence the number of admissible \(r\) values is
$$\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q),$$
where \(\pi(x)\) is the prime-counting function. Also, once \(q^2>n/p\), even the smallest possible \(r\) is too large, so \(q\) only needs to run up to \(\left\lfloor\sqrt{n/p}\right\rfloor\). This gives
$$A(n)=\sum_{\substack{p\lt q\\ pq^2\le n}}\left(\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q)\right).$$
Now fix a prime \(p\). Any prime \(q\) with
$$q\le \left\lfloor\frac{n}{p^3}\right\rfloor$$
produces a candidate \(p^3q\le n\). If we temporarily ignore the restriction \(q\ne p\), the contribution from this \(p\) is simply \(\pi(\lfloor n/p^3\rfloor)\). Summing over all possible base primes yields the raw count
$$B_{\mathrm{raw}}(n)=\sum_{p\le \lfloor \sqrt[3]{n}\rfloor}\pi\!\left(\left\lfloor\frac{n}{p^3}\right\rfloor\right).$$
This is exactly the quantity the implementation accumulates before correcting the bad diagonal case.
The raw sum \(B_{\mathrm{raw}}(n)\) incorrectly includes the choice \(q=p\). That choice gives
$$p^3q=p^4,$$
and \(p^4\) has only
$$d(p^4)=5$$
divisors, not \(8\). This invalid term appears exactly when
$$p^4\le n,$$
so the number of bad terms is
$$\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right).$$
Therefore the correct count for the \(p^3q\) family is
$$B(n)=B_{\mathrm{raw}}(n)-\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right).$$
The remaining family is \(p^7\le n\), whose contribution is
$$C(n)=\pi\!\left(\left\lfloor n^{1/7}\right\rfloor\right).$$
Putting the three disjoint cases together, we obtain
$$\boxed{f(n)=A(n)+B(n)+C(n).}$$
For the \(pqr\) family, only \(p=2\) contributes. With \((p,q)=(2,3)\), we get
$$\pi\!\left(\left\lfloor\frac{100}{6}\right\rfloor\right)-\pi(3)=\pi(16)-\pi(3)=6-2=4,$$
corresponding to \(30,42,66,78\). With \((p,q)=(2,5)\), we get
$$\pi\!\left(\left\lfloor\frac{100}{10}\right\rfloor\right)-\pi(5)=\pi(10)-\pi(5)=4-3=1,$$
which gives \(70\). Hence
$$A(100)=5.$$
For the \(p^3q\) family, the raw count is
$$B_{\mathrm{raw}}(100)=\pi(12)+\pi(3)=5+2=7.$$
The invalid choices \(q=p\) are counted by
$$\pi\!\left(\left\lfloor 100^{1/4}\right\rfloor\right)=\pi(3)=2,$$
so
$$B(100)=7-2=5.$$
These five numbers are \(24,40,54,56,88\). Finally, \(100\lt 2^7\), so
$$C(100)=0.$$
Therefore
$$f(100)=5+5+0=10,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations first compute exact integer square, cube, and seventh roots, with small corrective adjustments so every boundary case is handled safely. They then sieve all primes up to \(\lfloor\sqrt{n}\rfloor\). That range is enough for explicit iteration, because every prime that appears in the outer loops lies at most in that interval.
Next, the implementation builds a combinatorial prime-counting structure on two domains: direct arguments up to \(\sqrt{n}\), and quotient arguments of the form \(\lfloor n/i\rfloor\). After a prime-by-prime update pass, this structure can answer every needed value of \(\pi(x)\) in constant time.
With those prime counts available, the implementation evaluates the same three contributions as the mathematics: prime pairs for the \(pqr\) family, the raw sum for \(p^3q\), the subtraction of the forbidden \(p^4\) terms, and finally the \(p^7\) contribution. The sum of those parts is the final answer.
Let \(v=\lfloor\sqrt{n}\rfloor\). The sieve and the prime-counting preprocessing use \(O(v)\) memory and about \(O(v\log\log v)\) arithmetic on the explicitly sieved range. The \(p^3q\) stage iterates over primes \(p\le n^{1/3}\), so it requires only \(O(\pi(n^{1/3}))\) prime-count queries.
The dominant work is the \(pqr\) stage, which visits each prime pair \((p,q)\) satisfying \(p\lt q\) and \(pq^2\le n\). Its loop count is
$$O\!\left(\sum_{p\le n^{1/3}}\pi\!\left(\sqrt{\frac{n}{p}}\right)\right),$$
and each visit performs only \(O(1)\) table lookups. In practice this is vastly smaller than scanning all integers up to \(n\), and it is easily fast enough for \(n=10^{12}\).
Gesucht ist die Anzahl der ganzen Zahlen \(x\le n\), die genau acht positive Teiler besitzen. Für die Zielgröße \(n=10^{12}\) wäre es viel zu langsam, jede Zahl einzeln zu testen. Deshalb klassifiziert die Lösung alle gültigen Zahlen nach ihrer Primfaktorstruktur und reduziert das Problem auf einige wenige Abfragen der Primzahlzählfunktion.
Sei
$$f(n)=\#\{x\in \mathbb{Z}_{>0}:x\le n,\ d(x)=8\},$$
wobei \(d(x)\) die Teilerfunktion ist. Für
$$x=\prod_i p_i^{a_i}$$
gilt
$$d(x)=\prod_i (a_i+1).$$
Damit müssen wir nur diejenigen Exponentenmuster betrachten, deren Produkt der Faktoren \((a_i+1)\) genau \(8\) ergibt.
Die multiplikativen Zerlegungen von \(8\) sind
$$8,\qquad 4\cdot 2,\qquad 2\cdot 2\cdot 2.$$
Daraus folgen genau drei, paarweise disjunkte Formen:
$$x=p^7,\qquad x=p^3q,\qquad x=pqr,$$
wobei \(p,q,r\) Primzahlen sind, im mittleren Fall \(p\ne q\) gilt und im letzten Fall \(p\lt q\lt r\). Eine andere Struktur ist unmöglich, weil dann \(\prod (a_i+1)\neq 8\) wäre.
Fixiere Primzahlen \(p\lt q\lt r\) mit
$$pqr\le n.$$
Für ein festes Paar \((p,q)\) muss die dritte Primzahl die Bedingung
$$q\lt r\le \left\lfloor\frac{n}{pq}\right\rfloor$$
erfüllen. Also ist die Anzahl zulässiger \(r\)
$$\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q),$$
wobei \(\pi(x)\) die Anzahl der Primzahlen \(\le x\) bezeichnet. Sobald \(q^2>n/p\) gilt, ist sogar das kleinste mögliche \(r\) schon zu groß. Deshalb reicht es, \(q\) nur bis \(\left\lfloor\sqrt{n/p}\right\rfloor\) laufen zu lassen. Damit erhält man
$$A(n)=\sum_{\substack{p\lt q\\ pq^2\le n}}\left(\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q)\right).$$
Fixiere nun eine Primzahl \(p\). Jede Primzahl \(q\) mit
$$q\le \left\lfloor\frac{n}{p^3}\right\rfloor$$
liefert zunächst einen Kandidaten \(p^3q\le n\). Ignoriert man vorübergehend die Bedingung \(q\ne p\), so ist der Beitrag dieses \(p\) einfach \(\pi(\lfloor n/p^3\rfloor)\). Summiert über alle möglichen \(p\), ergibt das den Rohwert
$$B_{\mathrm{raw}}(n)=\sum_{p\le \lfloor \sqrt[3]{n}\rfloor}\pi\!\left(\left\lfloor\frac{n}{p^3}\right\rfloor\right).$$
Genau diesen Ausdruck akkumuliert die Implementierung vor der Korrektur des verbotenen Diagonalfalls.
Im Rohwert \(B_{\mathrm{raw}}(n)\) steckt fälschlich auch der Fall \(q=p\). Dann entsteht
$$p^3q=p^4,$$
und \(p^4\) besitzt nur
$$d(p^4)=5$$
Teiler statt \(8\). Dieser ungültige Fall tritt genau dann auf, wenn
$$p^4\le n,$$
also gibt es
$$\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right)$$
solche Fehlzählungen. Somit ist
$$B(n)=B_{\mathrm{raw}}(n)-\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right).$$
Die verbleibende Familie \(p^7\le n\) trägt
$$C(n)=\pi\!\left(\left\lfloor n^{1/7}\right\rfloor\right)$$
bei. Insgesamt folgt daher
$$\boxed{f(n)=A(n)+B(n)+C(n).}$$
Für die Familie \(pqr\) trägt nur \(p=2\) bei. Für \((p,q)=(2,3)\) erhält man
$$\pi\!\left(\left\lfloor\frac{100}{6}\right\rfloor\right)-\pi(3)=\pi(16)-\pi(3)=6-2=4,$$
also \(30,42,66,78\). Für \((p,q)=(2,5)\) ergibt sich
$$\pi\!\left(\left\lfloor\frac{100}{10}\right\rfloor\right)-\pi(5)=\pi(10)-\pi(5)=4-3=1,$$
nämlich \(70\). Daher
$$A(100)=5.$$
Für die Familie \(p^3q\) ist der Rohwert
$$B_{\mathrm{raw}}(100)=\pi(12)+\pi(3)=5+2=7.$$
Die verbotenen Fälle \(q=p\) werden gezählt durch
$$\pi\!\left(\left\lfloor 100^{1/4}\right\rfloor\right)=\pi(3)=2,$$
also
$$B(100)=7-2=5.$$
Die fünf gültigen Zahlen sind \(24,40,54,56,88\). Schließlich gilt \(100\lt 2^7\), also
$$C(100)=0.$$
Damit folgt
$$f(100)=5+5+0=10,$$
genau wie im Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen berechnen zuerst exakte ganzzahlige Quadrat-, Kubik- und siebte Wurzeln und korrigieren eventuelle Rundungsfehler direkt an der Grenze. Danach werden alle Primzahlen bis \(\lfloor\sqrt{n}\rfloor\) gesiebt. Mehr wird für die expliziten Schleifen nicht benötigt, weil jede dort verwendete Primzahl höchstens in diesem Bereich liegt.
Anschließend baut die Implementierung eine kombinatorische Struktur für Primzahlzählungen auf zwei Bereichen auf: direkte Argumente bis \(\sqrt{n}\) und Quotientenwerte der Form \(\lfloor n/i\rfloor\). Nach einer primeweisen Aktualisierung liefert diese Struktur alle benötigten Werte von \(\pi(x)\) in konstanter Zeit.
Mit diesen Primzahlzählungen werden dann genau die drei mathematischen Beiträge ausgewertet: zuerst die Primzahlpaare für den Fall \(pqr\), danach die Rohsumme für \(p^3q\), anschließend die Subtraktion der unerlaubten \(p^4\)-Fälle und zuletzt der Beitrag der Form \(p^7\). Ihre Summe ist die gesuchte Antwort.
Sei \(v=\lfloor\sqrt{n}\rfloor\). Sieb und Vorverarbeitung der Primzahlzählung benötigen \(O(v)\) Speicher und ungefähr \(O(v\log\log v)\) Rechenarbeit auf dem explizit gesiebten Bereich. Die Phase für \(p^3q\) läuft nur über Primzahlen \(p\le n^{1/3}\) und benötigt daher \(O(\pi(n^{1/3}))\) Abfragen der Primzahlzählfunktion.
Der dominierende Teil ist die Phase für \(pqr\), die jedes Primzahlpaar \((p,q)\) mit \(p\lt q\) und \(pq^2\le n\) besucht. Die Anzahl der Iterationen ist
$$O\!\left(\sum_{p\le n^{1/3}}\pi\!\left(\sqrt{\frac{n}{p}}\right)\right),$$
wobei jeder Schritt nur \(O(1)\)-Tabellenzugriffe braucht. Praktisch ist das um Größenordnungen kleiner als ein vollständiger Scan aller Zahlen bis \(n\) und für \(n=10^{12}\) problemlos schnell genug.
Aranan şey, \(x\le n\) koşulunu sağlayan ve tam olarak sekiz pozitif böleni olan sayıların adedidir. Hedef büyüklük \(n=10^{12}\) olduğundan her sayıyı tek tek incelemek çok yavaştır. Bu yüzden çözüm, geçerli sayıları asal çarpan yapılarına göre sınıflandırır ve sayımı birkaç asal sayma formülüne indirger.
Şunu tanımlayalım:
$$f(n)=\#\{x\in \mathbb{Z}_{>0}:x\le n,\ d(x)=8\},$$
burada \(d(x)\) bölen sayısı fonksiyonudur. Eğer
$$x=\prod_i p_i^{a_i}$$
ise
$$d(x)=\prod_i (a_i+1)$$
olur. Dolayısıyla yalnızca \((a_i+1)\) çarpımının tam olarak \(8\) verdiği üs desenlerini incelememiz gerekir.
\(8\)'in çarpımsal ayrışımları
$$8,\qquad 4\cdot 2,\qquad 2\cdot 2\cdot 2$$
şeklindedir. Bu nedenle tam olarak sekiz böleni olan her sayı, birbirini dışlayan şu üç biçimden birine sahiptir:
$$x=p^7,\qquad x=p^3q,\qquad x=pqr,$$
burada \(p,q,r\) asaldır, orta durumda \(p\ne q\), son durumda ise \(p\lt q\lt r\) kabul edilir. Başka bir asal üs düzeni mümkün değildir; çünkü o zaman \(\prod (a_i+1)\neq 8\) olur.
\(p\lt q\lt r\) ve
$$pqr\le n$$
olsun. Sabit bir \((p,q)\) çifti için üçüncü asalın
$$q\lt r\le \left\lfloor\frac{n}{pq}\right\rfloor$$
koşulunu sağlaması gerekir. Dolayısıyla uygun \(r\) sayısı
$$\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q)$$
olur; burada \(\pi(x)\), \(x\)'e kadar olan asal sayıları sayar. Ayrıca \(q^2>n/p\) olduğunda en küçük mümkün \(r\) bile fazla büyük kalır. Bu yüzden \(q\) yalnızca \(\left\lfloor\sqrt{n/p}\right\rfloor\) değerine kadar dolaşmalıdır. Böylece
$$A(n)=\sum_{\substack{p\lt q\\ pq^2\le n}}\left(\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q)\right)$$
elde edilir.
Şimdi bir asal \(p\) sabitleyelim. Eğer
$$q\le \left\lfloor\frac{n}{p^3}\right\rfloor$$
ise her asal \(q\), \(p^3q\le n\) biçiminde bir aday üretir. Geçici olarak \(q\ne p\) şartını görmezden gelirsek, bu \(p\) için katkı doğrudan \(\pi(\lfloor n/p^3\rfloor)\) olur. Tüm uygun \(p\) değerleri üzerinde toplarsak ham sayıma ulaşırız:
$$B_{\mathrm{raw}}(n)=\sum_{p\le \lfloor \sqrt[3]{n}\rfloor}\pi\!\left(\left\lfloor\frac{n}{p^3}\right\rfloor\right).$$
Uygulama, yasak çapraz durumu düzeltmeden önce tam olarak bu toplamı biriktirir.
Ham toplam \(B_{\mathrm{raw}}(n)\), yanlışlıkla \(q=p\) seçimini de içerir. Bu durumda
$$p^3q=p^4$$
olur ve \(p^4\) sayısının bölen sayısı
$$d(p^4)=5$$
olduğu için bu terim geçersizdir. Bu hatalı durum tam olarak
$$p^4\le n$$
iken ortaya çıkar; yani çıkarılması gereken terim sayısı
$$\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right)$$
kadardır. Dolayısıyla doğru \(p^3q\) sayımı
$$B(n)=B_{\mathrm{raw}}(n)-\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right)$$
olur. Kalan son aile \(p^7\le n\) olup katkısı
$$C(n)=\pi\!\left(\left\lfloor n^{1/7}\right\rfloor\right)$$
şeklindedir. Böylece
$$\boxed{f(n)=A(n)+B(n)+C(n)}$$
elde edilir.
\(pqr\) ailesinde yalnızca \(p=2\) katkı verir. \((p,q)=(2,3)\) için
$$\pi\!\left(\left\lfloor\frac{100}{6}\right\rfloor\right)-\pi(3)=\pi(16)-\pi(3)=6-2=4$$
olur; bunlar \(30,42,66,78\) sayılarıdır. \((p,q)=(2,5)\) için
$$\pi\!\left(\left\lfloor\frac{100}{10}\right\rfloor\right)-\pi(5)=\pi(10)-\pi(5)=4-3=1$$
elde edilir; bu da \(70\)'tir. Demek ki
$$A(100)=5.$$
\(p^3q\) ailesi için ham toplam
$$B_{\mathrm{raw}}(100)=\pi(12)+\pi(3)=5+2=7$$
olur. Hatalı \(q=p\) seçimleri
$$\pi\!\left(\left\lfloor 100^{1/4}\right\rfloor\right)=\pi(3)=2$$
ile sayılır; dolayısıyla
$$B(100)=7-2=5.$$
Bu beş sayı \(24,40,54,56,88\)'dir. Son olarak \(100\lt 2^7\) olduğundan
$$C(100)=0.$$
Böylece
$$f(100)=5+5+0=10$$
bulunur; bu da uygulamadaki kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları önce tam sayı karekök, küpkök ve yedinci kök sınırlarını güvenli biçimde hesaplar; kayan nokta yuvarlama hataları varsa küçük düzeltmelerle giderilir. Ardından \(\lfloor\sqrt{n}\rfloor\) değerine kadar asal sayılar süzülür. Açıkça dolaşılan tüm asallar bu aralıkta olduğu için bu yeterlidir.
Daha sonra uygulama iki bölgeli birleşik bir asal sayma yapısı kurar: biri doğrudan \(\sqrt{n}\)'ye kadar olan argümanlar için, diğeri \(\lfloor n/i\rfloor\) biçimindeki bölüm değerleri için. Asal asal güncellenen bir ön işleme sonunda, ihtiyaç duyulan tüm \(\pi(x)\) değerleri sabit zamanda elde edilir.
Bu hazır olduktan sonra uygulama, matematikteki üç katkıyı aynı sırayla toplar: önce \(pqr\) ailesi için asal çiftleri, sonra \(p^3q\) için ham toplam, ardından geçersiz \(p^4\) terimlerinin çıkarılması ve son olarak \(p^7\) katkısı. Bu parçaların toplamı nihai cevaptır.
\(v=\lfloor\sqrt{n}\rfloor\) olsun. Süzgeç ve asal sayma ön işleme adımı \(O(v)\) bellek kullanır ve açıkça süzülen aralık üzerinde yaklaşık \(O(v\log\log v)\) işlem yapar. \(p^3q\) aşaması yalnızca \(p\le n^{1/3}\) asalları üzerinde dolaştığı için \(O(\pi(n^{1/3}))\) adet asal sayma sorgusu gerektirir.
Baskın maliyet \(pqr\) aşamasındadır. Bu kısım, \(p\lt q\) ve \(pq^2\le n\) koşulunu sağlayan her asal çifti ziyaret eder. Döngü sayısı
$$O\!\left(\sum_{p\le n^{1/3}}\pi\!\left(\sqrt{\frac{n}{p}}\right)\right)$$
mertebesindedir ve her adım yalnızca \(O(1)\) tablo erişimi yapar. Pratikte bu, \(n\)'ye kadar tüm sayıları taramaktan çok daha küçüktür ve \(n=10^{12}\) için rahatlıkla yeterince hızlıdır.
Queremos contar los enteros \(x\le n\) que tienen exactamente ocho divisores positivos. Para el tamaño objetivo \(n=10^{12}\), comprobar cada número por separado sería demasiado lento. Por eso la solución clasifica todos los casos válidos según su estructura de factores primos y convierte el problema en unas pocas fórmulas con la función contadora de primos.
Definimos
$$f(n)=\#\{x\in \mathbb{Z}_{>0}:x\le n,\ d(x)=8\},$$
donde \(d(x)\) es la función número de divisores. Si
$$x=\prod_i p_i^{a_i},$$
entonces
$$d(x)=\prod_i (a_i+1).$$
Así, todo el problema consiste en encontrar los patrones de exponentes para los cuales el producto de los términos \((a_i+1)\) vale exactamente \(8\).
Las particiones multiplicativas de \(8\) son
$$8,\qquad 4\cdot 2,\qquad 2\cdot 2\cdot 2.$$
Por tanto, todo entero con exactamente ocho divisores tiene una de estas tres formas, mutuamente excluyentes:
$$x=p^7,\qquad x=p^3q,\qquad x=pqr,$$
donde \(p,q,r\) son primos, en el caso intermedio \(p\ne q\), y en el último caso \(p\lt q\lt r\). Ninguna otra estructura es posible, porque entonces \(\prod (a_i+1)\neq 8\).
Supongamos \(p\lt q\lt r\) y
$$pqr\le n.$$
Para un par fijo \((p,q)\), el tercer primo debe cumplir
$$q\lt r\le \left\lfloor\frac{n}{pq}\right\rfloor.$$
Entonces el número de valores posibles de \(r\) es
$$\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q),$$
donde \(\pi(x)\) cuenta los primos hasta \(x\). Además, cuando \(q^2>n/p\), ni siquiera el menor \(r\) permitido cabe ya en el producto. Por eso basta recorrer \(q\) hasta \(\left\lfloor\sqrt{n/p}\right\rfloor\). Así obtenemos
$$A(n)=\sum_{\substack{p\lt q\\ pq^2\le n}}\left(\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q)\right).$$
Ahora fijemos un primo \(p\). Todo primo \(q\) que satisfaga
$$q\le \left\lfloor\frac{n}{p^3}\right\rfloor$$
produce un candidato \(p^3q\le n\). Si ignoramos momentáneamente la restricción \(q\ne p\), la contribución de ese \(p\) es simplemente \(\pi(\lfloor n/p^3\rfloor)\). Sumando sobre todos los \(p\) posibles se obtiene el conteo bruto
$$B_{\mathrm{raw}}(n)=\sum_{p\le \lfloor \sqrt[3]{n}\rfloor}\pi\!\left(\left\lfloor\frac{n}{p^3}\right\rfloor\right).$$
Ese es exactamente el valor que la implementación acumula antes de corregir el caso diagonal prohibido.
La suma bruta \(B_{\mathrm{raw}}(n)\) incluye indebidamente el caso \(q=p\). En ese caso aparece
$$p^3q=p^4,$$
y \(p^4\) tiene solamente
$$d(p^4)=5$$
divisores, no \(8\). El término inválido aparece exactamente cuando
$$p^4\le n,$$
de modo que el número de sobrecuentas es
$$\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right).$$
Por tanto, el conteo correcto de la familia \(p^3q\) es
$$B(n)=B_{\mathrm{raw}}(n)-\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right).$$
La familia restante es \(p^7\le n\), que aporta
$$C(n)=\pi\!\left(\left\lfloor n^{1/7}\right\rfloor\right).$$
Juntando los tres casos disjuntos, queda
$$\boxed{f(n)=A(n)+B(n)+C(n).}$$
En la familia \(pqr\), solo contribuye \(p=2\). Para \((p,q)=(2,3)\) obtenemos
$$\pi\!\left(\left\lfloor\frac{100}{6}\right\rfloor\right)-\pi(3)=\pi(16)-\pi(3)=6-2=4,$$
que corresponden a \(30,42,66,78\). Para \((p,q)=(2,5)\) se obtiene
$$\pi\!\left(\left\lfloor\frac{100}{10}\right\rfloor\right)-\pi(5)=\pi(10)-\pi(5)=4-3=1,$$
es decir, \(70\). Por tanto,
$$A(100)=5.$$
En la familia \(p^3q\), el conteo bruto es
$$B_{\mathrm{raw}}(100)=\pi(12)+\pi(3)=5+2=7.$$
Los casos inválidos con \(q=p\) están dados por
$$\pi\!\left(\left\lfloor 100^{1/4}\right\rfloor\right)=\pi(3)=2,$$
así que
$$B(100)=7-2=5.$$
Esos cinco números son \(24,40,54,56,88\). Finalmente, como \(100\lt 2^7\), tenemos
$$C(100)=0.$$
En consecuencia,
$$f(100)=5+5+0=10,$$
lo que coincide con el valor de comprobación usado por la implementación.
Las implementaciones en C++, Python y Java calculan primero raíces entera cuadrada, cúbica y séptima, ajustando después los límites para que no haya errores en los bordes. Luego generan todos los primos hasta \(\lfloor\sqrt{n}\rfloor\). Ese rango basta para la iteración explícita, porque todos los primos que aparecen en los bucles exteriores están en ese intervalo.
Después, la implementación construye una estructura combinatoria de conteo de primos sobre dos dominios: argumentos directos hasta \(\sqrt{n}\) y valores cociente de la forma \(\lfloor n/i\rfloor\). Tras una fase de actualización primo a primo, esa estructura puede responder cada \(\pi(x)\) necesario en tiempo constante.
Con esos conteos disponibles, la implementación suma los mismos tres aportes de la derivación matemática: primero los pares \((p,q)\) para la familia \(pqr\), luego la suma bruta de \(p^3q\), después la resta de los términos prohibidos \(p^4\), y por último la contribución de \(p^7\). La suma de esas piezas es la respuesta final.
Sea \(v=\lfloor\sqrt{n}\rfloor\). La criba y el preprocesamiento para contar primos usan \(O(v)\) memoria y alrededor de \(O(v\log\log v)\) trabajo aritmético sobre el rango cribado explícitamente. La fase \(p^3q\) recorre solo los primos \(p\le n^{1/3}\), así que requiere \(O(\pi(n^{1/3}))\) consultas a la función contadora de primos.
La parte dominante es la fase \(pqr\), que visita cada par de primos \((p,q)\) con \(p\lt q\) y \(pq^2\le n\). Su número de iteraciones es
$$O\!\left(\sum_{p\le n^{1/3}}\pi\!\left(\sqrt{\frac{n}{p}}\right)\right),$$
y cada iteración hace solo accesos \(O(1)\) a tablas. En la práctica esto es muchísimo menor que examinar todos los enteros hasta \(n\), y resulta plenamente adecuado para \(n=10^{12}\).
我们要求的是满足 \(x\le n\) 且恰好有八个正因子的整数个数。对于目标规模 \(n=10^{12}\)，逐个整数分解并统计因子显然过慢，因此解法不是直接暴力，而是先把所有合法数按素因子结构分类，再把每一类转化为少量的素数计数问题。
记
$$f(n)=\#\{x\in \mathbb{Z}_{>0}:x\le n,\ d(x)=8\},$$
其中 \(d(x)\) 表示 \(x\) 的正因子个数。如果
$$x=\prod_i p_i^{a_i},$$
那么有
$$d(x)=\prod_i (a_i+1).$$
因此，这道题的核心不是“枚举所有 \(x\)”，而是找出哪些指数模式会让 \(\prod_i(a_i+1)=8\)，然后分别统计这些模式在 \(n\) 以内出现多少次。
\(8\) 的乘法拆分只有三种：
$$8,\qquad 4\cdot 2,\qquad 2\cdot 2\cdot 2.$$
所以，恰有八个因子的整数只能是以下三种互不重叠的形式：
$$x=p^7,\qquad x=p^3q,\qquad x=pqr,$$
其中 \(p,q,r\) 都是素数，中间这一类要求 \(p\ne q\)，最后一类为了避免重复计数约定 \(p\lt q\lt r\)。除此之外不可能再有别的形式，因为一旦指数模式不同，\(\prod_i(a_i+1)\) 就不会等于 \(8\)。
设 \(p\lt q\lt r\)，并且
$$pqr\le n.$$
如果固定前两个素数 \(p,q\)，那么第三个素数必须满足
$$q\lt r\le \left\lfloor\frac{n}{pq}\right\rfloor.$$
因此，对这个固定的 \((p,q)\)，可选的 \(r\) 个数就是
$$\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q),$$
这里 \(\pi(x)\) 表示不超过 \(x\) 的素数个数。另一方面，一旦 \(q^2>n/p\)，那么最小可能的 \(r\) 也已经过大，因此 \(q\) 只需要枚举到 \(\left\lfloor\sqrt{n/p}\right\rfloor\)。于是这部分可以写成
$$A(n)=\sum_{\substack{p\lt q\\ pq^2\le n}}\left(\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q)\right).$$
这正是实现中双层素数循环所对应的数学表达式。
现在固定一个素数 \(p\)。只要素数 \(q\) 满足
$$q\le \left\lfloor\frac{n}{p^3}\right\rfloor,$$
就会得到一个候选数 \(p^3q\le n\)。如果先暂时忽略 \(q\ne p\) 这个限制，那么对于固定的 \(p\)，贡献就是 \(\pi(\lfloor n/p^3\rfloor)\)。把所有可能的 \(p\) 加起来，得到一个“原始计数”：
$$B_{\mathrm{raw}}(n)=\sum_{p\le \lfloor \sqrt[3]{n}\rfloor}\pi\!\left(\left\lfloor\frac{n}{p^3}\right\rfloor\right).$$
程序会先累加这个原始值，因为它很容易通过素数计数函数快速获得。
问题在于，\(B_{\mathrm{raw}}(n)\) 把 \(q=p\) 的情况也算进去了。此时
$$p^3q=p^4,$$
而 \(p^4\) 的因子个数只有
$$d(p^4)=5,$$
并不是 \(8\)。这类错误项出现的充要条件是
$$p^4\le n,$$
所以错误项的个数恰好是
$$\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right).$$
因此，真正的 \(p^3q\) 计数应为
$$B(n)=B_{\mathrm{raw}}(n)-\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right).$$
剩下的最后一类是
$$p^7\le n,$$
它的贡献直接就是
$$C(n)=\pi\!\left(\left\lfloor n^{1/7}\right\rfloor\right).$$
三类互不重叠，所以总答案为
$$\boxed{f(n)=A(n)+B(n)+C(n).}$$
先看 \(pqr\) 这一类。这里只有 \(p=2\) 会产生贡献。对 \((p,q)=(2,3)\)，有
$$\pi\!\left(\left\lfloor\frac{100}{6}\right\rfloor\right)-\pi(3)=\pi(16)-\pi(3)=6-2=4,$$
对应的数是 \(30,42,66,78\)。对 \((p,q)=(2,5)\)，有
$$\pi\!\left(\left\lfloor\frac{100}{10}\right\rfloor\right)-\pi(5)=\pi(10)-\pi(5)=4-3=1,$$
对应的数是 \(70\)。所以
$$A(100)=5.$$
再看 \(p^3q\) 这一类，原始计数为
$$B_{\mathrm{raw}}(100)=\pi(12)+\pi(3)=5+2=7.$$
其中错误的 \(q=p\) 项由
$$\pi\!\left(\left\lfloor 100^{1/4}\right\rfloor\right)=\pi(3)=2$$
给出，因此
$$B(100)=7-2=5.$$
这五个合法数是 \(24,40,54,56,88\)。最后，\(100\lt 2^7\)，所以
$$C(100)=0.$$
总数就是
$$f(100)=5+5+0=10,$$
与实现中的校验结果完全一致。
C++、Python 和 Java 实现首先都会求出精确的整数平方根、立方根和七次根，并在浮点近似后做边界修正，保证像 \(p^7\le n\) 这样的临界判断不会出错。随后，程序筛出所有不超过 \(\lfloor\sqrt{n}\rfloor\) 的素数。对于外层显式枚举来说，这个范围已经足够。
接着，实现会建立一个组合式的素数计数结构，覆盖两个参数域：一类是直接参数 \(x\le \sqrt{n}\)，另一类是商值 \(\lfloor n/i\rfloor\)。经过按素数逐步更新后，这个结构就能在常数时间内返回所需的 \(\pi(x)\) 值。
有了这些素数计数以后，程序就严格按照上面的数学拆分来求和：先处理 \(pqr\) 的双层素数对，再累加 \(p^3q\) 的原始计数，然后减去非法的 \(p^4\) 项，最后补上 \(p^7\) 的贡献。四个部分相加就是最终答案。
令 \(v=\lfloor\sqrt{n}\rfloor\)。筛法和素数计数预处理占用 \(O(v)\) 空间，并在显式筛分的范围上做大约 \(O(v\log\log v)\) 级别的运算。\(p^3q\) 这一部分只需要遍历满足 \(p\le n^{1/3}\) 的素数，因此只会产生 \(O(\pi(n^{1/3}))\) 次素数计数查询。
主要开销来自 \(pqr\) 这一部分。它会访问所有满足 \(p\lt q\) 且 \(pq^2\le n\) 的素数对 \((p,q)\)。循环次数可以写成
$$O\!\left(\sum_{p\le n^{1/3}}\pi\!\left(\sqrt{\frac{n}{p}}\right)\right),$$
而每次循环内部只做 \(O(1)\) 次表查询。与直接扫描 \(1\) 到 \(n\) 的所有整数相比，这个复杂度小得多，对于 \(n=10^{12}\) 完全可行。
Нужно посчитать количество целых чисел \(x\le n\), имеющих ровно восемь положительных делителей. При целевом масштабе \(n=10^{12}\) проверять каждое число отдельно слишком дорого, поэтому решение сначала классифицирует все допустимые числа по их простой факторизации, а затем сводит подсчет к нескольким формулам с функцией \(\pi(x)\).
Обозначим
$$f(n)=\#\{x\in \mathbb{Z}_{>0}:x\le n,\ d(x)=8\},$$
где \(d(x)\) есть функция числа делителей. Если
$$x=\prod_i p_i^{a_i},$$
то
$$d(x)=\prod_i (a_i+1).$$
Значит, нужно найти все наборы показателей, для которых произведение \((a_i+1)\) равно \(8\), и отдельно посчитать вклад каждого возможного типа.
Мультипликативные разбиения числа \(8\) имеют вид
$$8,\qquad 4\cdot 2,\qquad 2\cdot 2\cdot 2.$$
Отсюда следует, что число с ровно восемью делителями может иметь только одну из трех непересекающихся форм:
$$x=p^7,\qquad x=p^3q,\qquad x=pqr,$$
где \(p,q,r\) — простые числа, в среднем случае \(p\ne q\), а в последнем случае для исключения повторов принимается \(p\lt q\lt r\). Других вариантов нет, потому что иначе произведение \(\prod (a_i+1)\) не было бы равно \(8\).
Пусть \(p\lt q\lt r\) и
$$pqr\le n.$$
Если фиксировать пару \((p,q)\), то третий простой должен удовлетворять
$$q\lt r\le \left\lfloor\frac{n}{pq}\right\rfloor.$$
Следовательно, число допустимых \(r\) равно
$$\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q),$$
где \(\pi(x)\) — количество простых чисел, не превосходящих \(x\). Кроме того, как только \(q^2>n/p\), даже минимально возможный \(r\) уже слишком велик. Поэтому \(q\) достаточно перебирать только до \(\left\lfloor\sqrt{n/p}\right\rfloor\). Получаем формулу
$$A(n)=\sum_{\substack{p\lt q\\ pq^2\le n}}\left(\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q)\right).$$
Теперь зафиксируем простой \(p\). Любой простой \(q\), для которого
$$q\le \left\lfloor\frac{n}{p^3}\right\rfloor,$$
дает кандидат \(p^3q\le n\). Если временно не учитывать условие \(q\ne p\), вклад этого \(p\) равен \(\pi(\lfloor n/p^3\rfloor)\). Суммируя по всем возможным \(p\), получаем грубый подсчет
$$B_{\mathrm{raw}}(n)=\sum_{p\le \lfloor \sqrt[3]{n}\rfloor}\pi\!\left(\left\lfloor\frac{n}{p^3}\right\rfloor\right).$$
Именно эту величину программа сначала накапливает, а уже потом исправляет лишний счет.
Проблема в том, что \(B_{\mathrm{raw}}(n)\) ошибочно включает случай \(q=p\). Тогда получается
$$p^3q=p^4,$$
а у числа \(p^4\) только
$$d(p^4)=5$$
делителей вместо восьми. Такой неверный вклад возникает в точности при
$$p^4\le n,$$
поэтому число ошибочных членов равно
$$\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right).$$
Следовательно, правильный вклад семейства \(p^3q\) равен
$$B(n)=B_{\mathrm{raw}}(n)-\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right).$$
Остается семейство \(p^7\le n\), дающее вклад
$$C(n)=\pi\!\left(\left\lfloor n^{1/7}\right\rfloor\right).$$
Так как все три класса не пересекаются, итоговая формула имеет вид
$$\boxed{f(n)=A(n)+B(n)+C(n).}$$
Для семейства \(pqr\) вклад дает только \(p=2\). При \((p,q)=(2,3)\) имеем
$$\pi\!\left(\left\lfloor\frac{100}{6}\right\rfloor\right)-\pi(3)=\pi(16)-\pi(3)=6-2=4,$$
что соответствует числам \(30,42,66,78\). При \((p,q)=(2,5)\) получаем
$$\pi\!\left(\left\lfloor\frac{100}{10}\right\rfloor\right)-\pi(5)=\pi(10)-\pi(5)=4-3=1,$$
то есть число \(70\). Значит,
$$A(100)=5.$$
Для семейства \(p^3q\) грубый подсчет равен
$$B_{\mathrm{raw}}(100)=\pi(12)+\pi(3)=5+2=7.$$
Лишние случаи \(q=p\) считаются формулой
$$\pi\!\left(\left\lfloor 100^{1/4}\right\rfloor\right)=\pi(3)=2,$$
поэтому
$$B(100)=7-2=5.$$
Эти пять чисел равны \(24,40,54,56,88\). Наконец, \(100\lt 2^7\), значит
$$C(100)=0.$$
Итак,
$$f(100)=5+5+0=10,$$
что совпадает с контрольным значением в реализации.
Реализации на C++, Python и Java сначала вычисляют точные целочисленные квадратный, кубический и седьмой корни, а затем подправляют граничные случаи, чтобы избежать ошибок округления. После этого строится решето всех простых до \(\lfloor\sqrt{n}\rfloor\). Этого достаточно для явных циклов, потому что все простые, которые реально перебираются, лежат именно в этом диапазоне.
Затем реализация строит комбинаторную структуру для подсчета простых на двух областях аргументов: прямые значения до \(\sqrt{n}\) и значения частного вида \(\lfloor n/i\rfloor\). После последовательного обновления по простым эта структура позволяет получать любой нужный \(\pi(x)\) за \(O(1)\).
Далее программа в точности реализует математическое разбиение: сначала считает вклад всех пар \((p,q)\) для семейства \(pqr\), потом суммирует сырой вклад семейства \(p^3q\), затем вычитает запрещенные члены \(p^4\) и, наконец, добавляет вклад чисел вида \(p^7\). Их сумма и есть ответ.
Пусть \(v=\lfloor\sqrt{n}\rfloor\). Решето и предварительная обработка для функции \(\pi(x)\) используют \(O(v)\) памяти и порядка \(O(v\log\log v)\) операций на явно просеиваемом диапазоне. Этап \(p^3q\) перебирает только простые \(p\le n^{1/3}\), поэтому требует лишь \(O(\pi(n^{1/3}))\) запросов к функции подсчета простых.
Основная стоимость приходится на этап \(pqr\), который посещает каждую пару простых \((p,q)\), удовлетворяющую условиям \(p\lt q\) и \(pq^2\le n\). Число итераций имеет вид
$$O\!\left(\sum_{p\le n^{1/3}}\pi\!\left(\sqrt{\frac{n}{p}}\right)\right),$$
и каждая итерация делает только \(O(1)\) обращений к таблицам. На практике это на порядки меньше, чем полный просмотр всех чисел до \(n\), и вполне достаточно для \(n=10^{12}\).
نريد عدّ جميع الأعداد الصحيحة \(x\le n\) التي لها بالضبط ثمانية قواسم موجبة. وعند الحجم المستهدف \(n=10^{12}\) يصبح فحص كل عدد على حدة بطيئًا جدًا، لذلك لا تعتمد الفكرة على العدّ المباشر، بل على تصنيف كل عدد صالح بحسب شكله في التحليل إلى عوامل أولية، ثم تحويل كل فئة إلى مسألة تعتمد على دالة عدّ الأعداد الأولية.
لنعرّف
$$f(n)=\#\{x\in \mathbb{Z}_{>0}:x\le n,\ d(x)=8\},$$
حيث \(d(x)\) هي دالة عدد القواسم. وإذا كتبنا
$$x=\prod_i p_i^{a_i},$$
فإن
$$d(x)=\prod_i (a_i+1).$$
إذن المطلوب فعليًا هو تحديد جميع أنماط الأسس التي تجعل حاصل ضرب القيم \((a_i+1)\) مساويًا تمامًا لـ \(8\)، ثم عدّ كل نمط على حدة ضمن المجال حتى \(n\).
التحليلات الضربية الممكنة للعدد \(8\) هي
$$8,\qquad 4\cdot 2,\qquad 2\cdot 2\cdot 2.$$
ولذلك فإن كل عدد له بالضبط ثمانية قواسم لا بد أن يكون في واحدة من الصور الثلاث المنفصلة التالية:
$$x=p^7,\qquad x=p^3q,\qquad x=pqr,$$
حيث \(p,q,r\) أعداد أولية، وفي الحالة الوسطى يجب أن يكون \(p\ne q\)، وفي الحالة الأخيرة نفرض \(p\lt q\lt r\) حتى لا نعدّ العدد نفسه أكثر من مرة. ولا توجد أي صورة أخرى، لأن أي قائمة أسس مختلفة ستجعل \(\prod_i(a_i+1)\neq 8\).
لنفرض أن
$$p\lt q\lt r,\qquad pqr\le n.$$
إذا ثبّتنا الزوج \((p,q)\)، فإن العدد الأولي الثالث يجب أن يحقق
$$q\lt r\le \left\lfloor\frac{n}{pq}\right\rfloor.$$
إذًا عدد القيم الممكنة لـ \(r\) هو
$$\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q),$$
حيث \(\pi(x)\) تعطي عدد الأعداد الأولية التي لا تتجاوز \(x\). كذلك، إذا أصبح \(q^2>n/p\)، فإن أصغر \(r\) ممكن سيكون كبيرًا أكثر من اللازم. ولهذا يكفي أن نمر على \(q\) حتى \(\left\lfloor\sqrt{n/p}\right\rfloor\). ومن هنا نحصل على
$$A(n)=\sum_{\substack{p\lt q\\ pq^2\le n}}\left(\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q)\right).$$
ثبّت الآن عددًا أوليًا \(p\). كل عدد أولي \(q\) يحقق
$$q\le \left\lfloor\frac{n}{p^3}\right\rfloor$$
يعطي مرشحًا من الشكل \(p^3q\le n\). وإذا تجاهلنا مؤقتًا الشرط \(q\ne p\)، فإن مساهمة هذا \(p\) هي ببساطة \(\pi(\lfloor n/p^3\rfloor)\). وبجمع ذلك على جميع القيم الممكنة لـ \(p\) نحصل على العدّ الخام
$$B_{\mathrm{raw}}(n)=\sum_{p\le \lfloor \sqrt[3]{n}\rfloor}\pi\!\left(\left\lfloor\frac{n}{p^3}\right\rfloor\right).$$
وهذه هي الكمية التي يجمعها التنفيذ أولًا قبل أن يطبّق تصحيح الحالة غير المسموح بها.
العدّ الخام \(B_{\mathrm{raw}}(n)\) يتضمن خطأً الحالة \(q=p\). وعندها يصبح العدد
$$p^3q=p^4,$$
لكن \(p^4\) لا يملك ثمانية قواسم، بل يملك فقط
$$d(p^4)=5.$$
وتظهر هذه الزيادة الخاطئة بالضبط عندما
$$p^4\le n,$$
ولذلك فإن عدد الحدود غير الصحيحة يساوي
$$\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right).$$
إذن يصبح العدّ الصحيح للفئة \(p^3q\)
$$B(n)=B_{\mathrm{raw}}(n)-\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right).$$
أما الفئة الأخيرة فهي \(p^7\le n\)، ومساهمتها هي
$$C(n)=\pi\!\left(\left\lfloor n^{1/7}\right\rfloor\right).$$
وبما أن الفئات الثلاث متمايزة، فإن الصيغة النهائية هي
$$\boxed{f(n)=A(n)+B(n)+C(n).}$$
في فئة \(pqr\) لا يظهر أي إسهام إلا عندما \(p=2\). فعند \((p,q)=(2,3)\) نحصل على
$$\pi\!\left(\left\lfloor\frac{100}{6}\right\rfloor\right)-\pi(3)=\pi(16)-\pi(3)=6-2=4,$$
وهذه تمثل الأعداد \(30,42,66,78\). وعند \((p,q)=(2,5)\) نجد
$$\pi\!\left(\left\lfloor\frac{100}{10}\right\rfloor\right)-\pi(5)=\pi(10)-\pi(5)=4-3=1,$$
أي العدد \(70\). ومن ثم
$$A(100)=5.$$
أما في فئة \(p^3q\)، فإن العدّ الخام هو
$$B_{\mathrm{raw}}(100)=\pi(12)+\pi(3)=5+2=7.$$
والحالات الخاطئة ذات \(q=p\) تُحصى بواسطة
$$\pi\!\left(\left\lfloor 100^{1/4}\right\rfloor\right)=\pi(3)=2,$$
لذلك
$$B(100)=7-2=5.$$
وهذه الأعداد الخمسة هي \(24,40,54,56,88\). وأخيرًا بما أن \(100\lt 2^7\)، فإن
$$C(100)=0.$$
وعليه يكون
$$f(100)=5+5+0=10,$$
وهو تمامًا نفس مقدار التحقق المستخدم في التنفيذ.
تبدأ تطبيقات C++ وPython وJava بحساب الجذور الصحيحة التربيعية والتكعيبية والسابعة بدقة، ثم تصحح الحدود يدويًا حتى لا تؤثر أخطاء التقريب العائم في الحالات الحدية. بعد ذلك تُبنى قائمة الأعداد الأولية حتى \(\lfloor\sqrt{n}\rfloor\)، وهذا يكفي لأن كل عدد أولي يُستخدم في الحلقات الخارجية يقع ضمن هذا المجال.
ثم ينشئ التنفيذ بنية تركيبية لعدّ الأعداد الأولية على مجالين: قيم مباشرة حتى \(\sqrt{n}\)، وقيم من الشكل \(\lfloor n/i\rfloor\). وبعد مرحلة تحديث تعتمد على الأعداد الأولية واحدًا بعد آخر، يمكن الحصول على أي قيمة مطلوبة لـ \(\pi(x)\) بزمن ثابت.
بعد ذلك يقيّم التنفيذ نفس الأجزاء الثلاثة المشتقة رياضيًا: أولًا أزواج الأعداد الأولية في حالة \(pqr\)، ثم المجموع الخام لحالة \(p^3q\)، ثم طرح حدود \(p^4\) غير الصالحة، وأخيرًا إضافة مساهمة \(p^7\). مجموع هذه الأجزاء هو الجواب النهائي.
ليكن \(v=\lfloor\sqrt{n}\rfloor\). إن الغربال ومرحلة التهيئة الخاصة بدالة عدّ الأعداد الأولية يستخدمان \(O(v)\) من الذاكرة، ويحتاجان تقريبًا إلى \(O(v\log\log v)\) من العمل الحسابي على المجال الذي يُغربل صراحة. أما مرحلة \(p^3q\) فلا تمر إلا على الأعداد الأولية \(p\le n^{1/3}\)، ولذلك فهي تحتاج فقط إلى \(O(\pi(n^{1/3}))\) من استعلامات \(\pi\).
الجزء المسيطر هو مرحلة \(pqr\)، إذ تزور كل زوج أولي \((p,q)\) يحقق \(p\lt q\) و\(pq^2\le n\). ويمكن كتابة عدد التكرارات على الصورة
$$O\!\left(\sum_{p\le n^{1/3}}\pi\!\left(\sqrt{\frac{n}{p}}\right)\right),$$
بينما لا يحتوي كل تكرار إلا على عدد ثابت من الوصول إلى الجداول. عمليًا هذا أصغر بكثير من فحص جميع الأعداد حتى \(n\)، وهو مناسب تمامًا عندما \(n=10^{12}\).