Write a positive integer \(n\gt 1\) in the form
$$n=\prod_{i=1}^{k} p_i^{e_i},\qquad p_1 \lt p_2 \lt \cdots \lt p_k,$$
where the primes are listed in increasing order. Problem 578 asks for the counting function
$$C(N)=\#\left\{n\le N : e_1\ge e_2\ge \cdots \ge e_k\ge 1\right\},$$
with \(1\) also counted. The difficulty is that \(N\) is enormous, so the solution cannot test each integer separately. Instead, it counts valid factorizations by their exponent pattern and then counts how many prime choices realize each pattern.
The implementations split the problem into two layers: first enumerate every feasible nonincreasing exponent pattern, then count the prime tuples that fit that pattern under the bound \(N\).
Every valid integer \(n\gt 1\) has a unique signature
$$\lambda=(e_1,e_2,\dots,e_k),\qquad e_1\ge e_2\ge \cdots \ge e_k\ge 1.$$
For a fixed signature define
$$A_\lambda(N)=\#\left\{(p_1,\dots,p_k): p_1\lt \cdots \lt p_k,\ \prod_{i=1}^{k} p_i^{e_i}\le N\right\}.$$
Then
$$C(N)=1+\sum_{\lambda} A_\lambda(N),$$
where the \(+1\) accounts for \(n=1\). A signature is feasible only if even its smallest possible realization fits:
$$2^{e_1}3^{e_2}5^{e_3}\cdots p_k^{e_k}\le N.$$
This observation is the foundation for the signature-generation recursion.
Let \(p_1,p_2,\dots\) denote the prime numbers. Suppose we have already committed to primes up through \(p_i\), so the next chosen prime must be larger than \(p_i\). For a remaining exponent list \((f_1,\dots,f_r)\) and a remaining limit \(L\), define
$$R(f_1,\dots,f_r;L,i)$$
to be the number of strictly increasing prime choices \(q_1\lt \cdots \lt q_r\), all greater than \(p_i\), such that
$$q_1^{f_1}q_2^{f_2}\cdots q_r^{f_r}\le L.$$
The recursive relation is
$$R(f_1,\dots,f_r;L,i)=\sum_{j>i,\ p_j^{f_1}\le L} R(f_2,\dots,f_r;L/p_j^{f_1},j).$$
The desired count for a full signature is simply
$$A_{(e_1,\dots,e_k)}(N)=R(e_1,\dots,e_k;N,0).$$
When only one exponent \(e\) remains, the recursion reduces to counting primes:
$$R(e;L,i)=\max\left(0,\pi\left(\left\lfloor L^{1/e}\right\rfloor\right)-i\right).$$
The reason is simple: any prime \(q\) larger than the first \(i\) primes is valid exactly when \(q^e\le L\).
When two exponents \(e\ge f\) remain, we obtain
$$R(e,f;L,i)=\sum_{j>i,\ p_j^e\le L}\max\left(0,\pi\left(\left\lfloor (L/p_j^e)^{1/f}\right\rfloor\right)-j\right).$$
This is much faster than descending one level deeper for every pair. The C++ implementation also gives special treatment to common exponents \(1,2,4,8\), because the corresponding bounds can be obtained by exact integer roots.
For long signatures, most branches are impossible. If we are considering the next prime \(p_j\) for the remaining exponents \((f_1,\dots,f_r)\), then even the smallest possible continuation would use consecutive larger primes:
$$p_j^{f_1}p_{j+1}^{f_2}\cdots p_{j+r-1}^{f_r}.$$
If this minimal product already exceeds \(L\), then no later choice of \(p_j\) can work, because later primes are only larger. So the search can stop immediately at that point instead of exploring dead branches.
A separate recursion generates the signatures themselves. Start with an exponent \(e_1\ge 1\) satisfying \(2^{e_1}\le N\). For the next position choose \(e_2\) with
$$1\le e_2\le e_1,\qquad 3^{e_2}\le N/2^{e_1}.$$
Then continue with \(5,7,11,\dots\) as the smallest possible future primes. Every time a prefix \((e_1,\dots,e_t)\) is feasible with these minimal primes, that prefix represents a genuine signature, so its contribution \(A_{(e_1,\dots,e_t)}(N)\) is added immediately. Extending the prefix by a new exponent \(e_{t+1}\le e_t\) guarantees that each nonincreasing signature appears once and only once.
Here we count numbers of the form \(p^2q\) with \(p\lt q\) and \(p^2q\le 100\). The formula becomes
$$A_{(2,1)}(100)=\sum_{p^2\le 100}\#\left\{q>p:\ q\le 100/p^2,\ q\text{ prime}\right\}.$$
Now evaluate each possible first prime:
$$\begin{aligned} p=2&:\quad q\le 25 &&\Rightarrow 8,\\ p=3&:\quad q\le 11 &&\Rightarrow 3,\\ p\ge 5&:\quad p^2q>100 &&\Rightarrow 0. \end{aligned}$$
So \(A_{(2,1)}(100)=11\). The same pruning idea also shows immediately that the longer signature \((2,2,1)\) is impossible at \(N=100\), because its minimal realization would be
$$2^2\cdot 3^2\cdot 5=180>100.$$
When all feasible signatures are summed, the total is \(C(100)=94\), which matches the implementation's checkpoint.
The C++ implementation begins by precomputing a compressed prime-count structure. It stores enough information to answer \(\pi(x)\) quickly both for small values of \(x\) and for quotient values of the form \(\lfloor N/v\rfloor\). It also precomputes prime powers \(p^e\le N\) for the primes that can matter in recursive branches.
After that, one recursive routine generates every feasible nonincreasing exponent signature, using the minimal primes \(2,3,5,\dots\) only as a feasibility test. Another recursive routine counts prime tuples for the current signature. Whenever only one or two exponents remain, the search switches to direct prime-count formulas instead of recursing blindly. Independent top-level branches, distinguished by the first exponent, are processed in parallel and then added together.
The Python and Java implementations do not reimplement the mathematics separately. They invoke the same compiled computation and extract the final numeric answer, so all three language versions use the same counting method.
There is no clean closed form depending only on \(N\), because the search cost is governed by how many exponent signatures survive the feasibility tests and how many prime branches survive pruning. The prime-count preprocessing stores \(O(\sqrt{N})\) distinct arguments and uses \(O(\sqrt{N})\) memory; its arithmetic cost is close to \(O(\sqrt{N}\log\log N)\).
After preprocessing, let \(B(N)\) denote the total number of recursive states that remain after pruning. Then the overall running time is roughly
$$O\!\left(\sqrt{N}\log\log N + B(N)\right),$$
with terminal branches answered by fast \(\pi(x)\) queries rather than full subtree expansion. In practice, this is dramatically smaller than enumerating all integers up to \(N\), which is why the method is fast enough for the Project Euler bound.
Schreibe eine positive ganze Zahl \(n\gt 1\) als
$$n=\prod_{i=1}^{k} p_i^{e_i},\qquad p_1 \lt p_2 \lt \cdots \lt p_k,$$
wobei die Primzahlen aufsteigend sortiert sind. Gesucht ist die Zählfunktion
$$C(N)=\#\left\{n\le N : e_1\ge e_2\ge \cdots \ge e_k\ge 1\right\},$$
wobei auch \(1\) mitgezählt wird. Da \(N\) sehr groß ist, kann man die Zahlen nicht einzeln testen. Stattdessen zählt die Lösung zuerst Exponentensignaturen und danach die Primzahl-Tupel, die zu jeder Signatur passen.
Die Implementierungen zerlegen das Problem in zwei Schichten: Zuerst werden alle zulässigen nichtanwachsenden Exponentenmuster erzeugt, danach zählt man für jedes Muster die möglichen Primzahlen.
Jede gültige Zahl \(n\gt 1\) besitzt eine eindeutige Signatur
$$\lambda=(e_1,e_2,\dots,e_k),\qquad e_1\ge e_2\ge \cdots \ge e_k\ge 1.$$
Für eine feste Signatur definieren wir
$$A_\lambda(N)=\#\left\{(p_1,\dots,p_k): p_1\lt \cdots \lt p_k,\ \prod_{i=1}^{k} p_i^{e_i}\le N\right\}.$$
Dann gilt
$$C(N)=1+\sum_{\lambda} A_\lambda(N),$$
wobei das \(+1\) für \(n=1\) steht. Eine Signatur ist nur dann möglich, wenn schon ihre kleinste Realisierung unterhalb von \(N\) liegt:
$$2^{e_1}3^{e_2}5^{e_3}\cdots p_k^{e_k}\le N.$$
Genau daraus entsteht die Rekursion, die die Signaturen erzeugt.
Bezeichne \(p_1,p_2,\dots\) als die Folge aller Primzahlen. Angenommen, es wurden bereits Primzahlen bis einschließlich \(p_i\) verbraucht, dann muss die nächste gewählte Primzahl größer als \(p_i\) sein. Für eine verbleibende Exponentenliste \((f_1,\dots,f_r)\) und ein Restlimit \(L\) sei
$$R(f_1,\dots,f_r;L,i)$$
die Anzahl streng wachsender Primzahlwahlen \(q_1\lt \cdots \lt q_r\), alle größer als \(p_i\), mit
$$q_1^{f_1}q_2^{f_2}\cdots q_r^{f_r}\le L.$$
Dann erhält man die Rekursion
$$R(f_1,\dots,f_r;L,i)=\sum_{j>i,\ p_j^{f_1}\le L} R(f_2,\dots,f_r;L/p_j^{f_1},j).$$
Der gesuchte Beitrag einer ganzen Signatur ist also
$$A_{(e_1,\dots,e_k)}(N)=R(e_1,\dots,e_k;N,0).$$
Bleibt nur noch ein Exponent \(e\), reduziert sich das Problem auf Primzahlzählen:
$$R(e;L,i)=\max\left(0,\pi\left(\left\lfloor L^{1/e}\right\rfloor\right)-i\right).$$
Denn gültig ist genau jede Primzahl \(q\), die größer als die ersten \(i\) Primzahlen ist und \(q^e\le L\) erfüllt.
Für zwei verbleibende Exponenten \(e\ge f\) gilt
$$R(e,f;L,i)=\sum_{j>i,\ p_j^e\le L}\max\left(0,\pi\left(\left\lfloor (L/p_j^e)^{1/f}\right\rfloor\right)-j\right).$$
Das ist deutlich schneller als alle Paare rekursiv auszuprobieren. Die C++-Implementierung behandelt außerdem die häufigen Exponenten \(1,2,4,8\) besonders effizient, weil sich die Schranken dann über exakte ganzzahlige Wurzeln gewinnen lassen.
Bei langen Signaturen sind die meisten Äste unmöglich. Wenn als nächste Primzahl \(p_j\) geprüft wird und die restlichen Exponenten \((f_1,\dots,f_r)\) sind, dann hätte selbst die kleinste mögliche Fortsetzung den Wert
$$p_j^{f_1}p_{j+1}^{f_2}\cdots p_{j+r-1}^{f_r}.$$
Ist dieses Minimalprodukt schon größer als \(L\), dann kann keine spätere Wahl von \(p_j\) mehr funktionieren, weil spätere Primzahlen nur größer werden. Der Suchast wird also sofort beendet.
Eine zweite Rekursion erzeugt die Signaturen selbst. Man beginnt mit \(e_1\ge 1\) unter der Bedingung \(2^{e_1}\le N\). Für die nächste Position wählt man \(e_2\) mit
$$1\le e_2\le e_1,\qquad 3^{e_2}\le N/2^{e_1}.$$
Danach setzt man mit \(5,7,11,\dots\) als kleinsten möglichen zukünftigen Primzahlen fort. Immer wenn ein Präfix \((e_1,\dots,e_t)\) mit diesen Minimalprimzahlen noch unter \(N\) liegt, repräsentiert es bereits eine echte Signatur; deshalb wird sein Beitrag \(A_{(e_1,\dots,e_t)}(N)\) sofort addiert. Durch die Bedingung \(e_{t+1}\le e_t\) erscheint jede nichtanwachsende Signatur genau einmal.
Hier zählen wir Zahlen der Form \(p^2q\) mit \(p\lt q\) und \(p^2q\le 100\). Die Formel lautet
$$A_{(2,1)}(100)=\sum_{p^2\le 100}\#\left\{q>p:\ q\le 100/p^2,\ q\text{ prime}\right\}.$$
Für die möglichen ersten Primzahlen ergibt sich
$$\begin{aligned} p=2&:\quad q\le 25 &&\Rightarrow 8,\\ p=3&:\quad q\le 11 &&\Rightarrow 3,\\ p\ge 5&:\quad p^2q>100 &&\Rightarrow 0. \end{aligned}$$
Also ist \(A_{(2,1)}(100)=11\). Dasselbe Abschneidekriterium zeigt sofort, dass die längere Signatur \((2,2,1)\) bei \(N=100\) unmöglich ist, denn
$$2^2\cdot 3^2\cdot 5=180>100.$$
Summiert man alle zulässigen Signaturen, erhält man \(C(100)=94\), genau wie im Kontrollwert der Implementierung.
Die C++-Implementierung beginnt mit einer komprimierten Struktur für Primzahlzählungen. Sie speichert genügend Informationen, um \(\pi(x)\) sowohl für kleine Argumente als auch für Quotientenwerte der Form \(\lfloor N/v\rfloor\) schnell beantworten zu können. Zusätzlich werden für alle relevanten Primzahlen die Potenzen \(p^e\le N\) vorab erzeugt.
Danach erzeugt eine Rekursion alle zulässigen nichtanwachsenden Signaturen, wobei die Minimalprimzahlen \(2,3,5,\dots\) nur als Machbarkeitstest dienen. Eine zweite Rekursion zählt für die aktuelle Signatur die konkreten Primzahl-Tupel. Sobald nur noch ein oder zwei Exponenten übrig sind, wird nicht weiter blind rekursiert, sondern direkt mit Primzahlzählformeln abgeschlossen. Unabhängige Top-Level-Äste, die durch den ersten Exponenten bestimmt sind, werden parallel verarbeitet und anschließend aufsummiert.
Die Python- und Java-Implementierungen setzen die Mathematik nicht neu um. Sie rufen dieselbe kompilierte Berechnung auf und lesen am Ende nur die ausgegebene Zahl aus. Darum verwenden alle drei Sprachversionen exakt dieselbe Zählmethode.
Es gibt keine einfache geschlossene Formel nur in Abhängigkeit von \(N\), weil die Suchkosten davon abhängen, wie viele Exponentensignaturen die Machbarkeitstests überleben und wie viele Primzahläste nach dem Abschneiden übrig bleiben. Die Vorverarbeitung für Primzahlzählungen speichert \(O(\sqrt{N})\) verschiedene Argumente und benötigt \(O(\sqrt{N})\) Speicher; der Rechenaufwand liegt näherungsweise bei \(O(\sqrt{N}\log\log N)\).
Sei \(B(N)\) die Gesamtzahl der rekursiven Zustände nach dem Abschneiden. Dann ist die Gesamtlaufzeit ungefähr
$$O\!\left(\sqrt{N}\log\log N + B(N)\right).$$
Weil Endäste durch schnelle \(\pi(x)\)-Abfragen beantwortet werden und nicht vollständig expandieren, ist \(B(N)\) in der Praxis viel kleiner als eine naive Enumeration aller Zahlen bis \(N\).
Pozitif bir \(n\gt 1\) tam sayısını
$$n=\prod_{i=1}^{k} p_i^{e_i},\qquad p_1 \lt p_2 \lt \cdots \lt p_k,$$
şeklinde yazalım; burada asallar artan sıradadır. Problem 578 şu sayma fonksiyonunu ister:
$$C(N)=\#\left\{n\le N : e_1\ge e_2\ge \cdots \ge e_k\ge 1\right\},$$
ve \(1\) de bu sayıya dahildir. \(N\) çok büyük olduğundan her sayıyı tek tek test etmek mümkün değildir. Bunun yerine çözüm, önce üs desenlerini sayar, sonra her desenin kaç farklı asal seçimiyle gerçekleştiğini hesaplar.
Uygulamalar problemi iki katmanda çözer: önce mümkün olan tüm azalmayan değil, azalan ya da sabit üs imzaları üretilir; ardından her imza için uygun asal dizileri sayılır.
Her geçerli \(n\gt 1\) sayısının tek bir imzası vardır:
$$\lambda=(e_1,e_2,\dots,e_k),\qquad e_1\ge e_2\ge \cdots \ge e_k\ge 1.$$
Sabit bir imza için
$$A_\lambda(N)=\#\left\{(p_1,\dots,p_k): p_1\lt \cdots \lt p_k,\ \prod_{i=1}^{k} p_i^{e_i}\le N\right\}$$
tanımını yapalım. O zaman
$$C(N)=1+\sum_{\lambda} A_\lambda(N)$$
olur; buradaki \(+1\), \(n=1\) içindir. Bir imza ancak en küçük gerçekleşme biçimi bile \(N\)'yi aşmıyorsa mümkündür:
$$2^{e_1}3^{e_2}5^{e_3}\cdots p_k^{e_k}\le N.$$
İmza üretme özyinelemesi tam olarak bu gözleme dayanır.
\(p_1,p_2,\dots\) bütün asallar olsun. Diyelim ki \(p_i\)'ye kadar olan asallar artık kullanılamaz; o halde sıradaki asal mutlaka \(p_i\)'den büyük olmalıdır. Kalan üs listesi \((f_1,\dots,f_r)\) ve kalan çarpımsal sınır \(L\) için
$$R(f_1,\dots,f_r;L,i)$$
ifadesi, \(p_i\)'den büyük olan ve
$$q_1^{f_1}q_2^{f_2}\cdots q_r^{f_r}\le L$$
koşulunu sağlayan sıkı artan asal seçimlerinin \(q_1\lt \cdots \lt q_r\) sayısını göstersin. O zaman özyineleme
$$R(f_1,\dots,f_r;L,i)=\sum_{j>i,\ p_j^{f_1}\le L} R(f_2,\dots,f_r;L/p_j^{f_1},j)$$
şeklindedir. Tam imza katkısı da
$$A_{(e_1,\dots,e_k)}(N)=R(e_1,\dots,e_k;N,0)$$
olur.
Yalnızca bir üs \(e\) kaldığında problem doğrudan asal saymaya iner:
$$R(e;L,i)=\max\left(0,\pi\left(\left\lfloor L^{1/e}\right\rfloor\right)-i\right).$$
Çünkü geçerli her asal \(q\), hem ilk \(i\) asaldan büyük olmalı hem de \(q^e\le L\) koşulunu sağlamalıdır.
İki üs \(e\ge f\) kaldığında ise
$$R(e,f;L,i)=\sum_{j>i,\ p_j^e\le L}\max\left(0,\pi\left(\left\lfloor (L/p_j^e)^{1/f}\right\rfloor\right)-j\right)$$
elde edilir. Bu, her çifti tam özyinelemeyle dolaşmaktan çok daha hızlıdır. C++ uygulaması ayrıca \(1,2,4,8\) üslerini özel olarak hızlandırır; çünkü bu durumlarda sınırlar tam sayı kökleriyle doğrudan elde edilir.
Uzun imzalarda dalların çoğu imkansızdır. Sıradaki asal için \(p_j\) adayını ve kalan üsler için \((f_1,\dots,f_r)\) listesini düşünelim. En küçük olası devam bile
$$p_j^{f_1}p_{j+1}^{f_2}\cdots p_{j+r-1}^{f_r}$$
olacaktır. Bu minimal çarpım \(L\)'yi aşıyorsa daha sonraki hiçbir \(p_j\) işe yaramaz; çünkü sonraki asallar daha büyüktür. Böylece dal anında kesilir.
Ayrı bir özyineleme imzaların kendisini üretir. Önce \(2^{e_1}\le N\) olacak şekilde \(e_1\ge 1\) seçilir. Sonra
$$1\le e_2\le e_1,\qquad 3^{e_2}\le N/2^{e_1}$$
koşuluyla \(e_2\) seçilir. Bundan sonra \(5,7,11,\dots\) en küçük olası gelecek asallar olarak kullanılır. Bir önek \((e_1,\dots,e_t)\) bu minimal asallarla bile uygunsa, bu önek gerçek bir imzayı temsil eder; dolayısıyla \(A_{(e_1,\dots,e_t)}(N)\) katkısı hemen eklenir. Yeni üssün her zaman \(e_{t+1}\le e_t\) alınması, her azalan imzanın tam bir kez oluşmasını sağlar.
Burada \(p^2q\) biçimindeki sayıları, \(p\lt q\) ve \(p^2q\le 100\) olacak şekilde sayıyoruz. Formül
$$A_{(2,1)}(100)=\sum_{p^2\le 100}\#\left\{q>p:\ q\le 100/p^2,\ q\text{ prime}\right\}$$
olur. Olası ilk asallara bakalım:
$$\begin{aligned} p=2&:\quad q\le 25 &&\Rightarrow 8,\\ p=3&:\quad q\le 11 &&\Rightarrow 3,\\ p\ge 5&:\quad p^2q>100 &&\Rightarrow 0. \end{aligned}$$
Dolayısıyla \(A_{(2,1)}(100)=11\). Aynı budama ilkesi, daha uzun \((2,2,1)\) imzasının da \(N=100\) için imkansız olduğunu hemen gösterir; çünkü
$$2^2\cdot 3^2\cdot 5=180>100.$$
Tüm geçerli imzalar toplandığında \(C(100)=94\) elde edilir; bu da uygulamanın kontrol değeriyle aynıdır.
C++ uygulaması önce sıkıştırılmış bir asal sayma yapısı kurar. Böylece hem küçük \(x\) değerleri hem de \(\lfloor N/v\rfloor\) biçimindeki bölüm değerleri için \(\pi(x)\) sorguları hızlıca cevaplanabilir. Ayrıca gerekli olabilecek her asal için \(p^e\le N\) kuvvetleri önceden hazırlanır.
Daha sonra bir özyineleme, minimal asallar \(2,3,5,\dots\) üzerinden giderek tüm geçerli azalan üs imzalarını üretir. İkinci özyineleme ise sabit imza için asal dizilerini sayar. Kalan üs sayısı bire veya ikiye düştüğünde arama daha derine inmez; doğrudan asal sayma formüllerine geçilir. İlk üssün belirlediği bağımsız üst düzey dallar paralel çalıştırılır ve sonrasında toplanır.
Python ve Java uygulamaları aynı matematiği ayrı ayrı yazmaz. İkisi de aynı derlenmiş hesabı çalıştırır ve son sayısal cevabı ayrıştırır. Bu yüzden üç dilde de kullanılan yöntem aynıdır.
Maliyet için yalnızca \(N\)'ye bağlı basit bir kapalı form yoktur; çünkü süre, kaç üs imzasının fizibilite testlerini geçtiğine ve budamadan sonra kaç asal dalının kaldığına bağlıdır. Asal sayma ön işlemesi \(O(\sqrt{N})\) farklı argüman saklar, \(O(\sqrt{N})\) bellek kullanır ve işlem maliyeti yaklaşık olarak \(O(\sqrt{N}\log\log N)\) düzeyindedir.
Budamadan sonra kalan toplam özyinelemeli durum sayısına \(B(N)\) dersek toplam süre yaklaşık
$$O\!\left(\sqrt{N}\log\log N + B(N)\right)$$
olur. Uç dallar hızlı \(\pi(x)\) sorgularına indirildiği için, pratikte bu sayı \(1\)'den \(N\)'ye kadar her tam sayıyı denemekten çok daha küçüktür.
Escribamos un entero positivo \(n\gt 1\) como
$$n=\prod_{i=1}^{k} p_i^{e_i},\qquad p_1 \lt p_2 \lt \cdots \lt p_k,$$
con los primos en orden creciente. El problema 578 pide la función
$$C(N)=\#\left\{n\le N : e_1\ge e_2\ge \cdots \ge e_k\ge 1\right\},$$
contando también \(1\). Como \(N\) es muy grande, no se puede comprobar cada entero por fuerza bruta. La idea es contar primero los patrones de exponentes y, para cada patrón, contar cuántas elecciones de primos lo realizan.
Las implementaciones separan el problema en dos niveles: generar todas las firmas de exponentes no crecientes factibles y, después, contar las tuplas de primos compatibles con cada firma.
Cada entero válido \(n\gt 1\) determina una firma única
$$\lambda=(e_1,e_2,\dots,e_k),\qquad e_1\ge e_2\ge \cdots \ge e_k\ge 1.$$
Para una firma fija definimos
$$A_\lambda(N)=\#\left\{(p_1,\dots,p_k): p_1\lt \cdots \lt p_k,\ \prod_{i=1}^{k} p_i^{e_i}\le N\right\}.$$
Entonces
$$C(N)=1+\sum_{\lambda} A_\lambda(N),$$
donde el \(+1\) representa \(n=1\). Una firma solo es factible si incluso su realización mínima cabe bajo \(N\):
$$2^{e_1}3^{e_2}5^{e_3}\cdots p_k^{e_k}\le N.$$
Ese criterio es exactamente el que usa la recursión que enumera las firmas.
Sea \(p_1,p_2,\dots\) la sucesión de primos. Supongamos que ya se han fijado primos hasta \(p_i\), así que el siguiente primo elegido debe ser mayor que \(p_i\). Para una lista restante de exponentes \((f_1,\dots,f_r)\) y un límite restante \(L\), definimos
$$R(f_1,\dots,f_r;L,i)$$
como el número de elecciones estrictamente crecientes \(q_1\lt \cdots \lt q_r\), todas mayores que \(p_i\), tales que
$$q_1^{f_1}q_2^{f_2}\cdots q_r^{f_r}\le L.$$
La recurrencia es
$$R(f_1,\dots,f_r;L,i)=\sum_{j>i,\ p_j^{f_1}\le L} R(f_2,\dots,f_r;L/p_j^{f_1},j).$$
En particular, la contribución de una firma completa es
$$A_{(e_1,\dots,e_k)}(N)=R(e_1,\dots,e_k;N,0).$$
Si solo queda un exponente \(e\), el problema se convierte en contar primos:
$$R(e;L,i)=\max\left(0,\pi\left(\left\lfloor L^{1/e}\right\rfloor\right)-i\right).$$
Esto cuenta exactamente los primos \(q\) que vienen después de los primeros \(i\) primos y satisfacen \(q^e\le L\).
Si quedan dos exponentes \(e\ge f\), se obtiene
$$R(e,f;L,i)=\sum_{j>i,\ p_j^e\le L}\max\left(0,\pi\left(\left\lfloor (L/p_j^e)^{1/f}\right\rfloor\right)-j\right).$$
Eso evita expandir inútilmente todo el subárbol restante. La implementación en C++ también acelera especialmente los exponentes \(1,2,4,8\), porque en esos casos los límites se obtienen con raíces enteras exactas.
Para firmas largas, la mayoría de las ramas no puede funcionar. Si estamos probando \(p_j\) como siguiente primo para los exponentes restantes \((f_1,\dots,f_r)\), incluso la continuación más pequeña posible valdría
$$p_j^{f_1}p_{j+1}^{f_2}\cdots p_{j+r-1}^{f_r}.$$
Si este producto mínimo ya supera \(L\), ninguna elección posterior de \(p_j\) servirá, porque los primos posteriores son todavía mayores. Por eso la rama se corta inmediatamente.
Otra recursión genera las propias firmas. Se empieza con \(e_1\ge 1\) bajo la condición \(2^{e_1}\le N\). Para la posición siguiente se escoge \(e_2\) cumpliendo
$$1\le e_2\le e_1,\qquad 3^{e_2}\le N/2^{e_1}.$$
Luego se continúa usando \(5,7,11,\dots\) como los primos futuros más pequeños posibles. Cada vez que un prefijo \((e_1,\dots,e_t)\) es viable con esos primos mínimos, ese prefijo ya representa una firma real, así que su contribución \(A_{(e_1,\dots,e_t)}(N)\) se suma de inmediato. La condición \(e_{t+1}\le e_t\) garantiza que cada firma no creciente aparezca una sola vez.
Aquí contamos enteros de la forma \(p^2q\) con \(p\lt q\) y \(p^2q\le 100\). La fórmula es
$$A_{(2,1)}(100)=\sum_{p^2\le 100}\#\left\{q>p:\ q\le 100/p^2,\ q\text{ prime}\right\}.$$
Evaluando según el primer primo:
$$\begin{aligned} p=2&:\quad q\le 25 &&\Rightarrow 8,\\ p=3&:\quad q\le 11 &&\Rightarrow 3,\\ p\ge 5&:\quad p^2q>100 &&\Rightarrow 0. \end{aligned}$$
Por tanto \(A_{(2,1)}(100)=11\). La misma poda muestra de inmediato que la firma \((2,2,1)\) es imposible cuando \(N=100\), porque
$$2^2\cdot 3^2\cdot 5=180>100.$$
Al sumar todas las firmas factibles se obtiene \(C(100)=94\), en acuerdo con el punto de control de la implementación.
La implementación en C++ empieza construyendo una estructura comprimida para contar primos. Guarda suficiente información para responder rápidamente \(\pi(x)\) tanto en valores pequeños como en cocientes de la forma \(\lfloor N/v\rfloor\). También precalcula las potencias \(p^e\le N\) de los primos que pueden aparecer en la recursión.
Después, una recursión enumera todas las firmas no crecientes factibles usando \(2,3,5,\dots\) solo como test mínimo de viabilidad. Otra recursión cuenta, para una firma fija, las elecciones reales de primos. Cuando solo quedan uno o dos exponentes, el algoritmo cambia a fórmulas directas con \(\pi(x)\) en lugar de seguir expandiendo el árbol. Las ramas de nivel superior, determinadas por el primer exponente, son independientes y se procesan en paralelo antes de sumar sus resultados.
Las implementaciones en Python y Java no rehacen la matemática por separado. Ambas invocan el mismo cálculo compilado y extraen la respuesta numérica final, por lo que las tres versiones usan exactamente el mismo método.
No existe una fórmula cerrada sencilla solo en función de \(N\), porque el coste depende de cuántas firmas superan la prueba de viabilidad y de cuántas ramas de primos sobreviven a la poda. La fase de preprocesamiento para \(\pi(x)\) almacena \(O(\sqrt{N})\) argumentos distintos, usa \(O(\sqrt{N})\) memoria y tiene un coste aritmético cercano a \(O(\sqrt{N}\log\log N)\).
Si \(B(N)\) es el número total de estados recursivos que quedan tras la poda, entonces el tiempo total es aproximadamente
$$O\!\left(\sqrt{N}\log\log N + B(N)\right).$$
Como las ramas terminales se resuelven con consultas rápidas a \(\pi(x)\) en lugar de expandirse por completo, el valor práctico de \(B(N)\) es muy inferior al de una enumeración ingenua de todos los enteros hasta \(N\).
把一个正整数 \(n\gt 1\) 写成
$$n=\prod_{i=1}^{k} p_i^{e_i},\qquad p_1 \lt p_2 \lt \cdots \lt p_k,$$
其中素数按从小到大排列。题目要求计算
$$C(N)=\#\left\{n\le N : e_1\ge e_2\ge \cdots \ge e_k\ge 1\right\},$$
并且把 \(1\) 也计入结果。难点在于 \(N\) 非常大，无法逐个整数分解再检查指数是否单调。实现采用的真正思路是：先按指数模式分类，再对每一种模式统计有多少组递增素数可以产生它。
整个算法分成两层。第一层枚举所有可行的非增指数签名，第二层在固定签名下统计满足乘积上界的素数元组。
每个合法的 \(n\gt 1\) 都对应唯一的签名
$$\lambda=(e_1,e_2,\dots,e_k),\qquad e_1\ge e_2\ge \cdots \ge e_k\ge 1.$$
对固定签名定义
$$A_\lambda(N)=\#\left\{(p_1,\dots,p_k): p_1\lt \cdots \lt p_k,\ \prod_{i=1}^{k} p_i^{e_i}\le N\right\}.$$
于是总计数就是
$$C(N)=1+\sum_{\lambda} A_\lambda(N),$$
其中 \(+1\) 对应整数 \(1\)。一个签名是否可行，首先要看它的最小实现是否已经超过 \(N\)。最小实现就是把最小的素数依次代进去：
$$2^{e_1}3^{e_2}5^{e_3}\cdots p_k^{e_k}\le N.$$
如果这个最小乘积都不满足，那么任何更大的素数选择更不可能满足。这正是签名枚举时的可行性判据。
记全部素数为 \(p_1,p_2,\dots\)。设前面已经用到了不超过 \(p_i\) 的素数，因此下一次选择的素数必须大于 \(p_i\)。对剩余指数列表 \((f_1,\dots,f_r)\) 和剩余上界 \(L\)，定义
$$R(f_1,\dots,f_r;L,i)$$
表示严格递增的素数选择
$$q_1\lt q_2\lt \cdots \lt q_r,\qquad q_1,q_2,\dots,q_r>p_i,$$
并满足
$$q_1^{f_1}q_2^{f_2}\cdots q_r^{f_r}\le L$$
的方案数。这样就得到递推式
$$R(f_1,\dots,f_r;L,i)=\sum_{j>i,\ p_j^{f_1}\le L} R(f_2,\dots,f_r;L/p_j^{f_1},j).$$
因此完整签名 \((e_1,\dots,e_k)\) 的贡献正是
$$A_{(e_1,\dots,e_k)}(N)=R(e_1,\dots,e_k;N,0).$$
这个写法与程序的递归结构完全对应：每次固定当前这一位指数对应的素数，然后把剩余限制传给下一层。
如果只剩最后一个指数 \(e\)，问题立即退化成素数计数：
$$R(e;L,i)=\max\left(0,\pi\left(\left\lfloor L^{1/e}\right\rfloor\right)-i\right).$$
原因是显然的：只要某个素数 \(q\) 大于前面已经固定的那 \(i\) 个素数，并且满足 \(q^e\le L\)，它就构成一个合法选择。
如果还剩两个指数 \(e\ge f\)，则可以把最后两层合并成
$$R(e,f;L,i)=\sum_{j>i,\ p_j^e\le L}\max\left(0,\pi\left(\left\lfloor (L/p_j^e)^{1/f}\right\rfloor\right)-j\right).$$
这样就不必把每一对素数都展开到更深层去枚举。C++ 实现还对 \(1,2,4,8\) 这几种常见指数单独优化，因为对应的界可以通过整数平方根反复计算出来。
对于较长的签名，绝大多数递归分支其实从一开始就不可能成功。假设当前准备把 \(p_j\) 作为下一位素数，而剩余指数为 \((f_1,\dots,f_r)\)。即使采用最小可能的后续素数，得到的乘积也至少是
$$p_j^{f_1}p_{j+1}^{f_2}\cdots p_{j+r-1}^{f_r}.$$
如果这个最小乘积已经大于 \(L\)，那么后面任何更大的 \(p_j\) 都不可能成功，因为素数只会变大不会变小。程序在这里直接终止这一整段搜索，这个剪枝是性能的关键之一。
除了固定签名后的递归计数之外，程序还有一层递归专门负责生成签名本身。先选 \(e_1\ge 1\)，要求
$$2^{e_1}\le N.$$
然后选第二个指数 \(e_2\)，要求
$$1\le e_2\le e_1,\qquad 3^{e_2}\le N/2^{e_1}.$$
继续下去时，分别用 \(5,7,11,\dots\) 作为将来位置上最小可能出现的素数。只要某个前缀 \((e_1,\dots,e_t)\) 在这些最小素数下仍然可行，它就已经对应一个真正的签名，因此它的贡献 \(A_{(e_1,\dots,e_t)}(N)\) 可以立刻加入答案。由于每一步都要求新指数不超过上一个指数，所以每个非增签名恰好出现一次，不会重复也不会遗漏。
这一签名对应的数形如 \(p^2q\)，其中 \(p\lt q\) 且 \(p^2q\le 100\)。计数公式为
$$A_{(2,1)}(100)=\sum_{p^2\le 100}\#\left\{q>p:\ q\le 100/p^2,\ q\text{ prime}\right\}.$$
逐个考察第一个素数：
$$\begin{aligned} p=2&:\quad q\le 25 &&\Rightarrow 8,\\ p=3&:\quad q\le 11 &&\Rightarrow 3,\\ p\ge 5&:\quad p^2q>100 &&\Rightarrow 0. \end{aligned}$$
因此 \(A_{(2,1)}(100)=11\)。同一个剪枝原则还可以立刻说明更长的签名 \((2,2,1)\) 在 \(N=100\) 下根本不可能，因为它的最小实现就是
$$2^2\cdot 3^2\cdot 5=180>100.$$
把所有可行签名都加起来后，得到 \(C(100)=94\)，这与实现中的校验值一致。
C++ 实现首先构建一个压缩的素数计数结构。它不仅能回答较小 \(x\) 的 \(\pi(x)\)，也能快速回答很多形如 \(\lfloor N/v\rfloor\) 的商值对应的 \(\pi(x)\)。同时，程序还预先保存了所有可能在递归中用到的素数幂 \(p^e\le N\)。
随后，一层递归负责生成所有可行的非增指数签名，并用最小素数序列 \(2,3,5,\dots\) 做可行性测试；另一层递归在固定签名下统计真正的素数选择。当只剩一个或两个指数时，搜索不再继续向下展开，而是切换到直接的 \(\pi(x)\) 公式。由首个指数决定的顶层分支彼此独立，因此在 C++ 中会并行处理，最后再把部分结果相加。
Python 与 Java 版本并没有各自重新实现这套数学逻辑。它们调用的是同一份编译后的核心计算，然后只负责读取最后输出的数字答案。因此三种语言的结果和算法细节完全一致。
这个问题没有一个只依赖 \(N\) 的简洁闭式复杂度，因为搜索成本取决于有多少指数签名通过可行性检测，以及经过剪枝后还剩下多少递归状态。素数计数预处理需要存储 \(O(\sqrt{N})\) 个不同参数，空间复杂度是 \(O(\sqrt{N})\)，算术成本接近 \(O(\sqrt{N}\log\log N)\)。
如果把剪枝之后保留下来的递归状态总数记为 \(B(N)\)，那么总时间大致可以写成
$$O\!\left(\sqrt{N}\log\log N + B(N)\right).$$
由于大量尾部分支会直接变成快速的 \(\pi(x)\) 查询，而不是完整展开成深层搜索树，所以实际运行成本远小于从 \(1\) 到 \(N\) 的逐个枚举。
Пусть положительное число \(n\gt 1\) разложено в виде
$$n=\prod_{i=1}^{k} p_i^{e_i},\qquad p_1 \lt p_2 \lt \cdots \lt p_k,$$
где простые упорядочены по возрастанию. Требуется вычислить функцию
$$C(N)=\#\left\{n\le N : e_1\ge e_2\ge \cdots \ge e_k\ge 1\right\},$$
причем число \(1\) тоже входит в подсчет. Прямая проверка каждого \(n\le N\) невозможна, поэтому решение считает не сами числа по одному, а сначала шаблоны показателей, а затем количество наборов простых, реализующих каждый шаблон.
Алгоритм разбивается на два уровня: сначала перечисляются все допустимые невозрастающие сигнатуры показателей, затем для каждой сигнатуры подсчитываются подходящие возрастающие наборы простых чисел.
Каждому допустимому \(n\gt 1\) соответствует единственная сигнатура
$$\lambda=(e_1,e_2,\dots,e_k),\qquad e_1\ge e_2\ge \cdots \ge e_k\ge 1.$$
Для фиксированной сигнатуры введем
$$A_\lambda(N)=\#\left\{(p_1,\dots,p_k): p_1\lt \cdots \lt p_k,\ \prod_{i=1}^{k} p_i^{e_i}\le N\right\}.$$
Тогда
$$C(N)=1+\sum_{\lambda} A_\lambda(N),$$
где \(+1\) отвечает числу \(1\). Сигнатура вообще может встретиться только тогда, когда даже ее минимальная реализация не превосходит \(N\):
$$2^{e_1}3^{e_2}5^{e_3}\cdots p_k^{e_k}\le N.$$
Именно этот критерий минимального произведения используется при перечислении сигнатур.
Обозначим простые числа через \(p_1,p_2,\dots\). Предположим, что уже использованы простые не больше \(p_i\), значит следующий выбранный простой обязан быть больше \(p_i\). Для оставшегося списка показателей \((f_1,\dots,f_r)\) и остаточного ограничения \(L\) обозначим через
$$R(f_1,\dots,f_r;L,i)$$
число строго возрастающих выборов простых
$$q_1\lt q_2\lt \cdots \lt q_r,\qquad q_1,q_2,\dots,q_r>p_i,$$
удовлетворяющих неравенству
$$q_1^{f_1}q_2^{f_2}\cdots q_r^{f_r}\le L.$$
Тогда выполняется рекурсия
$$R(f_1,\dots,f_r;L,i)=\sum_{j>i,\ p_j^{f_1}\le L} R(f_2,\dots,f_r;L/p_j^{f_1},j).$$
Следовательно, вклад полной сигнатуры равен
$$A_{(e_1,\dots,e_k)}(N)=R(e_1,\dots,e_k;N,0).$$
Если остался только один показатель \(e\), задача превращается в подсчет простых:
$$R(e;L,i)=\max\left(0,\pi\left(\left\lfloor L^{1/e}\right\rfloor\right)-i\right).$$
Это число простых \(q\), которые идут после первых \(i\) простых и удовлетворяют \(q^e\le L\).
Если остаются два показателя \(e\ge f\), получаем
$$R(e,f;L,i)=\sum_{j>i,\ p_j^e\le L}\max\left(0,\pi\left(\left\lfloor (L/p_j^e)^{1/f}\right\rfloor\right)-j\right).$$
Такой переход резко ускоряет хвост рекурсии. В C++-реализации дополнительно выделены частые случаи \(1,2,4,8\), потому что соответствующие границы удобно вычислять точными целочисленными корнями.
Для длинных сигнатур большинство ветвей безнадежно с самого начала. Если следующим кандидатом является \(p_j\), а оставшиеся показатели равны \((f_1,\dots,f_r)\), то даже самое маленькое продолжение дало бы произведение
$$p_j^{f_1}p_{j+1}^{f_2}\cdots p_{j+r-1}^{f_r}.$$
Если оно уже превышает \(L\), никакой более поздний выбор \(p_j\) не сработает, потому что простые дальше только растут. Поэтому вся эта часть поиска отбрасывается сразу.
Отдельная рекурсия строит сами сигнатуры. Сначала выбирается \(e_1\ge 1\) так, чтобы
$$2^{e_1}\le N.$$
Далее выбирается \(e_2\) при условиях
$$1\le e_2\le e_1,\qquad 3^{e_2}\le N/2^{e_1}.$$
Затем используются \(5,7,11,\dots\) как наименьшие возможные простые в следующих позициях. Если некоторый префикс \((e_1,\dots,e_t)\) остается допустимым даже при этих минимальных простых, то он уже соответствует реальной сигнатуре, и его вклад \(A_{(e_1,\dots,e_t)}(N)\) можно немедленно добавить. Условие \(e_{t+1}\le e_t\) гарантирует, что каждая невозрастающая сигнатура появляется ровно один раз.
Здесь мы считаем числа вида \(p^2q\), где \(p\lt q\) и \(p^2q\le 100\). Формула имеет вид
$$A_{(2,1)}(100)=\sum_{p^2\le 100}\#\left\{q>p:\ q\le 100/p^2,\ q\text{ prime}\right\}.$$
Рассмотрим возможный первый простой:
$$\begin{aligned} p=2&:\quad q\le 25 &&\Rightarrow 8,\\ p=3&:\quad q\le 11 &&\Rightarrow 3,\\ p\ge 5&:\quad p^2q>100 &&\Rightarrow 0. \end{aligned}$$
Итак, \(A_{(2,1)}(100)=11\). Тем же критерием отсечения сразу видно, что сигнатура \((2,2,1)\) при \(N=100\) невозможна, поскольку
$$2^2\cdot 3^2\cdot 5=180>100.$$
После суммирования по всем допустимым сигнатурам получается \(C(100)=94\), что совпадает с проверочным значением реализации.
C++-реализация сначала строит сжатую структуру для подсчета простых. Она позволяет быстро получать значения \(\pi(x)\) как для малых \(x\), так и для чисел вида \(\lfloor N/v\rfloor\). Кроме того, заранее сохраняются все степени \(p^e\le N\) для тех простых, которые могут понадобиться в рекурсии.
После этого одна рекурсивная процедура перечисляет все допустимые невозрастающие сигнатуры, используя минимальные простые \(2,3,5,\dots\) только как тест выполнимости. Другая рекурсивная процедура для фиксированной сигнатуры считает реальные наборы простых. Когда остается один или два показателя, поиск переключается на прямые формулы с \(\pi(x)\) вместо дальнейшего раскрытия дерева. Верхние ветви, определяемые первым показателем, независимы и поэтому в C++ вычисляются параллельно, а затем суммируются.
Версии на Python и Java не реализуют эту математику заново. Они запускают ту же скомпилированную вычислительную часть и извлекают итоговый числовой ответ. Поэтому во всех трех языках используется один и тот же алгоритм.
Простой замкнутой формулы только через \(N\) здесь нет, потому что стоимость поиска определяется количеством сигнатур, прошедших проверку выполнимости, и числом ветвей по простым, переживших отсечение. Предобработка для \(\pi(x)\) хранит \(O(\sqrt{N})\) различных аргументов, использует \(O(\sqrt{N})\) памяти и по трудоемкости близка к \(O(\sqrt{N}\log\log N)\).
Если через \(B(N)\) обозначить число рекурсивных состояний после отсечения, то суммарное время можно оценить как
$$O\!\left(\sqrt{N}\log\log N + B(N)\right).$$
Поскольку хвостовые ветви заменяются быстрыми запросами \(\pi(x)\), а не полным разворачиванием поддеревьев, на практике это на порядки лучше, чем наивный перебор всех чисел до \(N\).
لنكتب عددا صحيحا موجبا \(n\gt 1\) بالشكل
$$n=\prod_{i=1}^{k} p_i^{e_i},\qquad p_1 \lt p_2 \lt \cdots \lt p_k,$$
حيث تُرتَّب الأعداد الأولية تصاعديا. المطلوب هو حساب
$$C(N)=\#\left\{n\le N : e_1\ge e_2\ge \cdots \ge e_k\ge 1\right\},$$
مع احتساب \(1\) أيضا. وبما أن \(N\) ضخم جدا، فلا يمكن فحص كل عدد على حدة. لذلك تعتمد الفكرة على عد الأنماط الممكنة للأسس أولا، ثم عد اختيارات الأعداد الأولية التي تحقق كل نمط.
الخوارزمية تنقسم إلى مستويين: أولا توليد جميع تواقيع الأسس غير المتزايدة الممكنة، ثم عد المتتاليات الأولية المتزايدة التي تحقق كل توقيع تحت القيد \(N\).
كل عدد صحيح صالح \(n\gt 1\) يحدد توقيعا وحيدا من الصورة
$$\lambda=(e_1,e_2,\dots,e_k),\qquad e_1\ge e_2\ge \cdots \ge e_k\ge 1.$$
ولكل توقيع ثابت نعرّف
$$A_\lambda(N)=\#\left\{(p_1,\dots,p_k): p_1\lt \cdots \lt p_k,\ \prod_{i=1}^{k} p_i^{e_i}\le N\right\}.$$
ومن ثم
$$C(N)=1+\sum_{\lambda} A_\lambda(N),$$
حيث تمثل \(+1\) العدد \(1\). ولا يكون التوقيع ممكنا إلا إذا كانت أصغر صورة له ما تزال لا تتجاوز \(N\):
$$2^{e_1}3^{e_2}5^{e_3}\cdots p_k^{e_k}\le N.$$
هذا الشرط هو أساس العودية التي تولد التواقيع.
لنرمز إلى الأعداد الأولية كلها بـ \(p_1,p_2,\dots\). إذا كنا قد استخدمنا الأعداد الأولية حتى \(p_i\)، فلا بد أن يكون العدد الأولي التالي أكبر من \(p_i\). وللقائمة المتبقية من الأسس \((f_1,\dots,f_r)\) والحد المتبقي \(L\)، نعرّف
$$R(f_1,\dots,f_r;L,i)$$
باعتباره عدد الاختيارات المتزايدة تماما
$$q_1\lt q_2\lt \cdots \lt q_r,\qquad q_1,q_2,\dots,q_r>p_i,$$
التي تحقق
$$q_1^{f_1}q_2^{f_2}\cdots q_r^{f_r}\le L.$$
فتكون العلاقة العودية
$$R(f_1,\dots,f_r;L,i)=\sum_{j>i,\ p_j^{f_1}\le L} R(f_2,\dots,f_r;L/p_j^{f_1},j).$$
إذن مساهمة التوقيع الكامل هي
$$A_{(e_1,\dots,e_k)}(N)=R(e_1,\dots,e_k;N,0).$$
إذا بقي أس واحد فقط \(e\)، تتحول المسألة مباشرة إلى عد الأعداد الأولية:
$$R(e;L,i)=\max\left(0,\pi\left(\left\lfloor L^{1/e}\right\rfloor\right)-i\right).$$
فهذا يساوي عدد الأعداد الأولية \(q\) التي تأتي بعد أول \(i\) أعداد أولية وتحقق \(q^e\le L\).
وإذا بقي أسّان \(e\ge f\)، نحصل على
$$R(e,f;L,i)=\sum_{j>i,\ p_j^e\le L}\max\left(0,\pi\left(\left\lfloor (L/p_j^e)^{1/f}\right\rfloor\right)-j\right).$$
وبذلك نتجنب التوسع الكامل في بقية الشجرة. كما أن تنفيذ C++ يعطي معالجة أسرع للحالات \(1,2,4,8\) لأن الحدود المقابلة تُستخرج بجذور صحيحة دقيقة.
في التواقيع الطويلة، أغلب الفروع غير ممكنة أصلا. فإذا كنا نختبر \(p_j\) كعدد أولي تال، وكانت الأسس المتبقية هي \((f_1,\dots,f_r)\)، فإن أصغر امتداد ممكن لا بد أن يكون
$$p_j^{f_1}p_{j+1}^{f_2}\cdots p_{j+r-1}^{f_r}.$$
إذا تجاوز هذا الناتج \(L\)، فلن ينجح أي اختيار لاحق لـ \(p_j\)، لأن الأعداد الأولية اللاحقة أكبر فقط. لذلك تُقطع هذه الجهة من البحث فورا، وهذا أحد أهم أسباب السرعة.
هناك عودية مستقلة تبني التواقيع نفسها. نبدأ باختيار \(e_1\ge 1\) بشرط
$$2^{e_1}\le N.$$
ثم نختار \(e_2\) بحيث
$$1\le e_2\le e_1,\qquad 3^{e_2}\le N/2^{e_1}.$$
ثم نتابع مع \(5,7,11,\dots\) بوصفها أصغر أعداد أولية ممكنة في المواضع التالية. وكلما كان المقدّم \((e_1,\dots,e_t)\) ممكنا حتى مع هذه الأعداد الأولية الدنيا، فهذا يعني أنه يعبّر بالفعل عن توقيع صالح، ولذلك تُضاف مساهمته \(A_{(e_1,\dots,e_t)}(N)\) مباشرة. والشرط \(e_{t+1}\le e_t\) يضمن ظهور كل توقيع غير متزايد مرة واحدة فقط بلا تكرار.
هنا نعد الأعداد من الشكل \(p^2q\) مع \(p\lt q\) و\(p^2q\le 100\). تصبح الصيغة
$$A_{(2,1)}(100)=\sum_{p^2\le 100}\#\left\{q>p:\ q\le 100/p^2,\ q\text{ prime}\right\}.$$
وبفحص العدد الأولي الأول نحصل على
$$\begin{aligned} p=2&:\quad q\le 25 &&\Rightarrow 8,\\ p=3&:\quad q\le 11 &&\Rightarrow 3,\\ p\ge 5&:\quad p^2q>100 &&\Rightarrow 0. \end{aligned}$$
إذن \(A_{(2,1)}(100)=11\). ويبين معيار الحذف نفسه فورا أن التوقيع الأطول \((2,2,1)\) غير ممكن عندما \(N=100\)، لأن أصغر تمثيل له هو
$$2^2\cdot 3^2\cdot 5=180>100.$$
وعند جمع جميع التواقيع الممكنة نحصل على \(C(100)=94\)، وهو نفس مقدار التحقق المستخدم في التنفيذ.
يبدأ تنفيذ C++ ببناء بنية مضغوطة لعد الأعداد الأولية. هذه البنية تسمح بالإجابة السريعة عن \(\pi(x)\) للقيم الصغيرة، وكذلك للقيم من الشكل \(\lfloor N/v\rfloor\). كما تُحسب مسبقا جميع القوى \(p^e\le N\) للأعداد الأولية التي قد تظهر أثناء العودية.
بعد ذلك توجد عودية أولى لتوليد جميع تواقيع الأسس غير المتزايدة الممكنة باستخدام \(2,3,5,\dots\) فقط لاختبار الإمكان. وتوجد عودية ثانية لعد اختيارات الأعداد الأولية لتوقيع ثابت. وعندما لا يبقى إلا أس واحد أو أسّان، يتحول التنفيذ إلى صيغ مباشرة تعتمد على \(\pi(x)\) بدلا من الاستمرار في توسيع الشجرة. أما الفروع العليا التي يحددها الأس الأول فهي مستقلة، ولذلك تُنفذ بالتوازي ثم تُجمع نتائجها.
تنفيذا Python وJava لا يعيدان كتابة المنهج الرياضي من الصفر، بل يشغّلان الحساب المترجم نفسه ثم يستخرجان الجواب العددي النهائي. لهذا فاللغات الثلاث تستخدم الطريقة الحسابية نفسها.
لا توجد صيغة مغلقة بسيطة تعتمد على \(N\) فقط، لأن الكلفة الحقيقية تتعلق بعدد التواقيع التي تنجو من اختبار الإمكان وعدد حالات العودية التي تبقى بعد الحذف المبكر. مرحلة التهيئة الخاصة بـ \(\pi(x)\) تخزن \(O(\sqrt{N})\) قيما مميزة، وتستهلك \(O(\sqrt{N})\) من الذاكرة، وتكلفتها الحسابية قريبة من \(O(\sqrt{N}\log\log N)\).
إذا رمزنا بعدد حالات العودية المتبقية بعد الحذف بـ \(B(N)\)، فإن الزمن الكلي يمكن تقديره تقريبا بـ
$$O\!\left(\sqrt{N}\log\log N + B(N)\right).$$
ولأن الفروع الطرفية تختزل إلى استعلامات سريعة لـ \(\pi(x)\) بدلا من التوسع الكامل، فإن الأداء العملي أفضل بكثير من فحص كل الأعداد حتى \(N\) واحدا واحدا.