For \(1\le x\le N\), the problem calls \(x\) square root smooth when every prime factor of \(x\) is strictly smaller than \(\sqrt{x}\). The number \(1\) is included as well, because it has no prime factors at all. The goal is to compute the count \(C(N)\) for \(N=10^{10}\) without testing every integer individually.
Let \(P^+(x)\) denote the largest prime factor of \(x\) for \(x\ge 2\). Instead of counting square root smooth integers directly, it is easier to count the complement and subtract from \(N\).
Define
$$NS(N)=\#\left\{x\in\{1,\dots,N\}:x\ge 2,\ P^+(x)\ge \sqrt{x}\right\}.$$
Then the required answer is simply
$$C(N)=N-NS(N).$$
So the whole problem becomes: how many integers up to \(N\) have a largest prime factor at least as large as their square root?
Take any non-smooth integer \(x\), and let \(p=P^+(x)\) be its largest prime factor. Write
$$x=pq.$$
Because \(p\ge \sqrt{x}\), we immediately get
$$q=\frac{x}{p}\le p.$$
Also \(x\le N\) implies
$$q\le \left\lfloor\frac{N}{p}\right\rfloor.$$
Conversely, suppose \(p\) is prime and
$$1\le q\le \min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right).$$
Then every prime factor of \(q\) is at most \(q\le p\), so the largest prime factor of \(pq\) is exactly \(p\). Since \(q\le p\), we also have \(p\ge \sqrt{pq}\), so \(pq\) is non-smooth. Therefore every non-smooth number is counted exactly once by a pair \((p,q)\), and
$$NS(N)=\sum_{p\le N}\min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right),$$
where the sum runs over primes \(p\).
The same pairs can be counted by fixing \(q\) first. Because \(q\le p\) and \(pq\le N\), necessarily
$$q\le \sqrt{N}.$$
For a fixed \(q\), the admissible primes satisfy
$$q\le p\le \left\lfloor\frac{N}{q}\right\rfloor.$$
Hence
$$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right).$$
This is the form used by the Python and Java implementations. Once prime counts are known on the relevant arguments, the final summation is immediate.
From the prime-based sum we can also separate the cases \(p\le \sqrt N\) and \(p>\sqrt N\):
$$NS(N)=\sum_{p\le \sqrt N}p+\sum_{\sqrt N<p\le N}\left\lfloor\frac{N}{p}\right\rfloor.$$
In the second sum the quotient
$$k=\left\lfloor\frac{N}{p}\right\rfloor$$
is constant on intervals of primes. The relevant block is
$$\max\left(\left\lfloor\sqrt N\right\rfloor+1,\left\lfloor\frac{N}{k+1}\right\rfloor+1\right)\le p\le \left\lfloor\frac{N}{k}\right\rfloor,$$
so its contribution is
$$k\left(\pi\left(\left\lfloor\frac{N}{k}\right\rfloor\right)-\pi\left(\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\frac{N}{k+1}\right\rfloor\right)\right)\right).$$
This is the viewpoint used by the C++ implementation: it groups large primes by equal quotient instead of iterating over every prime one by one.
Here \(\lfloor\sqrt{100}\rfloor=10\). The small-prime part contributes
$$2+3+5+7=17.$$
The large-prime blocks are
$$\begin{aligned} k=1&:\quad 1\cdot(\pi(100)-\pi(50))=10,\\ k=2&:\quad 2\cdot(\pi(50)-\pi(33))=8,\\ k=3&:\quad 3\cdot(\pi(33)-\pi(25))=6,\\ k=4&:\quad 4\cdot(\pi(25)-\pi(20))=4,\\ k=5&:\quad 5\cdot(\pi(20)-\pi(16))=10,\\ k=7&:\quad 7\cdot(\pi(14)-\pi(12))=7,\\ k=9&:\quad 9\cdot(\pi(11)-\pi(10))=9. \end{aligned}$$
The missing values \(k=6\) and \(k=8\) contribute \(0\) because the corresponding intervals contain no primes. Therefore
$$NS(100)=17+10+8+6+4+10+7+9=71,$$
and thus
$$C(100)=100-71=29.$$
This matches the checkpoint used by the implementations.
After the transformation above, the original smooth-number question no longer requires factoring every integer up to \(N\). Everything reduces to evaluating \(\pi(x)\) on roughly \(2\sqrt N\) relevant arguments and combining those values with one of the two equivalent summation formulas.
The C++, Python, and Java implementations all begin with the complement identity \(C(N)=N-NS(N)\). They differ only in how they obtain the needed prime-counting values \(\pi(x)\).
The C++ implementation uses a standard sieve for small values and a cached Lehmer prime-counting method for large arguments. It evaluates the split formula: first add all primes up to \(\lfloor\sqrt N\rfloor\), then process the quotient blocks where \(\left\lfloor N/p\right\rfloor\) is constant and multiply each quotient by the number of primes in that interval.
The Python and Java implementations precompute \(\pi(v)\) simultaneously on the distinct values
$$v\in\left\{\left\lfloor\frac{N}{1}\right\rfloor,\left\lfloor\frac{N}{2}\right\rfloor,\dots,\left\lfloor\frac{N}{\lfloor\sqrt N\rfloor}\right\rfloor\right\}\cup\{1,2,\dots,\lfloor\sqrt N\rfloor\}.$$
They use the standard combinatorial prime-counting update over all primes up to \(\lfloor\sqrt N\rfloor\), turning an initial table \(v-1\) into exact values of \(\pi(v)\). With those values available, they evaluate
$$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right)$$
and subtract the result from \(N\).
The mathematical reduction leaves only \(O(\sqrt N)\) relevant \(q\)-values or quotient blocks. The Python and Java implementations store prime-counting data on about \(2\sqrt N\) distinct arguments, so their memory usage is \(O(\sqrt N)\), and their preprocessing is the usual sublinear combinatorial prime-counting pass over those values. The C++ implementation also performs only \(O(\sqrt N)\) outer accumulation steps, with the main cost coming from memoized prime-counting queries. In all three cases the method is vastly faster than scanning every integer up to \(N\) and is easily practical for \(N=10^{10}\).
Für \(1\le x\le N\) heißt \(x\) im Sinne der Aufgabe square root smooth, wenn jeder Primteiler von \(x\) strikt kleiner als \(\sqrt{x}\) ist. Auch die Zahl \(1\) wird mitgezählt, weil sie gar keine Primfaktoren besitzt. Gesucht ist also \(C(N)\) für \(N=10^{10}\), ohne alle Zahlen einzeln zu prüfen.
Sei \(P^+(x)\) für \(x\ge 2\) der größte Primteiler von \(x\). Statt die gesuchten Zahlen direkt zu zählen, ist es einfacher, die komplementäre Menge zu zählen und am Ende von \(N\) abzuziehen.
Definiere
$$NS(N)=\#\left\{x\in\{1,\dots,N\}:x\ge 2,\ P^+(x)\ge \sqrt{x}\right\}.$$
Dann ist die Antwort
$$C(N)=N-NS(N).$$
Damit reduziert sich das Problem auf die Frage, wie viele Zahlen bis \(N\) einen größten Primteiler besitzen, der mindestens so groß wie ihre Quadratwurzel ist.
Nimm eine nicht-smooth Zahl \(x\) und setze \(p=P^+(x)\). Schreibe
$$x=pq.$$
Aus \(p\ge \sqrt{x}\) folgt sofort
$$q=\frac{x}{p}\le p.$$
Außerdem impliziert \(x\le N\), dass
$$q\le \left\lfloor\frac{N}{p}\right\rfloor.$$
Umgekehrt gelte: \(p\) sei prim und
$$1\le q\le \min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right).$$
Dann ist jeder Primteiler von \(q\) höchstens \(q\le p\), also ist der größte Primteiler von \(pq\) genau \(p\). Wegen \(q\le p\) gilt zudem \(p\ge \sqrt{pq}\), also ist \(pq\) nicht smooth. Jede nicht-smooth Zahl wird daher genau einmal durch ein Paar \((p,q)\) erfasst, und es gilt
$$NS(N)=\sum_{p\le N}\min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right),$$
wobei über Primzahlen \(p\) summiert wird.
Dieselben Paare kann man auch zählen, indem man zuerst \(q\) fixiert. Aus \(q\le p\) und \(pq\le N\) folgt notwendig
$$q\le \sqrt{N}.$$
Für ein festes \(q\) müssen die zulässigen Primzahlen also
$$q\le p\le \left\lfloor\frac{N}{q}\right\rfloor$$
erfüllen. Damit erhält man
$$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right).$$
Genau diese Form verwenden die Python- und Java-Implementierungen. Sobald die benötigten Werte der Primzahlzählfunktion bekannt sind, ist die Endsumme direkt auswertbar.
Aus der primbasierten Summe kann man die Fälle \(p\le \sqrt N\) und \(p>\sqrt N\) trennen:
$$NS(N)=\sum_{p\le \sqrt N}p+\sum_{\sqrt N<p\le N}\left\lfloor\frac{N}{p}\right\rfloor.$$
Im zweiten Summanden ist der Quotient
$$k=\left\lfloor\frac{N}{p}\right\rfloor$$
auf ganzen Primzahlintervallen konstant. Der relevante Block ist
$$\max\left(\left\lfloor\sqrt N\right\rfloor+1,\left\lfloor\frac{N}{k+1}\right\rfloor+1\right)\le p\le \left\lfloor\frac{N}{k}\right\rfloor,$$
und sein Beitrag lautet
$$k\left(\pi\left(\left\lfloor\frac{N}{k}\right\rfloor\right)-\pi\left(\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\frac{N}{k+1}\right\rfloor\right)\right)\right).$$
Dies ist die Sichtweise der C++-Implementierung: große Primzahlen werden nach gleichem Quotienten gruppiert, statt einzeln durchlaufen zu werden.
Hier ist \(\lfloor\sqrt{100}\rfloor=10\). Der Beitrag der kleinen Primzahlen ist
$$2+3+5+7=17.$$
Die Blöcke der großen Primzahlen sind
$$\begin{aligned} k=1&:\quad 1\cdot(\pi(100)-\pi(50))=10,\\ k=2&:\quad 2\cdot(\pi(50)-\pi(33))=8,\\ k=3&:\quad 3\cdot(\pi(33)-\pi(25))=6,\\ k=4&:\quad 4\cdot(\pi(25)-\pi(20))=4,\\ k=5&:\quad 5\cdot(\pi(20)-\pi(16))=10,\\ k=7&:\quad 7\cdot(\pi(14)-\pi(12))=7,\\ k=9&:\quad 9\cdot(\pi(11)-\pi(10))=9. \end{aligned}$$
Die ausgelassenen Werte \(k=6\) und \(k=8\) liefern \(0\), weil die zugehörigen Intervalle keine Primzahl enthalten. Also gilt
$$NS(100)=17+10+8+6+4+10+7+9=71,$$
und damit
$$C(100)=100-71=29.$$
Das ist genau der Kontrollwert, den die Implementierungen verwenden.
Nach dieser Umformung muss man nicht mehr jede Zahl bis \(N\) faktorisieren. Das gesamte Problem reduziert sich darauf, \(\pi(x)\) für ungefähr \(2\sqrt N\) relevante Argumente zu kennen und diese Werte in eine von zwei äquivalenten Summen einzusetzen.
Die C++-, Python- und Java-Implementierungen starten alle mit der Komplementformel \(C(N)=N-NS(N)\). Sie unterscheiden sich nur darin, wie die benötigten Werte der Primzahlzählfunktion \(\pi(x)\) gewonnen werden.
Die C++-Implementierung verwendet ein klassisches Sieb für kleine Werte und eine gecachte Lehmer-Methode für große Argumente. Anschließend wertet sie die gesplittete Formel aus: erst die Summe der Primzahlen bis \(\lfloor\sqrt N\rfloor\), danach die Quotientenblöcke, in denen \(\left\lfloor N/p\right\rfloor\) konstant bleibt.
Die Python- und Java-Implementierungen berechnen \(\pi(v)\) gleichzeitig für die verschiedenen Werte
$$v\in\left\{\left\lfloor\frac{N}{1}\right\rfloor,\left\lfloor\frac{N}{2}\right\rfloor,\dots,\left\lfloor\frac{N}{\lfloor\sqrt N\rfloor}\right\rfloor\right\}\cup\{1,2,\dots,\lfloor\sqrt N\rfloor\}.$$
Dafür benutzen sie den üblichen kombinatorischen Primzahlzähl-Update über alle Primzahlen bis \(\lfloor\sqrt N\rfloor\), der aus einer Anfangstabelle \(v-1\) die exakten Werte \(\pi(v)\) macht. Danach wird
$$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right)$$
aufsummiert und vom Gesamtwert \(N\) abgezogen.
Die mathematische Reduktion lässt nur \(O(\sqrt N)\) relevante \(q\)-Werte oder Quotientenblöcke übrig. Die Python- und Java-Implementierungen speichern Primzahlzählwerte für ungefähr \(2\sqrt N\) verschiedene Argumente, also \(O(\sqrt N)\) Speicher, und ihre Vorverarbeitung ist der übliche sublineare kombinatorische Primzahlzähl-Durchlauf über diese Werte. Die C++-Implementierung benötigt ebenfalls nur \(O(\sqrt N)\) äußere Akkumulationsschritte; dort dominiert der Aufwand der memoisierten Primzahlzählabfragen. In allen drei Fällen ist das Verfahren um Größenordnungen schneller als ein Test jeder einzelnen Zahl bis \(N\) und für \(N=10^{10}\) problemlos praktikabel.
Problemde \(1\le x\le N\) için, \(x\) sayısı ancak tüm asal çarpanları \(\sqrt{x}\)'ten sıkı biçimde küçükse square root smooth kabul edilir. \(1\) sayısı da dahildir; çünkü hiç asal çarpanı yoktur. Amaç, tüm sayıları tek tek denemeden \(N=10^{10}\) için bu sayıların toplamını bulmaktır.
\(x\ge 2\) için \(P^+(x)\) en büyük asal çarpan olsun. Doğrudan smooth sayıları saymak yerine, tamamlayıcı kümeyi sayıp sonucu \(N\)'den çıkarmak çok daha elverişlidir.
Şunu tanımlayalım:
$$NS(N)=\#\left\{x\in\{1,\dots,N\}:x\ge 2,\ P^+(x)\ge \sqrt{x}\right\}.$$
O zaman aranan cevap
$$C(N)=N-NS(N)$$
olur. Yani artık sorumuz, \(N\)'ye kadar olan sayılar içinde en büyük asal çarpanı kendi karekökü kadar büyük ya da daha büyük olanları saymaktır.
Smooth olmayan bir \(x\) sayısı alın ve \(p=P^+(x)\) olsun. O halde
$$x=pq$$
şeklinde yazabiliriz. \(p\ge \sqrt{x}\) olduğundan
$$q=\frac{x}{p}\le p$$
elde edilir. Ayrıca \(x\le N\) olduğu için
$$q\le \left\lfloor\frac{N}{p}\right\rfloor$$
de geçerlidir. Ters yönde, \(p\) asal ve
$$1\le q\le \min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right)$$
ise, \(q\)'nun her asal çarpanı en çok \(q\le p\) olur. Bu yüzden \(pq\)'nun en büyük asal çarpanı tam olarak \(p\)'dir. Ayrıca \(q\le p\) olduğundan \(p\ge \sqrt{pq}\) da sağlanır; yani \(pq\) smooth değildir. Dolayısıyla her smooth olmayan sayı tam bir kez bir \((p,q)\) çiftiyle temsil edilir ve
$$NS(N)=\sum_{p\le N}\min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right)$$
olur; burada toplam asallar üzerinden alınır.
Aynı çiftleri bu kez önce \(q\)'yu sabitleyerek de sayabiliriz. \(q\le p\) ve \(pq\le N\) olduğundan zorunlu olarak
$$q\le \sqrt{N}$$
olur. Sabit bir \(q\) için uygun asallar
$$q\le p\le \left\lfloor\frac{N}{q}\right\rfloor$$
aralığındadır. Böylece
$$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right)$$
elde edilir. Python ve Java uygulamaları tam olarak bu biçimi kullanır. Gerekli \(\pi(x)\) değerleri hazır olduğunda son toplama doğrudan yapılır.
Asal tabanlı toplamı \(p\le \sqrt N\) ve \(p>\sqrt N\) olarak ayırabiliriz:
$$NS(N)=\sum_{p\le \sqrt N}p+\sum_{\sqrt N<p\le N}\left\lfloor\frac{N}{p}\right\rfloor.$$
İkinci toplamda
$$k=\left\lfloor\frac{N}{p}\right\rfloor$$
değeri bazı asal aralıklarında sabittir. İlgili blok
$$\max\left(\left\lfloor\sqrt N\right\rfloor+1,\left\lfloor\frac{N}{k+1}\right\rfloor+1\right)\le p\le \left\lfloor\frac{N}{k}\right\rfloor$$
şeklindedir ve katkısı
$$k\left(\pi\left(\left\lfloor\frac{N}{k}\right\rfloor\right)-\pi\left(\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\frac{N}{k+1}\right\rfloor\right)\right)\right)$$
olur. C++ uygulaması büyük asalları tek tek gezmek yerine bu eşit bölüm bloklarını kullanır.
Burada \(\lfloor\sqrt{100}\rfloor=10\) olur. Küçük asalların katkısı
$$2+3+5+7=17$$
şeklindedir. Büyük asal blokları ise
$$\begin{aligned} k=1&:\quad 1\cdot(\pi(100)-\pi(50))=10,\\ k=2&:\quad 2\cdot(\pi(50)-\pi(33))=8,\\ k=3&:\quad 3\cdot(\pi(33)-\pi(25))=6,\\ k=4&:\quad 4\cdot(\pi(25)-\pi(20))=4,\\ k=5&:\quad 5\cdot(\pi(20)-\pi(16))=10,\\ k=7&:\quad 7\cdot(\pi(14)-\pi(12))=7,\\ k=9&:\quad 9\cdot(\pi(11)-\pi(10))=9. \end{aligned}$$
Atlanan \(k=6\) ve \(k=8\) değerleri için karşılık gelen aralıklarda asal olmadığından katkı \(0\)'dır. Böylece
$$NS(100)=17+10+8+6+4+10+7+9=71,$$
dolayısıyla
$$C(100)=100-71=29$$
çıkar. Bu, uygulamalardaki kontrol değeriyle aynıdır.
Bu dönüşümden sonra artık \(N\)'ye kadar her sayıyı çarpanlara ayırmak gerekmiyor. Tüm problem, yaklaşık \(2\sqrt N\) adet ilgili argümanda \(\pi(x)\) değerlerini bulup bunları iki eşdeğer toplam formülünden birinde birleştirmeye indirgeniyor.
C++, Python ve Java uygulamalarının üçü de \(C(N)=N-NS(N)\) tamamlayıcı formülüyle başlar. Aralarındaki fark yalnızca ihtiyaç duyulan \(\pi(x)\) değerlerini nasıl ürettikleridir.
C++ uygulaması küçük değerler için klasik bir elek ve büyük değerler için önbellekli Lehmer asal sayımı kullanır. Ardından bölünmüş formülü uygular: önce \(\lfloor\sqrt N\rfloor\)'ye kadar olan asalları toplar, sonra \(\left\lfloor N/p\right\rfloor\) sabit kalan bölüm bloklarını işler.
Python ve Java uygulamaları ise
$$v\in\left\{\left\lfloor\frac{N}{1}\right\rfloor,\left\lfloor\frac{N}{2}\right\rfloor,\dots,\left\lfloor\frac{N}{\lfloor\sqrt N\rfloor}\right\rfloor\right\}\cup\{1,2,\dots,\lfloor\sqrt N\rfloor\}$$
kümesindeki farklı değerler için \(\pi(v)\) sayımlarını aynı anda hazırlar. Bunun için \(\lfloor\sqrt N\rfloor\)'ye kadar olan asallar üzerinde standart kombinatoryal asal sayım güncellemesini uygularlar; başlangıçtaki \(v-1\) tablosu böylece gerçek \(\pi(v)\) değerlerine dönüşür. Sonra
$$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right)$$
toplamını hesaplayıp bunu \(N\)'den çıkarırlar.
Matematiksel indirgeme sonunda geriye yalnızca \(O(\sqrt N)\) adet ilgili \(q\) değeri veya bölüm bloğu kalır. Python ve Java uygulamaları yaklaşık \(2\sqrt N\) farklı argüman üzerinde asal sayma verisi tuttuğu için bellek kullanımları \(O(\sqrt N)\)'dir; ön işleme aşaması da bu değerler üzerindeki olağan alt-doğrusal kombinatoryal asal sayım geçişidir. C++ uygulaması da yalnızca \(O(\sqrt N)\) adet dış birikim adımı yapar; burada asıl maliyet önbellekli asal sayım sorgularıdır. Üç yaklaşım da \(N\)'ye kadar her sayıyı tek tek test etmekten çok daha hızlıdır ve \(N=10^{10}\) için rahatlıkla uygulanabilir.
Para \(1\le x\le N\), el problema llama square root smooth a \(x\) cuando todos sus factores primos son estrictamente menores que \(\sqrt{x}\). El número \(1\) también cuenta, porque no tiene factores primos. Hay que calcular \(C(N)\) para \(N=10^{10}\) sin revisar cada entero de forma individual.
Sea \(P^+(x)\) el mayor factor primo de \(x\) cuando \(x\ge 2\). En vez de contar directamente los números válidos, conviene contar el complemento y restarlo de \(N\).
Definimos
$$NS(N)=\#\left\{x\in\{1,\dots,N\}:x\ge 2,\ P^+(x)\ge \sqrt{x}\right\}.$$
Entonces la respuesta buscada es
$$C(N)=N-NS(N).$$
Así, el problema pasa a ser: ¿cuántos enteros hasta \(N\) tienen un mayor factor primo al menos tan grande como su raíz cuadrada?
Tomemos un entero no smooth \(x\) y sea \(p=P^+(x)\) su mayor factor primo. Escribimos
$$x=pq.$$
Como \(p\ge \sqrt{x}\), se obtiene
$$q=\frac{x}{p}\le p.$$
Además, de \(x\le N\) sigue que
$$q\le \left\lfloor\frac{N}{p}\right\rfloor.$$
Recíprocamente, si \(p\) es primo y
$$1\le q\le \min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right),$$
entonces cualquier factor primo de \(q\) es a lo sumo \(q\le p\), de modo que el mayor factor primo de \(pq\) es exactamente \(p\). Como además \(q\le p\), se cumple \(p\ge \sqrt{pq}\), y por tanto \(pq\) es no smooth. Esto muestra que cada entero no smooth se cuenta exactamente una vez mediante un par \((p,q)\), y por ello
$$NS(N)=\sum_{p\le N}\min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right),$$
donde la suma recorre los primos \(p\).
Los mismos pares también pueden contarse fijando primero \(q\). Como \(q\le p\) y \(pq\le N\), necesariamente
$$q\le \sqrt{N}.$$
Para un \(q\) fijo, los primos admisibles son precisamente
$$q\le p\le \left\lfloor\frac{N}{q}\right\rfloor.$$
Por lo tanto,
$$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right).$$
Esta es la forma utilizada por las implementaciones en Python y Java. Una vez conocidos los valores necesarios de \(\pi(x)\), la suma final es directa.
Desde la suma sobre primos también podemos separar los casos \(p\le \sqrt N\) y \(p>\sqrt N\):
$$NS(N)=\sum_{p\le \sqrt N}p+\sum_{\sqrt N<p\le N}\left\lfloor\frac{N}{p}\right\rfloor.$$
En la segunda suma, el cociente
$$k=\left\lfloor\frac{N}{p}\right\rfloor$$
permanece constante en intervalos enteros de primos. El bloque correspondiente es
$$\max\left(\left\lfloor\sqrt N\right\rfloor+1,\left\lfloor\frac{N}{k+1}\right\rfloor+1\right)\le p\le \left\lfloor\frac{N}{k}\right\rfloor,$$
y su contribución vale
$$k\left(\pi\left(\left\lfloor\frac{N}{k}\right\rfloor\right)-\pi\left(\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\frac{N}{k+1}\right\rfloor\right)\right)\right).$$
Esta es la perspectiva de la implementación en C++: agrupa los primos grandes por cocientes iguales, en vez de recorrerlos uno por uno.
Aquí \(\lfloor\sqrt{100}\rfloor=10\). La parte de primos pequeños aporta
$$2+3+5+7=17.$$
Los bloques de primos grandes son
$$\begin{aligned} k=1&:\quad 1\cdot(\pi(100)-\pi(50))=10,\\ k=2&:\quad 2\cdot(\pi(50)-\pi(33))=8,\\ k=3&:\quad 3\cdot(\pi(33)-\pi(25))=6,\\ k=4&:\quad 4\cdot(\pi(25)-\pi(20))=4,\\ k=5&:\quad 5\cdot(\pi(20)-\pi(16))=10,\\ k=7&:\quad 7\cdot(\pi(14)-\pi(12))=7,\\ k=9&:\quad 9\cdot(\pi(11)-\pi(10))=9. \end{aligned}$$
Los valores omitidos \(k=6\) y \(k=8\) contribuyen \(0\), porque sus intervalos no contienen primos. En consecuencia,
$$NS(100)=17+10+8+6+4+10+7+9=71,$$
y por tanto
$$C(100)=100-71=29.$$
Ese es exactamente el valor de comprobación usado por las implementaciones.
Después de esta transformación, ya no hace falta factorizar todos los enteros hasta \(N\). Todo se reduce a conocer \(\pi(x)\) en aproximadamente \(2\sqrt N\) argumentos relevantes y combinar esos valores con una de las dos fórmulas equivalentes anteriores.
Las implementaciones en C++, Python y Java parten de la identidad complementaria \(C(N)=N-NS(N)\). Solo difieren en la manera de obtener los valores necesarios de la función contadora de primos \(\pi(x)\).
La implementación en C++ usa una criba clásica para valores pequeños y un método de conteo de primos de Lehmer con caché para argumentos grandes. Luego evalúa la fórmula separada: primero suma los primos hasta \(\lfloor\sqrt N\rfloor\), y después procesa los bloques de cociente constante donde \(\left\lfloor N/p\right\rfloor\) no cambia.
Las implementaciones en Python y Java precalculan \(\pi(v)\) simultáneamente para los valores distintos
$$v\in\left\{\left\lfloor\frac{N}{1}\right\rfloor,\left\lfloor\frac{N}{2}\right\rfloor,\dots,\left\lfloor\frac{N}{\lfloor\sqrt N\rfloor}\right\rfloor\right\}\cup\{1,2,\dots,\lfloor\sqrt N\rfloor\}.$$
Para ello aplican la actualización combinatoria estándar de conteo de primos sobre todos los primos hasta \(\lfloor\sqrt N\rfloor\), convirtiendo una tabla inicial \(v-1\) en los valores exactos \(\pi(v)\). Con esos datos ya disponibles, evalúan
$$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right)$$
y restan el resultado de \(N\).
La reducción matemática deja solo \(O(\sqrt N)\) valores relevantes de \(q\) o bloques de cociente. Las implementaciones en Python y Java almacenan datos de conteo de primos sobre aproximadamente \(2\sqrt N\) argumentos distintos, de modo que su memoria es \(O(\sqrt N)\), y su preprocesamiento es el recorrido sublineal combinatorio habitual sobre esos valores. La implementación en C++ también realiza solo \(O(\sqrt N)\) pasos externos de acumulación; allí el coste principal proviene de las consultas memoizadas de conteo de primos. En los tres casos, el método es muchísimo más rápido que inspeccionar todos los enteros hasta \(N\) y resulta plenamente práctico para \(N=10^{10}\).
对 \(1\le x\le N\) 而言，如果 \(x\) 的每一个素因子都严格小于 \(\sqrt{x}\)，题目就把它称为 square root smooth。数字 \(1\) 也要计入，因为它根本没有素因子。目标是在不逐个检测所有整数的前提下，计算 \(N=10^{10}\) 时的总数 \(C(N)\)。
对 \(x\ge 2\)，记 \(P^+(x)\) 为 \(x\) 的最大素因子。与其直接数满足条件的整数，不如先数补集，再从 \(N\) 中减掉。
定义
$$NS(N)=\#\left\{x\in\{1,\dots,N\}:x\ge 2,\ P^+(x)\ge \sqrt{x}\right\}.$$
那么题目要求的答案就是
$$C(N)=N-NS(N).$$
也就是说，我们现在真正要做的是统计不满足 smooth 条件的整数个数。
取任意一个非 smooth 的整数 \(x\)，令 \(p=P^+(x)\) 是它的最大素因子。写成
$$x=pq.$$
由于 \(p\ge \sqrt{x}\)，立刻得到
$$q=\frac{x}{p}\le p.$$
同时，\(x\le N\) 还说明
$$q\le \left\lfloor\frac{N}{p}\right\rfloor.$$
反过来，如果 \(p\) 是素数并且
$$1\le q\le \min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right),$$
那么 \(q\) 的所有素因子都不超过 \(q\le p\)，所以 \(pq\) 的最大素因子一定就是 \(p\)。又因为 \(q\le p\)，于是 \(p\ge \sqrt{pq}\)，因此 \(pq\) 的确属于补集。这样就证明了：每一个非 smooth 数都恰好对应唯一的一对 \((p,q)\)，并且
$$NS(N)=\sum_{p\le N}\min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right),$$
其中求和变量 \(p\) 只遍历素数。
同一批配对也可以先固定 \(q\) 再计数。因为 \(q\le p\) 且 \(pq\le N\)，所以必然有
$$q\le \sqrt{N}.$$
当 \(q\) 固定时，可行的素数 \(p\) 正好满足
$$q\le p\le \left\lfloor\frac{N}{q}\right\rfloor.$$
因此
$$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right).$$
这正是 Python 和 Java 实现所采用的形式。一旦所需的 \(\pi(x)\) 值准备好，最后这一步求和就非常直接。
从按素数求和的公式出发，也可以把 \(p\le \sqrt N\) 与 \(p>\sqrt N\) 分开：
$$NS(N)=\sum_{p\le \sqrt N}p+\sum_{\sqrt N<p\le N}\left\lfloor\frac{N}{p}\right\rfloor.$$
在第二项中，商
$$k=\left\lfloor\frac{N}{p}\right\rfloor$$
会在整段素数区间上保持不变。对应区间是
$$\max\left(\left\lfloor\sqrt N\right\rfloor+1,\left\lfloor\frac{N}{k+1}\right\rfloor+1\right)\le p\le \left\lfloor\frac{N}{k}\right\rfloor,$$
于是这一整块的贡献为
$$k\left(\pi\left(\left\lfloor\frac{N}{k}\right\rfloor\right)-\pi\left(\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\frac{N}{k+1}\right\rfloor\right)\right)\right).$$
这正是 C++ 实现的思路：不是逐个枚举大素数，而是按相同商值的区间来分组处理。
此时 \(\lfloor\sqrt{100}\rfloor=10\)。小素数部分先给出
$$2+3+5+7=17.$$
大素数的商值分块为
$$\begin{aligned} k=1&:\quad 1\cdot(\pi(100)-\pi(50))=10,\\ k=2&:\quad 2\cdot(\pi(50)-\pi(33))=8,\\ k=3&:\quad 3\cdot(\pi(33)-\pi(25))=6,\\ k=4&:\quad 4\cdot(\pi(25)-\pi(20))=4,\\ k=5&:\quad 5\cdot(\pi(20)-\pi(16))=10,\\ k=7&:\quad 7\cdot(\pi(14)-\pi(12))=7,\\ k=9&:\quad 9\cdot(\pi(11)-\pi(10))=9. \end{aligned}$$
其中 \(k=6\) 和 \(k=8\) 被省略，是因为对应区间里没有素数，所以贡献为 \(0\)。因此
$$NS(100)=17+10+8+6+4+10+7+9=71,$$
从而
$$C(100)=100-71=29.$$
这与实现里的校验值完全一致。
经过上述变形之后，原问题已经不需要把 \(1\) 到 \(N\) 的每个整数都做质因数分解了。真正需要的只是大约 \(2\sqrt N\) 个相关参数上的 \(\pi(x)\) 值，然后把它们代入前面两种等价公式中的任意一种即可。
C++、Python 和 Java 三个实现都从补集公式 \(C(N)=N-NS(N)\) 出发。它们的差别只在于怎样求出需要的素数计数函数 \(\pi(x)\)。
C++ 实现对较小范围使用常规筛法，对较大参数使用带缓存的 Lehmer 素数计数。随后它按照“先加上 \(\lfloor\sqrt N\rfloor\) 以内的素数，再处理 \(\left\lfloor N/p\right\rfloor\) 不变的区间块”这一思路来累计补集总数。
Python 和 Java 实现则一次性预处理下面这些不同的参数上的 \(\pi(v)\)：
$$v\in\left\{\left\lfloor\frac{N}{1}\right\rfloor,\left\lfloor\frac{N}{2}\right\rfloor,\dots,\left\lfloor\frac{N}{\lfloor\sqrt N\rfloor}\right\rfloor\right\}\cup\{1,2,\dots,\lfloor\sqrt N\rfloor\}.$$
它们对所有不超过 \(\lfloor\sqrt N\rfloor\) 的素数执行标准的组合式素数计数更新，把初始的 \(v-1\) 表修正成真正的 \(\pi(v)\)。有了这些值之后，就计算
$$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right)$$
并从 \(N\) 中减去它。
数学变换之后，真正需要处理的只有 \(O(\sqrt N)\) 个 \(q\) 值或商值区间。Python 和 Java 实现会在大约 \(2\sqrt N\) 个不同参数上保存素数计数信息，因此空间复杂度是 \(O(\sqrt N)\)，预处理则是这些参数上的标准亚线性组合式素数计数过程。C++ 实现的外层累加同样只有 \(O(\sqrt N)\) 步，主要代价来自带缓存的素数计数查询。无论哪一种实现，都远快于逐个检查 \(1\) 到 \(N\) 的所有整数，对于 \(N=10^{10}\) 都完全可行。
Для \(1\le x\le N\) число \(x\) считается square root smooth, если каждый его простой делитель строго меньше \(\sqrt{x}\). Число \(1\) тоже входит в подсчет, потому что у него вообще нет простых делителей. Нужно найти \(C(N)\) при \(N=10^{10}\), не проверяя по отдельности все числа до \(N\).
Пусть \(P^+(x)\) обозначает наибольший простой делитель числа \(x\) при \(x\ge 2\). Вместо прямого подсчета удобнее посчитать дополнение и затем вычесть его из \(N\).
Определим
$$NS(N)=\#\left\{x\in\{1,\dots,N\}:x\ge 2,\ P^+(x)\ge \sqrt{x}\right\}.$$
Тогда искомое значение равно
$$C(N)=N-NS(N).$$
Значит, теперь задача состоит в том, чтобы посчитать числа до \(N\), у которых наибольший простой делитель не меньше их квадратного корня.
Возьмем любое число \(x\), не удовлетворяющее условию smooth, и положим \(p=P^+(x)\). Тогда
$$x=pq.$$
Из \(p\ge \sqrt{x}\) следует
$$q=\frac{x}{p}\le p.$$
Кроме того, из \(x\le N\) имеем
$$q\le \left\lfloor\frac{N}{p}\right\rfloor.$$
Обратно, если \(p\) простое и
$$1\le q\le \min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right),$$
то любой простой делитель \(q\) не превосходит \(q\le p\), а значит, наибольший простой делитель \(pq\) равен именно \(p\). Поскольку \(q\le p\), получаем и \(p\ge \sqrt{pq}\), то есть \(pq\) действительно лежит в дополнении. Следовательно, каждое не-smooth число учитывается ровно один раз парой \((p,q)\), и потому
$$NS(N)=\sum_{p\le N}\min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right),$$
где суммирование ведется по простым \(p\).
Те же пары можно посчитать и по-другому, сначала фиксируя \(q\). Так как \(q\le p\) и \(pq\le N\), обязательно
$$q\le \sqrt{N}.$$
Для фиксированного \(q\) допустимые простые удовлетворяют
$$q\le p\le \left\lfloor\frac{N}{q}\right\rfloor.$$
Отсюда следует формула
$$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right).$$
Именно эту форму используют реализации на Python и Java. Как только нужные значения \(\pi(x)\) вычислены, финальная сумма получается сразу.
Исходную сумму по простым можно разделить на случаи \(p\le \sqrt N\) и \(p>\sqrt N\):
$$NS(N)=\sum_{p\le \sqrt N}p+\sum_{\sqrt N<p\le N}\left\lfloor\frac{N}{p}\right\rfloor.$$
Во втором слагаемом частное
$$k=\left\lfloor\frac{N}{p}\right\rfloor$$
постоянно на целых интервалах простых чисел. Соответствующий блок имеет вид
$$\max\left(\left\lfloor\sqrt N\right\rfloor+1,\left\lfloor\frac{N}{k+1}\right\rfloor+1\right)\le p\le \left\lfloor\frac{N}{k}\right\rfloor,$$
а его вклад равен
$$k\left(\pi\left(\left\lfloor\frac{N}{k}\right\rfloor\right)-\pi\left(\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\frac{N}{k+1}\right\rfloor\right)\right)\right).$$
Так смотрит на задачу реализация на C++: большие простые обрабатываются блоками с одинаковым частным, а не по одному.
Здесь \(\lfloor\sqrt{100}\rfloor=10\). Вклад малых простых равен
$$2+3+5+7=17.$$
Блоки для больших простых дают
$$\begin{aligned} k=1&:\quad 1\cdot(\pi(100)-\pi(50))=10,\\ k=2&:\quad 2\cdot(\pi(50)-\pi(33))=8,\\ k=3&:\quad 3\cdot(\pi(33)-\pi(25))=6,\\ k=4&:\quad 4\cdot(\pi(25)-\pi(20))=4,\\ k=5&:\quad 5\cdot(\pi(20)-\pi(16))=10,\\ k=7&:\quad 7\cdot(\pi(14)-\pi(12))=7,\\ k=9&:\quad 9\cdot(\pi(11)-\pi(10))=9. \end{aligned}$$
Значения \(k=6\) и \(k=8\) пропущены, потому что их интервалы не содержат простых чисел и дают нулевой вклад. Следовательно,
$$NS(100)=17+10+8+6+4+10+7+9=71,$$
и потому
$$C(100)=100-71=29.$$
Именно этот контрольный результат используется в реализациях.
После такой переработки уже не нужно раскладывать на множители каждое число до \(N\). Вся задача сводится к вычислению \(\pi(x)\) примерно на \(2\sqrt N\) существенных аргументах и подстановке этих значений в одну из двух эквивалентных сумм.
Реализации на C++, Python и Java все начинают с формулы дополнения \(C(N)=N-NS(N)\). Различие только в том, как именно они получают нужные значения функции подсчета простых \(\pi(x)\).
Реализация на C++ использует обычное решето для малых аргументов и кешируемый метод Лемера для больших значений. Затем она применяет разбиение по \(\sqrt N\): сначала суммирует простые до \(\lfloor\sqrt N\rfloor\), а потом проходит по блокам, где \(\left\lfloor N/p\right\rfloor\) остается постоянным.
Реализации на Python и Java одновременно предвычисляют \(\pi(v)\) для различных значений
$$v\in\left\{\left\lfloor\frac{N}{1}\right\rfloor,\left\lfloor\frac{N}{2}\right\rfloor,\dots,\left\lfloor\frac{N}{\lfloor\sqrt N\rfloor}\right\rfloor\right\}\cup\{1,2,\dots,\lfloor\sqrt N\rfloor\}.$$
Они выполняют стандартное комбинаторное обновление подсчета простых по всем простым до \(\lfloor\sqrt N\rfloor\), превращая начальную таблицу \(v-1\) в точные значения \(\pi(v)\). После этого вычисляется
$$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right)$$
и вычитается из \(N\).
После математического преобразования остается только \(O(\sqrt N)\) существенных значений \(q\) или блоков частных. Реализации на Python и Java хранят данные для функции подсчета простых примерно на \(2\sqrt N\) различных аргументах, то есть используют \(O(\sqrt N)\) памяти, а их предварительная обработка представляет собой стандартный сублинейный комбинаторный проход по этим значениям. Реализация на C++ тоже выполняет лишь \(O(\sqrt N)\) внешних шагов накопления; основная стоимость в ней связана с кешируемыми запросами к функции подсчета простых. Во всех трех версиях метод на порядки быстрее, чем проверка каждого числа до \(N\), и вполне практичен для \(N=10^{10}\).
بالنسبة إلى \(1\le x\le N\)، تُعدّ القيمة \(x\) من نوع square root smooth إذا كان كل عامل أولي لها أصغر من \(\sqrt{x}\) على نحو صارم. كما تُحسب القيمة \(1\) أيضًا لأنها لا تملك أي عوامل أولية. المطلوب هو حساب \(C(N)\) عند \(N=10^{10}\) من دون فحص كل عدد على حدة.
لنرمز بـ \(P^+(x)\) إلى أكبر عامل أولي للعدد \(x\) عندما \(x\ge 2\). بدلًا من عدّ الأعداد المطلوبة مباشرة، يكون من الأسهل عدّ المتمم ثم طرحه من \(N\).
نعرّف
$$NS(N)=\#\left\{x\in\{1,\dots,N\}:x\ge 2,\ P^+(x)\ge \sqrt{x}\right\}.$$
وعندئذ يكون الجواب المطلوب
$$C(N)=N-NS(N).$$
إذن صار السؤال الحقيقي هو: كم عدد الأعداد حتى \(N\) التي يكون أكبر عامل أولي لها على الأقل بقدر جذرها التربيعي؟
خذ عددًا غير smooth وليكن \(p=P^+(x)\) أكبر عامل أولي له. عندها يمكن كتابة
$$x=pq.$$
ومن العلاقة \(p\ge \sqrt{x}\) نحصل مباشرة على
$$q=\frac{x}{p}\le p.$$
وكذلك من الشرط \(x\le N\) ينتج
$$q\le \left\lfloor\frac{N}{p}\right\rfloor.$$
وبالعكس، إذا كان \(p\) عددًا أوليًا وحقق
$$1\le q\le \min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right),$$
فإن كل عامل أولي لـ \(q\) لا يتجاوز \(q\le p\)، ولذلك يكون أكبر عامل أولي للعدد \(pq\) هو \(p\) نفسه. وبما أن \(q\le p\)، نحصل أيضًا على \(p\ge \sqrt{pq}\)، أي إن \(pq\) ينتمي فعلًا إلى المتمم. وهكذا فإن كل عدد غير smooth يُعدّ مرة واحدة بالضبط بواسطة الزوج \((p,q)\)، ومن ثم
$$NS(N)=\sum_{p\le N}\min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right),$$
حيث يمتد الجمع على الأعداد الأولية \(p\).
يمكن عدّ الأزواج نفسها إذا ثبّتنا \(q\) أولًا. فمن الشرطين \(q\le p\) و\(pq\le N\) يلزم أن
$$q\le \sqrt{N}.$$
ولقيمة ثابتة من \(q\)، تكون الأعداد الأولية المسموح بها هي
$$q\le p\le \left\lfloor\frac{N}{q}\right\rfloor.$$
وعليه نحصل على
$$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right).$$
هذه هي الصيغة التي تعتمدها تنفيذا Python وJava. فعندما تصبح قيم \(\pi(x)\) المطلوبة جاهزة، يكون الجمع النهائي مباشرًا.
يمكن أيضًا فصل مجموع الأعداد الأولية إلى الحالتين \(p\le \sqrt N\) و\(p>\sqrt N\):
$$NS(N)=\sum_{p\le \sqrt N}p+\sum_{\sqrt N<p\le N}\left\lfloor\frac{N}{p}\right\rfloor.$$
في الحد الثاني يبقى خارج القسمة
$$k=\left\lfloor\frac{N}{p}\right\rfloor$$
ثابتًا على مجالات كاملة من الأعداد الأولية. والمجال الموافق هو
$$\max\left(\left\lfloor\sqrt N\right\rfloor+1,\left\lfloor\frac{N}{k+1}\right\rfloor+1\right)\le p\le \left\lfloor\frac{N}{k}\right\rfloor,$$
فتكون مساهمة هذا المجال
$$k\left(\pi\left(\left\lfloor\frac{N}{k}\right\rfloor\right)-\pi\left(\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\frac{N}{k+1}\right\rfloor\right)\right)\right).$$
هذه هي الزاوية التي يستخدمها تنفيذ C++: بدل المرور على كل عدد أولي كبير منفردًا، يجمعها في كتل ذات خارج قسمة واحد.
لدينا هنا \(\lfloor\sqrt{100}\rfloor=10\). مساهمة الأعداد الأولية الصغيرة هي
$$2+3+5+7=17.$$
أما كتل الأعداد الأولية الكبيرة فهي
$$\begin{aligned} k=1&:\quad 1\cdot(\pi(100)-\pi(50))=10,\\ k=2&:\quad 2\cdot(\pi(50)-\pi(33))=8,\\ k=3&:\quad 3\cdot(\pi(33)-\pi(25))=6,\\ k=4&:\quad 4\cdot(\pi(25)-\pi(20))=4,\\ k=5&:\quad 5\cdot(\pi(20)-\pi(16))=10,\\ k=7&:\quad 7\cdot(\pi(14)-\pi(12))=7,\\ k=9&:\quad 9\cdot(\pi(11)-\pi(10))=9. \end{aligned}$$
القيمتان \(k=6\) و\(k=8\) غير ظاهرتين لأن المجالين الموافقين لهما لا يحتويان أي أعداد أولية، وبالتالي فمساهمتهما تساوي \(0\). لذا
$$NS(100)=17+10+8+6+4+10+7+9=71,$$
ومن ثم
$$C(100)=100-71=29.$$
وهذا يطابق تمامًا قيمة التحقق المستخدمة في التنفيذات.
بعد هذا التحويل لم تعد هناك حاجة إلى تحليل كل عدد حتى \(N\) إلى عوامله الأولية. فالمسألة كلها تختزل إلى معرفة \(\pi(x)\) عند نحو \(2\sqrt N\) من القيم المهمة، ثم دمج هذه القيم في إحدى الصيغتين المتكافئتين السابقتين.
تنفيذا C++ وPython وJava كلها تبدأ من هوية المتمم \(C(N)=N-NS(N)\). والاختلاف بينها ينحصر في الطريقة التي تحصل بها على قيم دالة عدّ الأعداد الأولية \(\pi(x)\).
تنفيذ C++ يستخدم غربالًا قياسيًا للقيم الصغيرة وطريقة Lehmer مع تخزين مؤقت للقيم الكبيرة. بعد ذلك يطبق الصيغة المفصولة: يجمع أولًا الأعداد الأولية حتى \(\lfloor\sqrt N\rfloor\)، ثم يعالج كتل خارج القسمة التي تبقى فيها \(\left\lfloor N/p\right\rfloor\) ثابتة.
أما تنفيذا Python وJava فيحسبان \(\pi(v)\) دفعة واحدة للقيم المختلفة
$$v\in\left\{\left\lfloor\frac{N}{1}\right\rfloor,\left\lfloor\frac{N}{2}\right\rfloor,\dots,\left\lfloor\frac{N}{\lfloor\sqrt N\rfloor}\right\rfloor\right\}\cup\{1,2,\dots,\lfloor\sqrt N\rfloor\}.$$
ويستعملان التحديث التوافقي المعياري لعدّ الأعداد الأولية على جميع الأعداد الأولية حتى \(\lfloor\sqrt N\rfloor\)، بحيث تتحول القيمة الابتدائية \(v-1\) إلى القيمة الدقيقة \(\pi(v)\). وبعد توفر هذه القيم يُحسب
$$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right)$$
ثم يُطرح من \(N\).
بعد الاختزال الرياضي لا يبقى سوى \(O(\sqrt N)\) من قيم \(q\) المهمة أو كتل خارج القسمة. تنفيذا Python وJava يحتفظان ببيانات عدّ أولي على نحو \(2\sqrt N\) من القيم المختلفة، لذا يكون استهلاك الذاكرة \(O(\sqrt N)\)، وتكون مرحلة التهيئة هي المرور التوافقي المعتاد ذو الكلفة دون الخطية على هذه القيم. أما تنفيذ C++ فينجز هو أيضًا \(O(\sqrt N)\) فقط من خطوات التجميع الخارجية، وتأتي الكلفة الأساسية فيه من استعلامات عدّ الأعداد الأولية المخزنة مؤقتًا. في الحالات الثلاث، تكون الطريقة أسرع بكثير من فحص كل عدد حتى \(N\)، وهي عملية تمامًا عند \(N=10^{10}\).