For each nonnegative integer \(k\), let \(c_k\) be the natural density of positive integers \(n\) for which exactly \(k\) distinct primes satisfy \(p^2 \mid n\). Equivalently, if
$$\Omega_2(n)=\#\{p \text{ prime} : p^2 \mid n\},$$
then \(c_k\) is the density of the set \(\{n\ge 1 : \Omega_2(n)=k\}\). The problem asks for \(c_7\), written in normalized scientific notation with five significant digits.
The implementations treat each prime square event as one independent density contribution and accumulate the coefficient of degree \(7\) in an infinite Euler product.
Fix a prime \(p\). Among all positive integers, the density of multiples of \(p^2\) is
$$\frac{1}{p^2},$$
because exactly one residue class modulo \(p^2\) is divisible by \(p^2\). Therefore the density of integers not divisible by \(p^2\) is
$$1-\frac{1}{p^2}.$$
If we mark the event \(p^2 \mid n\) by a factor of \(z\), then prime \(p\) contributes the linear factor
$$\left(1-\frac{1}{p^2}\right)+\frac{z}{p^2}.$$
The constant term means “this prime does not contribute to \(\Omega_2(n)\),” while the coefficient of \(z\) means “this prime does contribute once.”
For a finite set of distinct primes \(S\), divisibility conditions by the squares \(\{p^2 : p\in S\}\) are independent at the density level. The reason is the Chinese remainder theorem: residue classes modulo
$$\prod_{p\in S} p^2$$
split cleanly into independent choices for each prime square modulus. Hence the truncated generating function is
$$F_S(z)=\prod_{p\in S}\left(1-\frac{1}{p^2}+\frac{z}{p^2}\right).$$
When this product is expanded, the coefficient of \(z^k\) is exactly the density of integers for which precisely \(k\) primes in \(S\) satisfy \(p^2 \mid n\).
Letting \(S\) grow through all primes gives
$$F(z)=\prod_p\left(1-\frac{1}{p^2}+\frac{z}{p^2}\right)=\sum_{k\ge 0} c_k z^k.$$
This product converges because
$$\sum_p \frac{1}{p^2}$$
converges. So each coefficient \(c_k\) is well defined. A useful sanity check is the degree-\(0\) coefficient:
$$c_0=\prod_p\left(1-\frac{1}{p^2}\right)=\frac{1}{\zeta(2)}=\frac{6}{\pi^2},$$
which is the classical density of squarefree integers. Problem 633 asks for the degree-\(7\) coefficient instead.
Suppose after processing some primes we have the truncated polynomial
$$C(z)=d_0+d_1 z+\cdots+d_7 z^7.$$
For the next prime \(p\), define
$$a_p=\frac{1}{p^2}, \qquad b_p=1-a_p.$$
Multiplying by the new factor \(b_p+a_p z\) gives
$$C(z)(b_p+a_p z).$$
Matching coefficients up to degree \(7\) yields
$$d_0' = d_0 b_p,$$
$$d_k' = d_k b_p + d_{k-1} a_p \qquad (1 \le k \le 7).$$
This is exactly the dynamic-programming update used in the implementations. The update must run from high degree down to low degree so that the old value of \(d_{k-1}\) is still available when degree \(k\) is updated.
The programs do not multiply over all primes literally. Instead they use every prime up to
$$P_{\max}=10^7.$$
This is numerically safe because the omitted tail is governed by the convergent series
$$\sum_{p>P_{\max}} \frac{1}{p^2}.$$
Each skipped prime contributes a factor extremely close to \(1\), so the resulting change in coefficients through degree \(7\) is far smaller than the requested five-significant-digit output. In other words, the infinite product is replaced by a finite product whose truncation error is below the display precision.
To see the mechanism concretely, pretend we only keep the primes \(2\) and \(3\). Then
$$\left(1-\frac{1}{2^2}+\frac{z}{2^2}\right)\left(1-\frac{1}{3^2}+\frac{z}{3^2}\right)=\left(\frac{3}{4}+\frac{z}{4}\right)\left(\frac{8}{9}+\frac{z}{9}\right).$$
Expanding gives
$$\frac{2}{3}+\frac{11}{36}z+\frac{1}{36}z^2.$$
So, with respect to the square divisibility events from only \(2^2\) and \(3^2\):
$$c_0^{(2,3)}=\frac{2}{3}, \qquad c_1^{(2,3)}=\frac{11}{36}, \qquad c_2^{(2,3)}=\frac{1}{36}.$$
The middle coefficient means that density \(\frac{11}{36}\) of integers are divisible by exactly one of \(4\) or \(9\). The full problem repeats this same multiplication across all primes and then reads off the coefficient of \(z^7\).
The C++, Python, and Java implementations all follow the same structure. First they generate every prime up to \(10^7\) using an odd-only sieve, which stores compositeness information only for odd numbers to reduce memory usage. Then they keep an array of eight floating-point coefficients representing the truncated polynomial
$$d_0+d_1 z+\cdots+d_7 z^7.$$
The array starts as
$$1+0z+0z^2+\cdots+0z^7,$$
because before processing any primes, the empty product equals \(1\).
For each prime \(p\), the implementation computes
$$a_p=\frac{1}{p^2}, \qquad b_p=1-\frac{1}{p^2},$$
and updates the coefficient array from degree \(7\) down to degree \(1\) using
$$d_k \leftarrow d_k b_p + d_{k-1} a_p,$$
followed by
$$d_0 \leftarrow d_0 b_p.$$
After the last prime, the entry at degree \(7\) is the numerical approximation to \(c_7\). The final step rescales that positive number into the form
$$m \times 10^e, \qquad 1 \le m < 10,$$
and rounds the mantissa to four digits after the decimal point, which is five significant digits overall.
Let \(P=10^7\) and \(K=7\). The prime sieve costs \(O(P \log\log P)\) time. The subsequent coefficient update costs \(O(K)\) per prime, so the dynamic-programming stage is
$$O(\pi(P)\,K).$$
Since \(K\) is fixed at \(7\), that stage is effectively linear in the number of generated primes. The coefficient array itself uses constant space \(O(K)\), while the sieve uses \(O(P)\) boolean storage, reduced in practice by storing only odd indices.
Für jede nichtnegative ganze Zahl \(k\) sei \(c_k\) die natürliche Dichte der positiven ganzen Zahlen \(n\), für die genau \(k\) verschiedene Primzahlen die Bedingung \(p^2 \mid n\) erfüllen. Äquivalent dazu definieren wir
$$\Omega_2(n)=\#\{p \text{ prim} : p^2 \mid n\}.$$
Dann ist \(c_k\) die Dichte der Menge \(\{n\ge 1 : \Omega_2(n)=k\}\). Gesucht ist \(c_7\), ausgegeben in normalisierter wissenschaftlicher Schreibweise mit fünf signifikanten Stellen.
Die Implementierungen betrachten für jede Primzahl separat das Ereignis „\(p^2\) teilt \(n\)“ und lesen anschließend den Koeffizienten von Grad \(7\) aus einem unendlichen Euler-Produkt ab.
Fixiere eine Primzahl \(p\). Unter allen positiven ganzen Zahlen ist die Dichte der Vielfachen von \(p^2\)
$$\frac{1}{p^2},$$
denn modulo \(p^2\) ist genau eine Restklasse durch \(p^2\) teilbar. Also ist die Dichte der Zahlen, die nicht durch \(p^2\) teilbar sind, gleich
$$1-\frac{1}{p^2}.$$
Markieren wir das Ereignis \(p^2 \mid n\) mit einer Potenz von \(z\), dann liefert die Primzahl \(p\) den linearen Faktor
$$\left(1-\frac{1}{p^2}\right)+\frac{z}{p^2}.$$
Der konstante Anteil bedeutet: diese Primzahl trägt nichts zu \(\Omega_2(n)\) bei. Der lineare Anteil bedeutet: diese Primzahl zählt genau einmal.
Für eine endliche Menge verschiedener Primzahlen \(S\) sind die Teilbarkeitsbedingungen bezüglich \(\{p^2 : p\in S\}\) auf Dichteebene unabhängig. Der Grund ist der chinesische Restsatz: Restklassen modulo
$$\prod_{p\in S} p^2$$
zerfallen in unabhängige Entscheidungen modulo jeder einzelnen Primzahlpotenz. Daher ist die abgeschnittene erzeugende Funktion
$$F_S(z)=\prod_{p\in S}\left(1-\frac{1}{p^2}+\frac{z}{p^2}\right).$$
Beim Ausmultiplizieren ist der Koeffizient von \(z^k\) genau die Dichte der Zahlen, für die unter den Primzahlen aus \(S\) genau \(k\) Bedingungen \(p^2 \mid n\) erfüllt sind.
Lässt man \(S\) über alle Primzahlen wachsen, erhält man
$$F(z)=\prod_p\left(1-\frac{1}{p^2}+\frac{z}{p^2}\right)=\sum_{k\ge 0} c_k z^k.$$
Dieses Produkt konvergiert, weil
$$\sum_p \frac{1}{p^2}$$
konvergiert. Also ist jeder Koeffizient \(c_k\) wohldefiniert. Ein nützlicher Kontrollwert ist der Koeffizient von Grad \(0\):
$$c_0=\prod_p\left(1-\frac{1}{p^2}\right)=\frac{1}{\zeta(2)}=\frac{6}{\pi^2},$$
also die klassische Dichte der quadratfreien Zahlen. In Problem 633 interessiert statt dessen der Koeffizient von Grad \(7\).
Angenommen, nach einigen Primzahlen liegt das abgeschnittene Polynom
$$C(z)=d_0+d_1 z+\cdots+d_7 z^7$$
vor. Für die nächste Primzahl \(p\) setzen wir
$$a_p=\frac{1}{p^2}, \qquad b_p=1-a_p.$$
Die Multiplikation mit dem neuen Faktor \(b_p+a_p z\) ergibt
$$C(z)(b_p+a_p z).$$
Durch Koeffizientenvergleich bis Grad \(7\) folgt
$$d_0' = d_0 b_p,$$
$$d_k' = d_k b_p + d_{k-1} a_p \qquad (1 \le k \le 7).$$
Genau diese Aktualisierung verwendet die dynamische Programmierung in den Implementierungen. Dabei muss man von hohen Graden nach unten iterieren, damit der alte Wert von \(d_{k-1}\) nicht zu früh überschrieben wird.
Die Programme multiplizieren nicht über alle Primzahlen explizit, sondern nur über alle Primzahlen bis
$$P_{\max}=10^7.$$
Das ist numerisch ausreichend, weil der weggelassene Schwanz durch die konvergente Reihe
$$\sum_{p>P_{\max}} \frac{1}{p^2}$$
kontrolliert wird. Jede übersprungene Primzahl liefert einen Faktor, der extrem nahe bei \(1\) liegt. Daher ist die Änderung der Koeffizienten bis Grad \(7\) deutlich kleiner als die geforderte Ausgabe mit fünf signifikanten Stellen.
Zur Veranschaulichung betrachten wir nur \(2\) und \(3\). Dann gilt
$$\left(1-\frac{1}{2^2}+\frac{z}{2^2}\right)\left(1-\frac{1}{3^2}+\frac{z}{3^2}\right)=\left(\frac{3}{4}+\frac{z}{4}\right)\left(\frac{8}{9}+\frac{z}{9}\right).$$
Ausmultipliziert ergibt das
$$\frac{2}{3}+\frac{11}{36}z+\frac{1}{36}z^2.$$
Bezogen nur auf die Quadrat-Teilbarkeitsereignisse \(4 \mid n\) und \(9 \mid n\) bedeutet das:
$$c_0^{(2,3)}=\frac{2}{3}, \qquad c_1^{(2,3)}=\frac{11}{36}, \qquad c_2^{(2,3)}=\frac{1}{36}.$$
Insbesondere haben also Dichte \(\frac{11}{36}\) genau eine der beiden Eigenschaften „durch \(4\) teilbar“ oder „durch \(9\) teilbar“. Das volle Problem wiederholt dieselbe Multiplikation über alle Primzahlen und liest am Ende den Koeffizienten von \(z^7\) ab.
Die C++-, Python- und Java-Implementierungen folgen alle demselben Aufbau. Zuerst erzeugen sie mit einem Sieb alle Primzahlen bis \(10^7\). Dabei werden nur ungerade Zahlen gespeichert, um Speicher zu sparen. Anschließend verwalten sie ein Feld mit acht Gleitkomma-Koeffizienten für das abgeschnittene Polynom
$$d_0+d_1 z+\cdots+d_7 z^7.$$
Zu Beginn steht dort
$$1+0z+0z^2+\cdots+0z^7,$$
denn vor der ersten Primzahl ist das leere Produkt gleich \(1\).
Für jede Primzahl \(p\) berechnet die Implementierung
$$a_p=\frac{1}{p^2}, \qquad b_p=1-\frac{1}{p^2},$$
und aktualisiert das Koeffizientenfeld von Grad \(7\) abwärts bis Grad \(1\) mit
$$d_k \leftarrow d_k b_p + d_{k-1} a_p,$$
danach folgt
$$d_0 \leftarrow d_0 b_p.$$
Nach der letzten Primzahl ist der Eintrag von Grad \(7\) die numerische Näherung an \(c_7\). Abschließend wird dieser positive Wert in die Form
$$m \times 10^e, \qquad 1 \le m < 10,$$
gebracht und die Mantisse auf vier Nachkommastellen gerundet, also auf insgesamt fünf signifikante Stellen.
Mit \(P=10^7\) und \(K=7\) kostet das Primzahlsieb \(O(P \log\log P)\) Zeit. Die anschließende Koeffizientenaktualisierung benötigt \(O(K)\) Arbeit pro Primzahl und damit insgesamt
$$O(\pi(P)\,K).$$
Da \(K=7\) konstant ist, ist diese Phase praktisch linear in der Anzahl der erzeugten Primzahlen. Das Koeffizientenfeld benötigt konstanten Speicher \(O(K)\); das Sieb braucht \(O(P)\) Booleanspeicher, in der Praxis halbiert durch die Speicherung nur ungerader Indizes.
Her \(k \ge 0\) için \(c_k\), tam olarak \(k\) farklı asal \(p\) için \(p^2 \mid n\) koşulunu sağlayan pozitif tamsayıların doğal yoğunluğu olsun. Başka bir deyişle
$$\Omega_2(n)=\#\{p \text{ asal} : p^2 \mid n\}$$
tanımlanırsa, \(c_k\) değeri \(\{n\ge 1 : \Omega_2(n)=k\}\) kümesinin yoğunluğudur. Problem, \(c_7\) değerini beş anlamlı basamaklı normalize bilimsel gösterimde istemektedir.
Uygulamalar, her asalın karesine bölünebilme olayını bağımsız bir yoğunluk katkısı olarak ele alır ve sonsuz bir Euler çarpımındaki \(z^7\) katsayısını hesaplar.
Sabit bir asal \(p\) alalım. Pozitif tamsayılar içinde \(p^2\)'nin katı olan sayıların yoğunluğu
$$\frac{1}{p^2}$$
olur; çünkü mod \(p^2\) altında yalnızca bir kalan sınıfı \(p^2\)'ye bölünür. Buna göre \(p^2\)'ye bölünmeyen sayıların yoğunluğu
$$1-\frac{1}{p^2}$$
olur. Eğer \(p^2 \mid n\) olayını bir \(z\) çarpanı ile işaretlersek, asal \(p\) şu doğrusal çarpanı üretir:
$$\left(1-\frac{1}{p^2}\right)+\frac{z}{p^2}.$$
Sabit terim “bu asal \(\Omega_2(n)\) sayımına katkı yapmıyor”, \(z\)'li terim ise “bu asal tam bir katkı yapıyor” anlamına gelir.
Sonlu bir \(S\) asal kümesi için \(\{p^2 : p\in S\}\) biçimindeki bölünebilme koşulları yoğunluk düzeyinde bağımsızdır. Bunun nedeni Çin kalan teoremidir: mod
$$\prod_{p\in S} p^2$$
altındaki kalan sınıfları, her asal karesi için bağımsız seçimlere ayrılır. Bu yüzden kesilmiş üreteç fonksiyon
$$F_S(z)=\prod_{p\in S}\left(1-\frac{1}{p^2}+\frac{z}{p^2}\right)$$
olur. Bu çarpım açıldığında \(z^k\)'nin katsayısı, \(S\) içindeki tam olarak \(k\) asal için \(p^2 \mid n\) olan sayıların yoğunluğunu verir.
\(S\) tüm asallara doğru büyütülünce
$$F(z)=\prod_p\left(1-\frac{1}{p^2}+\frac{z}{p^2}\right)=\sum_{k\ge 0} c_k z^k$$
elde edilir. Bu çarpım yakınsaktır; çünkü
$$\sum_p \frac{1}{p^2}$$
yakınsaktır. Dolayısıyla her \(c_k\) iyi tanımlıdır. Güzel bir kontrol noktası derece \(0\) katsayısıdır:
$$c_0=\prod_p\left(1-\frac{1}{p^2}\right)=\frac{1}{\zeta(2)}=\frac{6}{\pi^2},$$
yani squarefree sayıların klasik yoğunluğu. Bu problemde ise gereken katsayı derece \(7\)'dir.
Bazı asalları işledikten sonra elimizde
$$C(z)=d_0+d_1 z+\cdots+d_7 z^7$$
kesilmiş polinomu olsun. Sıradaki asal \(p\) için
$$a_p=\frac{1}{p^2}, \qquad b_p=1-a_p$$
tanımlarını yapalım. Yeni çarpan \(b_p+a_p z\) ile çarpınca
$$C(z)(b_p+a_p z)$$
elde edilir. Derece \(7\)'ye kadar katsayıları eşleştirince
$$d_0' = d_0 b_p,$$
$$d_k' = d_k b_p + d_{k-1} a_p \qquad (1 \le k \le 7)$$
çıkar. Uygulamadaki dinamik programlama tam olarak budur. Güncelleme yüksek dereceden aşağıya doğru yapılmalıdır; aksi halde \(d_{k-1}\)'in eski değeri erkenden ezilir.
Programlar tüm asallar üzerinde sonsuz çarpım yapmaz; bunun yerine
$$P_{\max}=10^7$$
sınırına kadar olan asalları kullanır. Bu yaklaşım sayısal olarak güvenlidir, çünkü dışarıda bırakılan kuyruk
$$\sum_{p>P_{\max}} \frac{1}{p^2}$$
yakınsak bir seridir ve çok küçüktür. Atlanan her asal, \(1\)'e son derece yakın bir çarpan getirir. Böylece derece \(7\)'ye kadar olan katsayılardaki hata, istenen beş anlamlı basamak hassasiyetinin çok altında kalır.
Mekanizmayı görmek için yalnızca \(2\) ve \(3\) asallarını kullanalım. O zaman
$$\left(1-\frac{1}{2^2}+\frac{z}{2^2}\right)\left(1-\frac{1}{3^2}+\frac{z}{3^2}\right)=\left(\frac{3}{4}+\frac{z}{4}\right)\left(\frac{8}{9}+\frac{z}{9}\right)$$
olur. Çarpımı açarsak
$$\frac{2}{3}+\frac{11}{36}z+\frac{1}{36}z^2$$
elde edilir. Yani yalnızca \(4\) ve \(9\)'a bölünebilme olaylarına bakıldığında
$$c_0^{(2,3)}=\frac{2}{3}, \qquad c_1^{(2,3)}=\frac{11}{36}, \qquad c_2^{(2,3)}=\frac{1}{36}$$
olur. Özellikle \(\frac{11}{36}\) yoğunluğa sahip sayılar tam olarak bir tanesini sağlar: ya \(4\) böler ya da \(9\) böler, ama ikisi birden değil. Gerçek problem bu çarpımı bütün asallar için sürdürüp sonunda \(z^7\) katsayısını okur.
C++, Python ve Java uygulamaları aynı akışı izler. Önce tek sayılar üzerinden çalışan bir asal eleği ile \(10^7\)'ye kadar tüm asallar üretilir; böylece bellek tüketimi azaltılır. Sonra
$$d_0+d_1 z+\cdots+d_7 z^7$$
kesilmiş polinomunu tutan sekiz elemanlı bir kayan nokta katsayı dizisi kullanılır. Başlangıçta bu dizi
$$1+0z+0z^2+\cdots+0z^7$$
şeklindedir; çünkü hiç asal işlenmeden önce boş çarpım \(1\)'dir.
Her asal \(p\) için uygulama
$$a_p=\frac{1}{p^2}, \qquad b_p=1-\frac{1}{p^2}$$
değerlerini hesaplar ve katsayıları derece \(7\)'den derece \(1\)'e doğru
$$d_k \leftarrow d_k b_p + d_{k-1} a_p$$
kuralıyla günceller. Ardından
$$d_0 \leftarrow d_0 b_p$$
uygulanır. Son asal işlendiğinde derece \(7\) girdisi \(c_7\)'nin sayısal yaklaşımıdır. Son adım, bu pozitif sayıyı
$$m \times 10^e, \qquad 1 \le m < 10$$
biçimine getirip mantissayı virgülden sonra dört basamağa yuvarlamaktır; böylece toplam beş anlamlı basamak elde edilir.
\(P=10^7\) ve \(K=7\) için asal eleği \(O(P \log\log P)\) zamanda çalışır. Sonraki katsayı güncelleme aşaması her asal başına \(O(K)\) iş yapar; toplam maliyet
$$O(\pi(P)\,K)$$
olur. \(K\) sabit \(7\) olduğundan bu aşama pratikte asal sayısına göre lineerdir. Katsayı dizisinin belleği \(O(K)\) sabittir; eleğin belleği ise \(O(P)\) düzeyindedir, fakat yalnızca tek indeksler saklandığı için pratikte daha küçüktür.
Para cada entero no negativo \(k\), sea \(c_k\) la densidad natural de los enteros positivos \(n\) para los cuales exactamente \(k\) primos distintos cumplen \(p^2 \mid n\). De forma equivalente, si definimos
$$\Omega_2(n)=\#\{p \text{ primo} : p^2 \mid n\},$$
entonces \(c_k\) es la densidad del conjunto \(\{n\ge 1 : \Omega_2(n)=k\}\). La tarea pide \(c_7\), expresado en notación científica normalizada con cinco cifras significativas.
Las implementaciones tratan cada condición \(p^2 \mid n\) como una contribución de densidad independiente y acumulan el coeficiente de grado \(7\) de un producto de Euler infinito.
Fijemos un primo \(p\). Entre todos los enteros positivos, la densidad de los múltiplos de \(p^2\) es
$$\frac{1}{p^2},$$
porque exactamente una clase de residuos módulo \(p^2\) es divisible por \(p^2\). Por tanto, la densidad de los enteros no divisibles por \(p^2\) es
$$1-\frac{1}{p^2}.$$
Si marcamos el evento \(p^2 \mid n\) con una potencia de \(z\), el primo \(p\) aporta el factor lineal
$$\left(1-\frac{1}{p^2}\right)+\frac{z}{p^2}.$$
El término constante significa “este primo no contribuye a \(\Omega_2(n)\)” y el término lineal significa “este primo contribuye exactamente una vez”.
Para un conjunto finito de primos distintos \(S\), las condiciones de divisibilidad por \(\{p^2 : p\in S\}\) son independientes a nivel de densidad. La razón es el teorema chino del resto: las clases de residuos módulo
$$\prod_{p\in S} p^2$$
se descomponen en elecciones independientes para cada módulo cuadrático. Por ello, la función generadora truncada es
$$F_S(z)=\prod_{p\in S}\left(1-\frac{1}{p^2}+\frac{z}{p^2}\right).$$
Al expandir este producto, el coeficiente de \(z^k\) es exactamente la densidad de enteros para los que precisamente \(k\) primos de \(S\) verifican \(p^2 \mid n\).
Cuando \(S\) crece hasta contener todos los primos, obtenemos
$$F(z)=\prod_p\left(1-\frac{1}{p^2}+\frac{z}{p^2}\right)=\sum_{k\ge 0} c_k z^k.$$
Este producto converge porque
$$\sum_p \frac{1}{p^2}$$
converge. Así, cada coeficiente \(c_k\) está bien definido. Una comprobación útil es el coeficiente de grado \(0\):
$$c_0=\prod_p\left(1-\frac{1}{p^2}\right)=\frac{1}{\zeta(2)}=\frac{6}{\pi^2},$$
que coincide con la densidad clásica de los enteros libres de cuadrados. El problema 633 pide, en cambio, el coeficiente de grado \(7\).
Supongamos que tras procesar algunos primos tenemos el polinomio truncado
$$C(z)=d_0+d_1 z+\cdots+d_7 z^7.$$
Para el siguiente primo \(p\), definimos
$$a_p=\frac{1}{p^2}, \qquad b_p=1-a_p.$$
Multiplicar por el nuevo factor \(b_p+a_p z\) produce
$$C(z)(b_p+a_p z).$$
Al igualar coeficientes hasta grado \(7\), se obtiene
$$d_0' = d_0 b_p,$$
$$d_k' = d_k b_p + d_{k-1} a_p \qquad (1 \le k \le 7).$$
Esta es exactamente la actualización de programación dinámica usada por las implementaciones. El recorrido debe hacerse de grado alto a grado bajo para no sobrescribir antes de tiempo el valor antiguo de \(d_{k-1}\).
Los programas no multiplican literalmente sobre todos los primos, sino solo sobre los primos hasta
$$P_{\max}=10^7.$$
Esto es suficiente numéricamente porque la cola omitida está controlada por la serie convergente
$$\sum_{p>P_{\max}} \frac{1}{p^2}.$$
Cada primo omitido aporta un factor extremadamente cercano a \(1\), así que la variación de los coeficientes hasta grado \(7\) queda muy por debajo de la precisión exigida de cinco cifras significativas.
Para ver el mecanismo en pequeño, conservemos solo los primos \(2\) y \(3\). Entonces
$$\left(1-\frac{1}{2^2}+\frac{z}{2^2}\right)\left(1-\frac{1}{3^2}+\frac{z}{3^2}\right)=\left(\frac{3}{4}+\frac{z}{4}\right)\left(\frac{8}{9}+\frac{z}{9}\right).$$
Al expandir, resulta
$$\frac{2}{3}+\frac{11}{36}z+\frac{1}{36}z^2.$$
Con respecto únicamente a los eventos \(4 \mid n\) y \(9 \mid n\), esto significa que
$$c_0^{(2,3)}=\frac{2}{3}, \qquad c_1^{(2,3)}=\frac{11}{36}, \qquad c_2^{(2,3)}=\frac{1}{36}.$$
El coeficiente central indica que una fracción \(\frac{11}{36}\) de los enteros es divisible por exactamente uno de \(4\) o \(9\). El problema completo repite esta misma multiplicación sobre todos los primos y luego toma el coeficiente de \(z^7\).
Las implementaciones en C++, Python y Java siguen la misma estrategia. Primero generan todos los primos hasta \(10^7\) mediante una criba que almacena solo números impares para ahorrar memoria. Después mantienen un arreglo de ocho coeficientes en coma flotante que representa el polinomio truncado
$$d_0+d_1 z+\cdots+d_7 z^7.$$
Ese arreglo comienza como
$$1+0z+0z^2+\cdots+0z^7,$$
porque antes de procesar ningún primo, el producto vacío vale \(1\).
Para cada primo \(p\), la implementación calcula
$$a_p=\frac{1}{p^2}, \qquad b_p=1-\frac{1}{p^2},$$
y actualiza el arreglo desde grado \(7\) hacia grado \(1\) con la regla
$$d_k \leftarrow d_k b_p + d_{k-1} a_p,$$
seguida de
$$d_0 \leftarrow d_0 b_p.$$
Tras el último primo, la entrada de grado \(7\) es la aproximación numérica de \(c_7\). Finalmente, ese valor positivo se reescala a la forma
$$m \times 10^e, \qquad 1 \le m < 10,$$
y la mantisa se redondea a cuatro decimales, lo que produce cinco cifras significativas en total.
Sea \(P=10^7\) y \(K=7\). La criba de primos cuesta \(O(P \log\log P)\) tiempo. Después, la actualización de coeficientes cuesta \(O(K)\) por primo, de modo que la fase dinámica total es
$$O(\pi(P)\,K).$$
Como \(K\) está fijado en \(7\), esta parte es efectivamente lineal en el número de primos generados. El arreglo de coeficientes usa espacio constante \(O(K)\), mientras que la criba usa \(O(P)\) almacenamiento booleano, reducido en la práctica al guardar solo índices impares.
对每个非负整数 \(k\)，设 \(c_k\) 为满足“恰好有 \(k\) 个不同素数 \(p\) 使得 \(p^2 \mid n\)”的正整数 \(n\) 的自然密度。也就是说，如果定义
$$\Omega_2(n)=\#\{p \text{ prime} : p^2 \mid n\},$$
那么 \(c_k\) 就是集合 \(\{n\ge 1 : \Omega_2(n)=k\}\) 的自然密度。题目要求求出 \(c_7\)，并以规范化科学计数法输出，保留五位有效数字。
三份实现都基于同一个想法：把每个素数平方的整除事件当成一个独立的密度因子，然后从一个无穷 Euler 乘积中提取 \(z^7\) 的系数。
固定一个素数 \(p\)。在所有正整数中，被 \(p^2\) 整除的数的密度是
$$\frac{1}{p^2},$$
因为模 \(p^2\) 的所有剩余类里，只有一个剩余类对应 \(p^2\) 的倍数。因此，不被 \(p^2\) 整除的密度就是
$$1-\frac{1}{p^2}.$$
如果我们用一个形式变量 \(z\) 来标记事件 \(p^2 \mid n\)，那么素数 \(p\) 对应的局部因子就是
$$\left(1-\frac{1}{p^2}\right)+\frac{z}{p^2}.$$
其中常数项表示“这个素数没有贡献到 \(\Omega_2(n)\)”，而 \(z\) 的系数表示“这个素数恰好贡献一次”。这里之所以只会贡献 \(0\) 或 \(1\)，是因为 \(\Omega_2(n)\) 统计的是满足 \(p^2 \mid n\) 的不同素数个数，而不是平方因子的重数。
设 \(S\) 是一个有限素数集合。对于集合 \(\{p^2 : p\in S\}\) 中的平方整除条件，它们在密度层面上是独立的。原因来自中国剩余定理：模
$$\prod_{p\in S} p^2$$
的剩余类，可以拆成各个模 \(p^2\) 的独立选择。因此，对应的截断生成函数为
$$F_S(z)=\prod_{p\in S}\left(1-\frac{1}{p^2}+\frac{z}{p^2}\right).$$
把这个乘积展开以后，\(z^k\) 的系数正好等于这样一类整数的密度：在 \(S\) 中，恰好有 \(k\) 个素数满足 \(p^2 \mid n\)。这一步把组合意义和密度意义直接连接起来。
让 \(S\) 逐渐扩大到所有素数，就得到
$$F(z)=\prod_p\left(1-\frac{1}{p^2}+\frac{z}{p^2}\right)=\sum_{k\ge 0} c_k z^k.$$
这个无穷乘积是收敛的，因为
$$\sum_p \frac{1}{p^2}$$
本身收敛，所以每个系数 \(c_k\) 都有良好的定义。一个非常有用的校验是常数项：
$$c_0=\prod_p\left(1-\frac{1}{p^2}\right)=\frac{1}{\zeta(2)}=\frac{6}{\pi^2}.$$
这正是平方自由数的经典自然密度。也就是说，问题 633 其实是在同一个 Euler 乘积里，不再读取常数项，而是读取 \(z^7\) 的系数。
假设已经处理完一部分素数，此时保存的截断多项式是
$$C(z)=d_0+d_1 z+\cdots+d_7 z^7.$$
对下一个素数 \(p\)，记
$$a_p=\frac{1}{p^2}, \qquad b_p=1-a_p.$$
新的多项式就是
$$C(z)(b_p+a_p z).$$
比较各次幂的系数，在最高只保留到 \(z^7\) 的前提下，可以得到
$$d_0' = d_0 b_p,$$
$$d_k' = d_k b_p + d_{k-1} a_p \qquad (1 \le k \le 7).$$
这就是实现中真正执行的动态规划更新。必须按次数从高到低更新，否则 \(d_{k-1}\) 会在还没有被更高次数使用之前就被新值覆盖掉。由于题目只需要 \(c_7\)，所以数组只保留 \(0\) 到 \(7\) 这八个系数即可。
程序没有真的把所有素数都乘进去，而是只处理到
$$P_{\max}=10^7.$$
这样做是可行的，因为被省略的尾项由收敛级数
$$\sum_{p>P_{\max}} \frac{1}{p^2}$$
控制。对于很大的素数 \(p\)，对应因子
$$1-\frac{1}{p^2}+\frac{z}{p^2}$$
与 \(1\) 的差异极小，所以这些尾部素数对低次数系数，尤其是次数不超过 \(7\) 的系数，只会带来远小于显示精度的改动。题目最终只要求五位有效数字，因此这种截断已经足够稳定。
为了把整个机制算清楚，我们先只保留两个素数 \(2\) 和 \(3\)。这时生成函数变成
$$\left(1-\frac{1}{2^2}+\frac{z}{2^2}\right)\left(1-\frac{1}{3^2}+\frac{z}{3^2}\right)=\left(\frac{3}{4}+\frac{z}{4}\right)\left(\frac{8}{9}+\frac{z}{9}\right).$$
把它展开，得到
$$\frac{2}{3}+\frac{11}{36}z+\frac{1}{36}z^2.$$
这表示如果我们只关心“是否被 \(4\) 整除”和“是否被 \(9\) 整除”这两个事件，那么：
$$c_0^{(2,3)}=\frac{2}{3}, \qquad c_1^{(2,3)}=\frac{11}{36}, \qquad c_2^{(2,3)}=\frac{1}{36}.$$
其中 \(\frac{11}{36}\) 的含义是：恰好满足两者之一的整数密度为 \(\frac{11}{36}\)。完整问题只不过是把同样的乘法过程从两个素数推广到全部素数，然后读取 \(z^7\) 的系数。
C++、Python 和 Java 三个实现的结构完全一致。第一步是用只存奇数下标的筛法生成所有不超过 \(10^7\) 的素数，这样可以明显减少内存占用。第二步是维护一个长度为 \(8\) 的浮点系数数组，用来表示截断多项式
$$d_0+d_1 z+\cdots+d_7 z^7.$$
初始状态是
$$1+0z+0z^2+\cdots+0z^7,$$
因为在还没有处理任何素数时，空乘积等于 \(1\)。
之后对每个素数 \(p\)，实现都会计算
$$a_p=\frac{1}{p^2}, \qquad b_p=1-\frac{1}{p^2},$$
并按照从高次到低次的顺序执行更新
$$d_k \leftarrow d_k b_p + d_{k-1} a_p,$$
最后再执行
$$d_0 \leftarrow d_0 b_p.$$
当最后一个素数处理完以后，次数 \(7\) 处的数组项就是 \(c_7\) 的数值近似。最后一步把这个正数重新缩放成
$$m \times 10^e, \qquad 1 \le m < 10,$$
并把尾数四舍五入到小数点后四位，也就是总共五位有效数字。
记 \(P=10^7\)，\(K=7\)。筛素数的时间复杂度为 \(O(P \log\log P)\)。随后每个素数只需要做 \(O(K)\) 次系数更新，因此动态规划部分的总复杂度为
$$O(\pi(P)\,K).$$
由于这里 \(K\) 固定为 \(7\)，所以这一部分对实际运行而言几乎就是按素数个数线性增长。系数数组本身只占常数空间 \(O(K)\)，而筛法需要 \(O(P)\) 级别的布尔存储，不过因为只记录奇数位置，常数因子更小。
Для каждого неотрицательного целого \(k\) пусть \(c_k\) обозначает натуральную плотность положительных целых чисел \(n\), для которых ровно \(k\) различных простых чисел удовлетворяют условию \(p^2 \mid n\). Эквивалентно можно ввести функцию
$$\Omega_2(n)=\#\{p \text{ prime} : p^2 \mid n\}.$$
Тогда \(c_k\) есть плотность множества \(\{n\ge 1 : \Omega_2(n)=k\}\). Нужно найти \(c_7\) и вывести его в нормализованной научной записи с пятью значащими цифрами.
Все реализации рассматривают каждое событие вида \(p^2 \mid n\) как отдельный независимый вклад в плотность и затем извлекают коэффициент при \(z^7\) из бесконечного произведения Эйлера.
Зафиксируем простое число \(p\). Плотность чисел, делящихся на \(p^2\), равна
$$\frac{1}{p^2},$$
потому что по модулю \(p^2\) ровно один класс вычетов делится на \(p^2\). Следовательно, плотность чисел, не делящихся на \(p^2\), равна
$$1-\frac{1}{p^2}.$$
Если отметить событие \(p^2 \mid n\) формальным множителем \(z\), то простое \(p\) вносит линейный фактор
$$\left(1-\frac{1}{p^2}\right)+\frac{z}{p^2}.$$
Свободный член означает, что данное простое не увеличивает \(\Omega_2(n)\), а коэффициент при \(z\) означает, что это простое учитывается ровно один раз.
Для конечного множества различных простых \(S\) условия делимости на \(\{p^2 : p\in S\}\) независимы на уровне плотностей. Это следует из китайской теоремы об остатках: классы вычетов по модулю
$$\prod_{p\in S} p^2$$
распадаются на независимые выборы по каждому модулю \(p^2\). Поэтому усеченная производящая функция имеет вид
$$F_S(z)=\prod_{p\in S}\left(1-\frac{1}{p^2}+\frac{z}{p^2}\right).$$
После раскрытия произведения коэффициент при \(z^k\) равен в точности плотности чисел, для которых среди простых из \(S\) ровно \(k\) условий \(p^2 \mid n\) выполняются.
Если расширять \(S\) до множества всех простых, получаем
$$F(z)=\prod_p\left(1-\frac{1}{p^2}+\frac{z}{p^2}\right)=\sum_{k\ge 0} c_k z^k.$$
Это произведение сходится, поскольку сходится ряд
$$\sum_p \frac{1}{p^2}.$$
Значит, каждый коэффициент \(c_k\) определен корректно. Удобная проверка - коэффициент при \(z^0\):
$$c_0=\prod_p\left(1-\frac{1}{p^2}\right)=\frac{1}{\zeta(2)}=\frac{6}{\pi^2},$$
то есть классическая плотность квадратсвободных чисел. В задаче 633 нужен не этот коэффициент, а коэффициент степени \(7\).
Предположим, что после обработки некоторого числа простых мы имеем усеченный полином
$$C(z)=d_0+d_1 z+\cdots+d_7 z^7.$$
Для следующего простого \(p\) введем обозначения
$$a_p=\frac{1}{p^2}, \qquad b_p=1-a_p.$$
После умножения на новый фактор \(b_p+a_p z\) получаем
$$C(z)(b_p+a_p z).$$
Сравнение коэффициентов до степени \(7\) дает формулы
$$d_0' = d_0 b_p,$$
$$d_k' = d_k b_p + d_{k-1} a_p \qquad (1 \le k \le 7).$$
Именно это соотношение используется в динамическом обновлении коэффициентов. Обход должен идти от больших степеней к меньшим, иначе старое значение \(d_{k-1}\) будет испорчено слишком рано.
Программы не перемножают все простые буквально, а используют только простые до
$$P_{\max}=10^7.$$
Это оправдано численно, потому что отброшенный хвост контролируется сходящимся рядом
$$\sum_{p>P_{\max}} \frac{1}{p^2}.$$
Каждое пропущенное простое дает множитель, чрезвычайно близкий к \(1\). Поэтому изменение коэффициентов до степени \(7\) оказывается намного меньше точности итогового вывода, где требуется только пять значащих цифр.
Чтобы увидеть механику на малом примере, оставим только простые \(2\) и \(3\). Тогда
$$\left(1-\frac{1}{2^2}+\frac{z}{2^2}\right)\left(1-\frac{1}{3^2}+\frac{z}{3^2}\right)=\left(\frac{3}{4}+\frac{z}{4}\right)\left(\frac{8}{9}+\frac{z}{9}\right).$$
После раскрытия получаем
$$\frac{2}{3}+\frac{11}{36}z+\frac{1}{36}z^2.$$
То есть, если учитывать только события \(4 \mid n\) и \(9 \mid n\), имеем
$$c_0^{(2,3)}=\frac{2}{3}, \qquad c_1^{(2,3)}=\frac{11}{36}, \qquad c_2^{(2,3)}=\frac{1}{36}.$$
Средний коэффициент означает, что плотность чисел, делящихся ровно на одно из \(4\) и \(9\), равна \(\frac{11}{36}\). Полная задача делает ту же самую операцию для всех простых и затем считывает коэффициент при \(z^7\).
Реализации на C++, Python и Java устроены одинаково. Сначала они строят список всех простых до \(10^7\) с помощью решета, хранящего информацию только для нечетных чисел, чтобы уменьшить память. Затем поддерживается массив из восьми вещественных коэффициентов, представляющий усеченный полином
$$d_0+d_1 z+\cdots+d_7 z^7.$$
Начальное состояние массива равно
$$1+0z+0z^2+\cdots+0z^7,$$
потому что пустое произведение равно \(1\).
Для каждого простого \(p\) реализация вычисляет
$$a_p=\frac{1}{p^2}, \qquad b_p=1-\frac{1}{p^2},$$
и затем обновляет коэффициенты от степени \(7\) вниз до степени \(1\) по правилу
$$d_k \leftarrow d_k b_p + d_{k-1} a_p,$$
после чего выполняет
$$d_0 \leftarrow d_0 b_p.$$
После обработки последнего простого элемент степени \(7\) является численным приближением к \(c_7\). Финальный этап переводит это положительное число в вид
$$m \times 10^e, \qquad 1 \le m < 10,$$
и округляет мантиссу до четырех знаков после запятой, то есть до пяти значащих цифр всего.
Пусть \(P=10^7\) и \(K=7\). Решето простых требует \(O(P \log\log P)\) времени. После этого на каждый простой приходится \(O(K)\) операций обновления коэффициентов, так что полная стоимость динамической части равна
$$O(\pi(P)\,K).$$
Поскольку \(K\) фиксировано и равно \(7\), эта фаза практически линейна по числу найденных простых. Массив коэффициентов использует постоянную память \(O(K)\), а решето требует \(O(P)\) булевой памяти, причем на практике константа уменьшена за счет хранения только нечетных индексов.
لكل عدد صحيح غير سالب \(k\)، نرمز بـ \(c_k\) إلى الكثافة الطبيعية للأعداد الصحيحة الموجبة \(n\) التي تحقق أن هناك بالضبط \(k\) أعداد أولية مختلفة \(p\) بحيث \(p^2 \mid n\). وبصياغة مكافئة، إذا عرفنا
$$\Omega_2(n)=\#\{p \text{ prime} : p^2 \mid n\},$$
فإن \(c_k\) هي كثافة المجموعة \(\{n\ge 1 : \Omega_2(n)=k\}\). المطلوب هو حساب \(c_7\) وكتابته بصيغة علمية معيارية مع خمس خانات معنوية.
تعتمد جميع التطبيقات على الفكرة نفسها: كل حدث من الشكل \(p^2 \mid n\) يعطي مساهمة كثافة مستقلة، ثم نأخذ معامل \(z^7\) من حاصل ضرب أويلر لا نهائي.
ثبّت عددًا أوليًا \(p\). بين جميع الأعداد الصحيحة الموجبة، كثافة الأعداد القابلة للقسمة على \(p^2\) هي
$$\frac{1}{p^2},$$
لأن هناك فئة بواقي واحدة فقط modulo \(p^2\) تمثل مضاعفات \(p^2\). إذن كثافة الأعداد غير القابلة للقسمة على \(p^2\) هي
$$1-\frac{1}{p^2}.$$
إذا استخدمنا المتغير الشكلي \(z\) لتمييز الحدث \(p^2 \mid n\)، فإن هذا الأولي يساهم بالعامل الخطي
$$\left(1-\frac{1}{p^2}\right)+\frac{z}{p^2}.$$
الحد الثابت يعني أن هذا الأولي لا يضيف شيئًا إلى \(\Omega_2(n)\)، أما معامل \(z\) فيعني أن هذا الأولي يُحسب مرة واحدة.
إذا أخذنا مجموعة منتهية \(S\) من الأعداد الأولية المختلفة، فإن شروط القسمة على \(\{p^2 : p\in S\}\) تكون مستقلة على مستوى الكثافات. السبب هو مبرهنة البواقي الصينية: فئات البواقي modulo
$$\prod_{p\in S} p^2$$
تنفصل إلى اختيارات مستقلة لكل مربع أولي على حدة. لذلك تكون الدالة المولدة المقطوعة
$$F_S(z)=\prod_{p\in S}\left(1-\frac{1}{p^2}+\frac{z}{p^2}\right).$$
وعند توسيع هذا الحاصل، فإن معامل \(z^k\) يساوي بالضبط كثافة الأعداد التي تحقق أن عدد الشروط \(p^2 \mid n\) المحققة داخل المجموعة \(S\) يساوي \(k\).
عندما نسمح للمجموعة \(S\) بأن تكبر حتى تشمل جميع الأعداد الأولية، نحصل على
$$F(z)=\prod_p\left(1-\frac{1}{p^2}+\frac{z}{p^2}\right)=\sum_{k\ge 0} c_k z^k.$$
هذا الحاصل متقارب لأن
$$\sum_p \frac{1}{p^2}$$
متقاربة. لذلك يكون كل معامل \(c_k\) معرفًا تعريفًا صحيحًا. ومن الاختبارات المفيدة الحد الثابت:
$$c_0=\prod_p\left(1-\frac{1}{p^2}\right)=\frac{1}{\zeta(2)}=\frac{6}{\pi^2},$$
وهو الكثافة الكلاسيكية للأعداد الخالية من المربعات. أما هذه المسألة فتريد معامل الدرجة \(7\) بدلًا من ذلك.
افترض أننا بعد معالجة بعض الأعداد الأولية نملك كثير الحدود المقطوع
$$C(z)=d_0+d_1 z+\cdots+d_7 z^7.$$
وللأولي التالي \(p\) نعرّف
$$a_p=\frac{1}{p^2}, \qquad b_p=1-a_p.$$
عند الضرب بالعامل الجديد \(b_p+a_p z\) نحصل على
$$C(z)(b_p+a_p z).$$
وبمقارنة المعاملات حتى الدرجة \(7\) نجد
$$d_0' = d_0 b_p,$$
$$d_k' = d_k b_p + d_{k-1} a_p \qquad (1 \le k \le 7).$$
هذه هي بالضبط علاقة البرمجة الديناميكية المستخدمة في التنفيذ. ويجب تنفيذ التحديث من الدرجات العليا إلى الدنيا حتى لا يتم الكتابة فوق القيمة القديمة لـ \(d_{k-1}\) قبل استخدامها.
البرامج لا تضرب على جميع الأعداد الأولية حرفيًا، بل تكتفي بجميع الأوليات حتى
$$P_{\max}=10^7.$$
وهذا كافٍ عدديًا لأن الذيل المحذوف تحكمه السلسلة المتقاربة
$$\sum_{p>P_{\max}} \frac{1}{p^2}.$$
كل أولي محذوف يضيف عاملًا قريبًا جدًا من \(1\)، وبالتالي فإن تأثيره في المعاملات حتى الدرجة \(7\) أصغر بكثير من دقة الإخراج المطلوبة، وهي خمس خانات معنوية فقط.
لرؤية الآلية بصورة ملموسة، لنحتفظ فقط بالأوليين \(2\) و\(3\). عندئذ يصبح حاصل الضرب
$$\left(1-\frac{1}{2^2}+\frac{z}{2^2}\right)\left(1-\frac{1}{3^2}+\frac{z}{3^2}\right)=\left(\frac{3}{4}+\frac{z}{4}\right)\left(\frac{8}{9}+\frac{z}{9}\right).$$
وبالتوسيع نحصل على
$$\frac{2}{3}+\frac{11}{36}z+\frac{1}{36}z^2.$$
أي أنه إذا كنا نهتم فقط بحدثي \(4 \mid n\) و\(9 \mid n\)، فإن
$$c_0^{(2,3)}=\frac{2}{3}, \qquad c_1^{(2,3)}=\frac{11}{36}, \qquad c_2^{(2,3)}=\frac{1}{36}.$$
والمعامل الأوسط يعني أن كثافة الأعداد التي تقبل القسمة على واحد فقط من \(4\) أو \(9\) تساوي \(\frac{11}{36}\). المسألة الكاملة لا تفعل إلا تكرار الضرب نفسه على جميع الأوليات ثم قراءة معامل \(z^7\).
تتبع تطبيقات C++ وPython وJava البنية نفسها. أولًا يتم توليد جميع الأعداد الأولية حتى \(10^7\) باستعمال منخل يخزن معلومات الأعداد الفردية فقط لتقليل الذاكرة. بعد ذلك يُحافَظ على مصفوفة من ثمانية معاملات عشرية تمثل كثير الحدود المقطوع
$$d_0+d_1 z+\cdots+d_7 z^7.$$
وتبدأ هذه المصفوفة بالحالة
$$1+0z+0z^2+\cdots+0z^7,$$
لأن حاصل الضرب الفارغ يساوي \(1\).
لكل أولي \(p\)، يحسب التنفيذ
$$a_p=\frac{1}{p^2}, \qquad b_p=1-\frac{1}{p^2},$$
ثم يحدّث المعاملات من الدرجة \(7\) نزولًا إلى الدرجة \(1\) وفق العلاقة
$$d_k \leftarrow d_k b_p + d_{k-1} a_p,$$
ثم ينفذ بعد ذلك
$$d_0 \leftarrow d_0 b_p.$$
بعد آخر أولي، تكون الخانة ذات الدرجة \(7\) هي التقريب العددي لـ \(c_7\). وفي النهاية يعاد تمثيل هذا العدد الموجب على الصورة
$$m \times 10^e, \qquad 1 \le m < 10,$$
ثم تُقرَّب المانتيسا إلى أربع خانات بعد الفاصلة، أي إلى خمس خانات معنوية إجمالًا.
إذا وضعنا \(P=10^7\) و\(K=7\)، فإن بناء منخل الأوليات يستغرق زمنًا مقداره \(O(P \log\log P)\). أما مرحلة تحديث المعاملات فتأخذ \(O(K)\) لكل أولي، وبالتالي يكون مجموعها
$$O(\pi(P)\,K).$$
وبما أن \(K\) ثابت ويساوي \(7\)، فهذه المرحلة تكاد تكون خطية في عدد الأوليات المولدة. مصفوفة المعاملات نفسها تحتاج إلى مساحة ثابتة \(O(K)\)، بينما يحتاج المنخل إلى مساحة من رتبة \(O(P)\) من القيم المنطقية، مع تقليل العامل الثابت عمليًا لأن التخزين يقتصر على الأعداد الفردية.