Project Euler 187 asks for the number of composite integers \(n \lt 10^8\) that have exactly two prime factors when multiplicity is counted. In other words, we must count the semiprimes below the limit, including prime squares such as \(4=2^2\), \(9=3^2\), and \(25=5^2\).
Instead of factoring every integer below the limit, the solution counts prime pairs directly. If a number is semiprime, then it can be written as \(n=pq\) with primes \(p \le q\). Once that order is enforced, every valid semiprime corresponds to exactly one pair \((p,q)\).
Let \(L\) denote the upper bound. The target quantity is
$$S(L)=\#\{n \lt L : n=pq,\ p \le q,\ p,q\text{ prime}\}.$$
The key idea is to choose the smaller prime first and then count how many larger primes can be paired with it.
Every semiprime has a factorization \(n=pq\) with primes \(p \le q\). Because the smaller factor is placed first, the representation is unique. So the whole problem becomes a counting problem on ordered prime pairs satisfying
$$pq \lt L,\qquad p \le q.$$
This removes the need for individual factorization. We never inspect a candidate integer and ask whether it is semiprime; we build exactly the semiprimes we want by counting admissible pairs.
In every valid pair, the smaller prime satisfies \(p \ge 2\). Therefore the larger prime must satisfy
$$q \le \left\lfloor\frac{L-1}{2}\right\rfloor.$$
Indeed, if \(q\) were larger than \((L-1)/2\), then even the smallest possible partner \(p=2\) would give \(2q \ge L\). So every prime that can appear in any valid semiprime lies in the interval up to
$$Q_{\max}=\left\lfloor\frac{L-1}{2}\right\rfloor.$$
That is exactly why the implementations sieve primes only up to \(Q_{\max}\) rather than all the way to \(L\).
Fix a prime \(p\) and insist that it is the smaller factor. Then \(q\) must satisfy two conditions: it must be at least \(p\), and the product must stay below \(L\). So the admissible range is
$$p \le q \le \left\lfloor\frac{L-1}{p}\right\rfloor.$$
If \(\pi(x)\) denotes the prime-counting function, then the number of valid partners for this one \(p\) is
$$\pi\!\left(\left\lfloor\frac{L-1}{p}\right\rfloor\right)-\pi(p)+1.$$
The implementations do not construct a separate array of \(\pi(x)\) values. They get the same count by binary-searching the sorted prime list and measuring how many primes in the suffix beginning at \(p\) stay below the upper bound.
For a fixed smaller factor \(p\), the smallest possible partner is \(q=p\). If even \(p^2\) is already too large, then no larger prime \(q\) can work. Therefore only primes satisfying
$$p^2 \lt L$$
need to be processed. This explains the early termination condition used by all three implementations.
The problem statement says there are 10 semiprimes below 30. The counting method reproduces that result immediately.
Here
$$Q_{\max}=\left\lfloor\frac{29}{2}\right\rfloor=14,$$
so the relevant primes are \(2,3,5,7,11,13\).
For \(p=2\), we get \(q \le \lfloor 29/2 \rfloor = 14\), so the valid partners are \(2,3,5,7,11,13\). That contributes 6 semiprimes:
$$2\cdot2,\ 2\cdot3,\ 2\cdot5,\ 2\cdot7,\ 2\cdot11,\ 2\cdot13.$$
For \(p=3\), the bound is \(q \le \lfloor 29/3 \rfloor = 9\), so the valid partners are \(3,5,7\). That contributes 3 more:
$$3\cdot3,\ 3\cdot5,\ 3\cdot7.$$
For \(p=5\), the bound is \(q \le \lfloor 29/5 \rfloor = 5\), so only \(5\cdot5\) remains. At \(p=7\), we already have \(7^2=49 \ge 30\), so the process stops. The total is
$$6+3+1=10,$$
matching the sample list \(4,6,9,10,14,15,21,22,25,26\).
If \(p_1 \lt p_2 \lt \cdots \lt p_m\) are the primes up to \(Q_{\max}\), then the answer can be written as
$$S(L)=\sum_{\substack{1 \le i \le m\\ p_i^2 \lt L}} \#\left\{j \ge i : p_j \le \left\lfloor\frac{L-1}{p_i}\right\rfloor\right\}.$$
This formula is exactly what the implementations evaluate. The only tasks are generating the ordered prime list once and then locating the right endpoint for each \(p_i\).
The C++, Python, and Java implementations all begin with a sieve of Eratosthenes up to \(Q_{\max}\). The sieve invariant is the standard one: when the algorithm reaches a prime \(r\), every composite smaller than \(r^2\) has already been marked, so it is enough to strike out multiples starting from \(r^2\).
Once the prime list is available, the implementation scans that list from left to right. The current prime is treated as the smaller factor \(p\). If \(p^2 \ge L\), the loop ends immediately; otherwise the code computes the bound \(\left\lfloor\frac{L-1}{p}\right\rfloor\) and performs an upper-bound search in the sorted prime list.
Starting that search from the current index rather than from the beginning is the implementation-level version of enforcing \(q \ge p\). That single detail ensures that mixed products such as \(2\cdot13\) and \(13\cdot2\) are not both counted, while squares such as \(5\cdot5\) are still included. The three languages differ only in surface syntax: one uses a standard library upper-bound operation, one uses built-in list bisection, and one performs the same upper-bound search manually over an array.
Let \(Q_{\max}=\left\lfloor\frac{L-1}{2}\right\rfloor\). The sieve phase costs
$$O\!\left(Q_{\max}\log\log Q_{\max}\right)$$
time and
$$O(Q_{\max})$$
memory.
The second phase processes only the primes below \(\sqrt{L}\), so it performs \(\pi(\sqrt{L})\) iterations, each with one binary search in the prime list. That contributes
$$O\!\left(\pi(\sqrt{L})\log \pi(Q_{\max})\right)$$
additional time. For the Euler limit \(L=10^8\), this post-sieve work is much smaller than factoring every integer below the limit, and the sieve remains the dominant cost.
Project Euler 187 fragt nach der Anzahl zusammengesetzter Zahlen \(n \lt 10^8\), die genau zwei Primfaktoren besitzen, wobei Vielfachheiten mitgezählt werden. Gesucht sind also die Halbprimzahlen unterhalb der Schranke; Quadrate wie \(4=2^2\), \(9=3^2\) und \(25=5^2\) gehören ausdrücklich dazu.
Der entscheidende Perspektivwechsel lautet: Nicht jede Zahl unterhalb der Grenze wird faktorisiert, sondern die zulässigen Primzahlpaare werden direkt gezählt. Jede Halbprimzahl hat die Form \(n=pq\) mit Primzahlen \(p \le q\), und mit dieser Reihenfolge wird jede Zahl genau einmal erfasst.
Sei \(L\) die obere Schranke. Dann ist die gesuchte Anzahl
$$S(L)=\#\{n \lt L : n=pq,\ p \le q,\ p,q\text{ prime}\}.$$
Die gesamte Herleitung basiert darauf, zuerst den kleineren Primfaktor festzulegen und dann zu zählen, wie viele größere Primzahlen noch als Partner in Frage kommen.
Jede Halbprimzahl besitzt eine Darstellung \(n=pq\) mit Primzahlen \(p \le q\). Wegen dieser Ordnung ist die Darstellung eindeutig. Damit reduziert sich die Aufgabe auf das Zählen aller Primzahlpaare mit
$$pq \lt L,\qquad p \le q.$$
Das ist genau die richtige Zustandsmenge: keine gültige Zahl fehlt, und keine wird doppelt gezählt.
In jedem gültigen Paar gilt \(p \ge 2\). Daher muss für den größeren Faktor gelten
$$q \le \left\lfloor\frac{L-1}{2}\right\rfloor.$$
Denn wäre \(q\) größer, dann würde schon mit dem kleinsten möglichen Partner \(p=2\) das Produkt die Schranke erreichen oder überschreiten. Also genügt es, alle Primzahlen bis
$$Q_{\max}=\left\lfloor\frac{L-1}{2}\right\rfloor$$
zu erzeugen. Genau deshalb arbeiten die Implementierungen mit einem Sieb bis \(Q_{\max}\) und nicht bis \(L\).
Ist \(p\) als kleinerer Faktor fest gewählt, dann muss \(q\) gleichzeitig \(q \ge p\) und \(pq \lt L\) erfüllen. Das ergibt den Bereich
$$p \le q \le \left\lfloor\frac{L-1}{p}\right\rfloor.$$
Mit der Primzahlzählfunktion \(\pi(x)\) ist die Anzahl solcher Partner
$$\pi\!\left(\left\lfloor\frac{L-1}{p}\right\rfloor\right)-\pi(p)+1.$$
Im Code erscheint diese Formel nicht als separates \(\pi\)-Array. Stattdessen wird in der sortierten Primzahlliste per Binärsuche der letzte zulässige Index gefunden; die Länge des passenden Suffix-Abschnitts ist dann genau der gesuchte Beitrag.
Der kleinste Partner zu einem festen \(p\) ist \(q=p\). Falls bereits
$$p^2 \ge L,$$
dann kann kein größeres \(q\) mehr funktionieren. Deshalb müssen nur Primzahlen mit \(p^2 \lt L\) betrachtet werden. Diese Beobachtung erklärt die Abbruchbedingung aller drei Implementierungen.
Für die Beispielgrenze aus der Aufgabenstellung ist
$$Q_{\max}=\left\lfloor\frac{29}{2}\right\rfloor=14,$$
also sind die relevanten Primzahlen \(2,3,5,7,11,13\).
Für \(p=2\) gilt \(q \le \lfloor 29/2 \rfloor = 14\). Das liefert sechs Produkte:
$$2\cdot2,\ 2\cdot3,\ 2\cdot5,\ 2\cdot7,\ 2\cdot11,\ 2\cdot13.$$
Für \(p=3\) gilt \(q \le \lfloor 29/3 \rfloor = 9\). Das liefert drei weitere:
$$3\cdot3,\ 3\cdot5,\ 3\cdot7.$$
Für \(p=5\) bleibt wegen \(q \le \lfloor 29/5 \rfloor = 5\) nur
$$5\cdot5.$$
Bei \(p=7\) ist schon \(7^2=49 \ge 30\), also endet der Prozess. Insgesamt ergibt sich
$$6+3+1=10,$$
genau wie in der angegebenen Liste \(4,6,9,10,14,15,21,22,25,26\).
Sind \(p_1 \lt p_2 \lt \cdots \lt p_m\) alle Primzahlen bis \(Q_{\max}\), dann lautet die gesuchte Anzahl
$$S(L)=\sum_{\substack{1 \le i \le m\\ p_i^2 \lt L}} \#\left\{j \ge i : p_j \le \left\lfloor\frac{L-1}{p_i}\right\rfloor\right\}.$$
Genau diese Summe wird von den Implementierungen ausgewertet.
Die C++-, Python- und Java-Implementierungen beginnen mit einem Sieb des Eratosthenes bis \(Q_{\max}\). Die zugrunde liegende Invariante ist klassisch: Wenn das Verfahren bei einer Primzahl \(r\) angekommen ist, sind bereits alle zusammengesetzten Zahlen unterhalb von \(r^2\) markiert, sodass das Streichen bei \(r^2\) beginnen darf.
Danach wird die Primzahlliste von links nach rechts durchlaufen. Die aktuelle Primzahl wird als kleiner Faktor \(p\) behandelt. Sobald \(p^2 \ge L\) gilt, bricht die Schleife ab. Andernfalls berechnet der Code die Schranke \(\left\lfloor\frac{L-1}{p}\right\rfloor\) und sucht per oberer Schranke in der sortierten Primzahlliste nach dem letzten zulässigen Partner.
Dass diese Suche erst am aktuellen Index beginnt, ist die algorithmische Umsetzung der Bedingung \(q \ge p\). Dadurch werden Produkte wie \(2\cdot13\) und \(13\cdot2\) nicht doppelt erfasst, während Quadrate \(p^2\) weiterhin korrekt mitzählen. Die drei Sprachen unterscheiden sich nur in der konkreten Schreibweise der Binärsuche.
Mit
$$Q_{\max}=\left\lfloor\frac{L-1}{2}\right\rfloor$$
kostet die Siebphase
$$O\!\left(Q_{\max}\log\log Q_{\max}\right)$$
Zeit und
$$O(Q_{\max})$$
Speicher.
In der zweiten Phase werden nur die Primzahlen unterhalb von \(\sqrt{L}\) betrachtet. Das sind \(\pi(\sqrt{L})\) Iterationen, jeweils mit einer Binärsuche in der Primzahlliste. Dieser Teil benötigt also
$$O\!\left(\pi(\sqrt{L})\log \pi(Q_{\max})\right)$$
zusätzliche Zeit. Für \(L=10^8\) ist das deutlich effizienter als die Faktorisierung jeder einzelnen Zahl unterhalb der Schranke; dominiert wird das Verfahren weiterhin vom Sieb.
Project Euler 187, \(10^8\)'den küçük olup asal çarpanları çokluklarıyla birlikte tam iki tane olan bileşik sayıların sayısını ister. Başka bir deyişle, sınırın altındaki yarı-asalları saymamız gerekir; \(4=2^2\), \(9=3^2\) ve \(25=5^2\) gibi asal kareler de bu kümeye dahildir.
Asıl fikir, her sayıyı tek tek asal çarpanlarına ayırmamakta yatar. Bir yarı-asal sayı \(n=pq\) biçiminde yazılır; burada \(p\) ve \(q\) asaldır ve \(p \le q\) koşulu konursa aynı sayı bir daha sayılmaz. Böylece problem, sayıları test etme probleminden asal çiftleri sayma problemine dönüşür.
Üst sınırı \(L\) ile gösterelim. Aranan miktar
$$S(L)=\#\{n \lt L : n=pq,\ p \le q,\ p,q\text{ prime}\}$$
olur. Çözümün omurgası, önce küçük asal \(p\)'yi seçip sonra ona eşlik edebilecek büyük asalları saymaktır.
Her yarı-asal sayı iki asalın çarpımıdır. Çarpanları \(p \le q\) sırasıyla yazdığımız anda temsil tek olur. Dolayısıyla problem tam olarak şu koşulları sağlayan asal çiftleri saymaya iner:
$$pq \lt L,\qquad p \le q.$$
Bu yaklaşımda hiçbir geçerli sayı kaçmaz ve hiçbir sayı iki kez sayılmaz. Çünkü her yarı-asalın tek bir küçük-asal, büyük-asal ayrımı vardır.
Her geçerli çiftten küçük olan asal en az 2'dir. Bu yüzden büyük olan asal için zorunlu olarak
$$q \le \left\lfloor\frac{L-1}{2}\right\rfloor$$
olmalıdır. Aksi halde \(q\) bundan büyükse, en küçük ortak çarpan olan \(2\) ile bile \(2q \ge L\) olur ve sayı sınırın altında kalmaz. Demek ki herhangi bir yarı-asalda yer alabilecek bütün asallar şu eşiğin altındadır:
$$Q_{\max}=\left\lfloor\frac{L-1}{2}\right\rfloor.$$
Uygulamaların yalnızca bu sınıra kadar asal üretmesi tamamen bu gözleme dayanır.
Küçük asal \(p\) sabitlendiğinde, hem \(q \ge p\) olmalı hem de çarpım \(L\)'yi geçmemelidir. O halde
$$p \le q \le \left\lfloor\frac{L-1}{p}\right\rfloor$$
aralığındaki asal sayılar bu \(p\)'nin katkısını verir. Asal sayma fonksiyonu \(\pi(x)\) ile bu katkı
$$\pi\!\left(\left\lfloor\frac{L-1}{p}\right\rfloor\right)-\pi(p)+1$$
şeklindedir. Kod ayrı bir \(\pi\) tablosu kurmaz; aynı sonucu sıralı asal listesinde ikili arama yaparak elde eder. Mevcut asalın bulunduğu konumdan itibaren üst sınırı aşmayan kaç asal kaldığı sayılır.
Sabit \(p\) için alınabilecek en küçük ortak çarpan yine \(q=p\)'dir. Eğer
$$p^2 \ge L$$
ise daha büyük hiçbir \(q\) işe yaramaz. Dolayısıyla yalnızca \(p^2 \lt L\) koşulunu sağlayan asallar incelenir. Tüm uygulamalardaki erken çıkış koşulu tam olarak budur.
Sorudaki örnek için
$$Q_{\max}=\left\lfloor\frac{29}{2}\right\rfloor=14$$
olur; yani gereken asallar \(2,3,5,7,11,13\)'tür.
\(p=2\) için \(q \le \lfloor 29/2 \rfloor = 14\) olduğundan altı ürün vardır:
$$2\cdot2,\ 2\cdot3,\ 2\cdot5,\ 2\cdot7,\ 2\cdot11,\ 2\cdot13.$$
\(p=3\) için \(q \le \lfloor 29/3 \rfloor = 9\) olur ve üç ürün gelir:
$$3\cdot3,\ 3\cdot5,\ 3\cdot7.$$
\(p=5\) için üst sınır \(5\) olduğundan yalnızca
$$5\cdot5$$
kalır. \(p=7\) noktasında ise \(7^2=49 \ge 30\) olduğu için devam etmeye gerek yoktur. Toplam
$$6+3+1=10$$
çıkar; bu da örnek listedeki \(4,6,9,10,14,15,21,22,25,26\) sayılarıyla aynıdır.
\(p_1 \lt p_2 \lt \cdots \lt p_m\), \(Q_{\max}\)'a kadarki asal sayılar olsun. O zaman cevap
$$S(L)=\sum_{\substack{1 \le i \le m\\ p_i^2 \lt L}} \#\left\{j \ge i : p_j \le \left\lfloor\frac{L-1}{p_i}\right\rfloor\right\}$$
şeklinde yazılır. Uygulamalar tam olarak bu toplamı hesaplar.
C++, Python ve Java uygulamalarının üçü de önce \(Q_{\max}\)'a kadar Eratosthenes eleği kurar. Buradaki temel değişmez şudur: algoritma bir asal \(r\)'ye geldiğinde, \(r^2\)'den küçük bütün bileşik sayılar daha önce işaretlenmiştir; bu yüzden yeni eleme işlemi \(r^2\)'den başlatılır.
Asal liste hazırlandıktan sonra uygulama listeyi soldan sağa gezer ve her adımda mevcut asalı küçük çarpan \(p\) kabul eder. Eğer \(p^2 \ge L\) ise döngü sona erer. Değilse \(\left\lfloor\frac{L-1}{p}\right\rfloor\) üst sınırı hesaplanır ve sıralı asal listede bu sınıra kadar giden en son konum ikili arama ile bulunur.
Aramanın listenin başından değil, mevcut asalın konumundan başlatılması \(q \ge p\) koşulunun kod karşılığıdır. Bu sayede \(2\cdot13\) ile \(13\cdot2\) ayrı ayrı sayılmaz; buna karşılık \(5\cdot5\) gibi kareler doğal biçimde korunur. Diller arasındaki fark yalnızca ikili aramanın sözdizimindedir; yapılan matematik aynıdır.
\(Q_{\max}=\left\lfloor\frac{L-1}{2}\right\rfloor\) olmak üzere, eleğin maliyeti
$$O\!\left(Q_{\max}\log\log Q_{\max}\right)$$
zamandır ve bellek kullanımı
$$O(Q_{\max})$$
olur.
İkinci fazda yalnızca \(\sqrt{L}\)'den küçük asallar dolaşılır; yani \(\pi(\sqrt{L})\) kadar yineleme vardır ve her birinde asal listesi üzerinde tek bir ikili arama yapılır. Bu bölüm
$$O\!\left(\pi(\sqrt{L})\log \pi(Q_{\max})\right)$$
ek zaman gerektirir. \(L=10^8\) için bu yaklaşım, tüm sayıları tek tek çarpanlara ayırmaktan çok daha hızlıdır ve baskın maliyet yine elekte kalır.
Project Euler 187 pide contar los enteros compuestos \(n \lt 10^8\) que tienen exactamente dos factores primos contando multiplicidades. Es decir, hay que contar los semiprimos por debajo del límite, incluyendo cuadrados primos como \(4=2^2\), \(9=3^2\) y \(25=5^2\).
La solución no intenta factorizar todos los enteros menores que el límite. En lugar de eso, cuenta directamente los pares de primos. Si \(n\) es semiprimo, entonces \(n=pq\) con \(p \le q\), y esa convención de orden hace que cada semiprimo aparezca una sola vez.
Sea \(L\) el límite superior. La cantidad buscada es
$$S(L)=\#\{n \lt L : n=pq,\ p \le q,\ p,q\text{ prime}\}.$$
Todo el método consiste en fijar primero el primo pequeño \(p\) y contar después cuántos primos \(q\) pueden acompañarlo.
Cada semiprimo admite una factorización \(n=pq\) con primos \(p \le q\). Una vez impuesta esa desigualdad, la representación es única. Por tanto, el problema se reduce a contar los pares de primos que cumplen
$$pq \lt L,\qquad p \le q.$$
Eso evita cualquier doble conteo y elimina la necesidad de probar número por número si tiene exactamente dos factores primos.
En todo par válido, el primo menor satisface \(p \ge 2\). Entonces el primo mayor debe obedecer
$$q \le \left\lfloor\frac{L-1}{2}\right\rfloor.$$
Si \(q\) fuera mayor que ese valor, ni siquiera con el compañero mínimo \(p=2\) el producto quedaría por debajo de \(L\). Así, cualquier primo que pueda aparecer en una solución está acotado por
$$Q_{\max}=\left\lfloor\frac{L-1}{2}\right\rfloor.$$
Esa es la razón exacta por la que las implementaciones generan primos solo hasta \(Q_{\max}\).
Si fijamos \(p\) como el factor pequeño, entonces \(q\) tiene que cumplir simultáneamente \(q \ge p\) y \(pq \lt L\). Por tanto, el rango admisible es
$$p \le q \le \left\lfloor\frac{L-1}{p}\right\rfloor.$$
Si \(\pi(x)\) denota la función contadora de primos, la contribución de ese \(p\) es
$$\pi\!\left(\left\lfloor\frac{L-1}{p}\right\rfloor\right)-\pi(p)+1.$$
Las implementaciones no construyen explícitamente esa función. Obtienen la misma cantidad mediante una búsqueda binaria sobre la lista ordenada de primos para localizar el último primo no superior al límite permitido.
Para un \(p\) fijo, el compañero más pequeño posible es \(q=p\). Si ya ocurre que
$$p^2 \ge L,$$
entonces ningún primo mayor podrá servir. De ahí que solo haya que procesar los primos con \(p^2 \lt L\). Esa observación es exactamente la condición de corte de los tres programas.
En el ejemplo del enunciado,
$$Q_{\max}=\left\lfloor\frac{29}{2}\right\rfloor=14,$$
de modo que los primos relevantes son \(2,3,5,7,11,13\).
Para \(p=2\), el límite es \(q \le \lfloor 29/2 \rfloor = 14\), así que hay seis productos:
$$2\cdot2,\ 2\cdot3,\ 2\cdot5,\ 2\cdot7,\ 2\cdot11,\ 2\cdot13.$$
Para \(p=3\), el límite es \(q \le \lfloor 29/3 \rfloor = 9\), y aparecen tres más:
$$3\cdot3,\ 3\cdot5,\ 3\cdot7.$$
Para \(p=5\), como \(q \le \lfloor 29/5 \rfloor = 5\), solo queda
$$5\cdot5.$$
En \(p=7\) ya tenemos \(7^2=49 \ge 30\), así que el proceso termina. El total es
$$6+3+1=10,$$
justo los diez valores del ejemplo: \(4,6,9,10,14,15,21,22,25,26\).
Si \(p_1 \lt p_2 \lt \cdots \lt p_m\) son los primos hasta \(Q_{\max}\), la respuesta puede escribirse como
$$S(L)=\sum_{\substack{1 \le i \le m\\ p_i^2 \lt L}} \#\left\{j \ge i : p_j \le \left\lfloor\frac{L-1}{p_i}\right\rfloor\right\}.$$
Esa es exactamente la cantidad que acumulan las implementaciones.
Las implementaciones en C++, Python y Java empiezan construyendo todos los primos hasta \(Q_{\max}\) con la criba de Eratóstenes. La invariante de la criba es la habitual: cuando el algoritmo llega a un primo \(r\), todos los compuestos menores que \(r^2\) ya han sido marcados, así que basta con tachar múltiplos a partir de \(r^2\).
Con la lista de primos ya ordenada, el código la recorre de izquierda a derecha y trata cada primo actual como el factor pequeño \(p\). Si \(p^2 \ge L\), el recorrido termina. Si no, calcula \(\left\lfloor\frac{L-1}{p}\right\rfloor\) y localiza mediante búsqueda binaria el punto donde dejan de ser válidos los posibles compañeros.
El hecho de arrancar esa búsqueda en la posición actual, y no al principio de la lista, es la traducción algorítmica de la restricción \(q \ge p\). Eso impide contar por separado \(2\cdot13\) y \(13\cdot2\), pero conserva correctamente los cuadrados \(p^2\). Las diferencias entre lenguajes son solo de sintaxis; el algoritmo es el mismo en los tres casos.
Con
$$Q_{\max}=\left\lfloor\frac{L-1}{2}\right\rfloor,$$
la fase de cribado cuesta
$$O\!\left(Q_{\max}\log\log Q_{\max}\right)$$
tiempo y
$$O(Q_{\max})$$
memoria.
La segunda fase solo recorre los primos por debajo de \(\sqrt{L}\), es decir, \(\pi(\sqrt{L})\) iteraciones, cada una con una búsqueda binaria sobre la tabla de primos. Por tanto añade
$$O\!\left(\pi(\sqrt{L})\log \pi(Q_{\max})\right)$$
de tiempo. Para \(L=10^8\), este método es muy superior a factorizar todos los enteros por separado, y el coste dominante sigue siendo la criba.
Project Euler 187 要求统计所有小于 \(10^8\) 的合数中，有多少个恰好包含两个素因子，并且重数也要计入。这正是半素数的定义，所以像 \(4=2^2\)、\(9=3^2\)、\(25=5^2\) 这样的素数平方也必须算进去。
直接从 1 到 \(10^8\) 逐个分解显然太浪费。真正高效的视角不是“检查每个整数是不是半素数”，而是“直接统计哪些素数对会产生一个半素数”。如果 \(n\) 是半素数，那么它一定可以唯一写成 \(n=pq\)，其中 \(p,q\) 都是素数且 \(p \le q\)。
设上界为 \(L\)。目标数量可以写成
$$S(L)=\#\{n \lt L : n=pq,\ p \le q,\ p,q\text{ prime}\}.$$
整个方法的核心，是先固定较小的素数 \(p\)，再计算有多少个较大的素数 \(q\) 能与它配对。
每个半素数都能写成两个素数的乘积。如果我们强制把较小的那个放在前面，即要求 \(p \le q\)，那么这种表示就是唯一的。因此，原题完全等价于统计满足
$$pq \lt L,\qquad p \le q$$
的素数对个数。这样做的好处是非常直接的：不会漏掉任何半素数，也不会把同一个半素数用两种顺序重复统计。
任意一个合法素数对里，较小的素数至少是 \(2\)。因此较大的那个素数一定满足
$$q \le \left\lfloor\frac{L-1}{2}\right\rfloor.$$
理由很简单：如果 \(q\) 已经大于这个值，那么即使把它和最小可能的素数 \(2\) 相乘，也会得到 \(2q \ge L\)，不再小于上界。于是，任何可能出现在答案中的素数都不会超过
$$Q_{\max}=\left\lfloor\frac{L-1}{2}\right\rfloor.$$
这正是三个实现都只把素数筛到 \(Q_{\max}\) 的数学依据。
一旦把 \(p\) 固定为较小因子，那么 \(q\) 必须同时满足两个条件：一是不能小于 \(p\)，二是乘积必须仍然小于 \(L\)。因此合法区间恰好是
$$p \le q \le \left\lfloor\frac{L-1}{p}\right\rfloor.$$
如果记 \(\pi(x)\) 为不超过 \(x\) 的素数个数，那么这个 \(p\) 的贡献就是
$$\pi\!\left(\left\lfloor\frac{L-1}{p}\right\rfloor\right)-\pi(p)+1.$$
实现里并没有显式构造整张 \(\pi(x)\) 表，而是利用“素数列表已经有序”这一事实，在列表中做一次上界二分查找。这样得到的末端位置，与上面的公式完全等价。
对于固定的较小因子 \(p\)，最小可能的搭档就是 \(q=p\)。如果连
$$p^2 \ge L$$
都已经成立，那么任何更大的素数 \(q\) 只会让乘积更大，自然也不可能合法。所以外层循环只需要处理满足 \(p^2 \lt L\) 的素数。这不是代码层面的技巧，而是问题本身给出的自然截断条件。
题目样例说，小于 30 的半素数一共有 10 个。用上面的计数方法可以直接重现这个结果。
首先
$$Q_{\max}=\left\lfloor\frac{29}{2}\right\rfloor=14,$$
因此只需要考虑素数 \(2,3,5,7,11,13\)。
当 \(p=2\) 时，有
$$q \le \left\lfloor\frac{29}{2}\right\rfloor=14,$$
所以可用的 \(q\) 是 \(2,3,5,7,11,13\)，贡献 6 个半素数：
$$2\cdot2,\ 2\cdot3,\ 2\cdot5,\ 2\cdot7,\ 2\cdot11,\ 2\cdot13.$$
当 \(p=3\) 时，有
$$q \le \left\lfloor\frac{29}{3}\right\rfloor=9,$$
因此 \(q\) 只能取 \(3,5,7\)，再贡献 3 个：
$$3\cdot3,\ 3\cdot5,\ 3\cdot7.$$
当 \(p=5\) 时，只有
$$q \le \left\lfloor\frac{29}{5}\right\rfloor=5,$$
所以只剩下
$$5\cdot5.$$
接下来到 \(p=7\) 时，已经有 \(7^2=49 \ge 30\)，因此过程结束。总数就是
$$6+3+1=10,$$
恰好对应样例里的 \(4,6,9,10,14,15,21,22,25,26\)。
如果把不超过 \(Q_{\max}\) 的素数记为 \(p_1 \lt p_2 \lt \cdots \lt p_m\)，那么答案可以写成
$$S(L)=\sum_{\substack{1 \le i \le m\\ p_i^2 \lt L}} \#\left\{j \ge i : p_j \le \left\lfloor\frac{L-1}{p_i}\right\rfloor\right\}.$$
三个实现所做的事情，本质上就是高效地把这条公式算出来。
C++、Python 和 Java 三个实现的结构完全一致。第一阶段先用埃拉托斯特尼筛法生成所有不超过 \(Q_{\max}\) 的素数。筛法的核心不变量是：当算法处理到某个素数 \(r\) 时，所有小于 \(r^2\) 的合数都已经在更早的时候被标记过，因此新的划去操作只需要从 \(r^2\) 开始。
有了有序素数表以后，第二阶段从左到右扫描这张表，把当前素数看作较小因子 \(p\)。如果 \(p^2 \ge L\)，外层循环立刻终止；否则先计算上界 \(\left\lfloor\frac{L-1}{p}\right\rfloor\)，再在有序表中做一次上界二分查找，找到最后一个仍然合法的素数位置。
二分查找不是从表头开始，而是从当前 \(p\) 所在的位置开始，这一点正对应了数学条件 \(q \ge p\)。因此像 \(2\cdot13\) 和 \(13\cdot2\) 这样的同一乘积不会重复统计，而 \(5\cdot5\) 这样的平方仍然会被正确保留。三种语言之间只有语法差异，算法内容完全相同。
记
$$Q_{\max}=\left\lfloor\frac{L-1}{2}\right\rfloor.$$
筛法阶段的时间复杂度是
$$O\!\left(Q_{\max}\log\log Q_{\max}\right),$$
空间复杂度是
$$O(Q_{\max}).$$
第二阶段只遍历小于 \(\sqrt{L}\) 的素数，因此共有 \(\pi(\sqrt{L})\) 次迭代，每次附带一次在素数表上的二分查找，所以额外时间为
$$O\!\left(\pi(\sqrt{L})\log \pi(Q_{\max})\right).$$
对于题目中的 \(L=10^8\)，这种做法远比逐个整数分解高效得多，整体瓶颈仍然是生成素数表的那一步。
Project Euler 187 просит посчитать составные числа \(n \lt 10^8\), имеющие ровно два простых множителя с учетом кратности. Иначе говоря, нужно посчитать полупростые числа ниже заданной границы; квадраты простых, такие как \(4=2^2\), \(9=3^2\) и \(25=5^2\), тоже входят в ответ.
Вместо того чтобы факторизовать каждое число по отдельности, решение напрямую считает допустимые пары простых. Если число полупростое, то оно единственным образом представляется в виде \(n=pq\), где \(p\) и \(q\) простые и \(p \le q\).
Пусть \(L\) обозначает верхнюю границу. Тогда искомое количество равно
$$S(L)=\#\{n \lt L : n=pq,\ p \le q,\ p,q\text{ prime}\}.$$
Вся идея состоит в том, чтобы фиксировать меньший простой множитель \(p\), а затем считать, сколько простых \(q\) можно с ним сочетать.
Каждое полупростое число имеет разложение \(n=pq\) с простыми \(p \le q\). После введения этого порядка разложение становится единственным. Поэтому исходная задача полностью эквивалентна подсчету пар простых, удовлетворяющих условиям
$$pq \lt L,\qquad p \le q.$$
Такой переход устраняет и пропуски, и двойной счет: каждое допустимое число соответствует ровно одной паре.
В любой допустимой паре меньший множитель удовлетворяет \(p \ge 2\). Значит, больший множитель обязан подчиняться неравенству
$$q \le \left\lfloor\frac{L-1}{2}\right\rfloor.$$
Иначе даже с минимально возможным партнером \(p=2\) произведение уже не будет меньше \(L\). Следовательно, любой простой, который вообще может встретиться в ответе, не превосходит
$$Q_{\max}=\left\lfloor\frac{L-1}{2}\right\rfloor.$$
Именно поэтому все реализации строят решето только до \(Q_{\max}\), а не до самого \(L\).
Если меньший множитель \(p\) уже выбран, то \(q\) должен одновременно удовлетворять условиям \(q \ge p\) и \(pq \lt L\). Поэтому допустимый диапазон имеет вид
$$p \le q \le \left\lfloor\frac{L-1}{p}\right\rfloor.$$
Если \(\pi(x)\) обозначает функцию подсчета простых чисел, то вклад такого \(p\) равен
$$\pi\!\left(\left\lfloor\frac{L-1}{p}\right\rfloor\right)-\pi(p)+1.$$
В коде эта формула реализуется не через отдельную таблицу \(\pi(x)\), а через двоичный поиск по отсортированному списку простых. Он находит последний допустимый индекс, после чего остается только взять длину соответствующего хвоста списка.
Для фиксированного \(p\) наименьший возможный партнер равен самому \(p\). Если уже выполнено
$$p^2 \ge L,$$
то любой больший простой \(q\) тем более не подойдет. Поэтому нужно рассматривать только простые \(p\), для которых \(p^2 \lt L\). Это и есть точная причина раннего завершения внешнего цикла.
В примере из условия утверждается, что ниже 30 находится 10 полупростых чисел. Рассмотрим тот же подсчет в терминах пар простых.
Сначала
$$Q_{\max}=\left\lfloor\frac{29}{2}\right\rfloor=14,$$
поэтому достаточно простых \(2,3,5,7,11,13\).
Для \(p=2\) получаем \(q \le \lfloor 29/2 \rfloor = 14\), то есть шесть произведений:
$$2\cdot2,\ 2\cdot3,\ 2\cdot5,\ 2\cdot7,\ 2\cdot11,\ 2\cdot13.$$
Для \(p=3\) имеем \(q \le \lfloor 29/3 \rfloor = 9\), и это дает еще три:
$$3\cdot3,\ 3\cdot5,\ 3\cdot7.$$
Для \(p=5\) верхняя граница равна 5, поэтому остается только
$$5\cdot5.$$
При \(p=7\) уже выполняется \(7^2=49 \ge 30\), значит, процесс заканчивается. Общая сумма равна
$$6+3+1=10,$$
что в точности совпадает со списком \(4,6,9,10,14,15,21,22,25,26\).
Если \(p_1 \lt p_2 \lt \cdots \lt p_m\) — все простые числа до \(Q_{\max}\), то ответ можно записать так:
$$S(L)=\sum_{\substack{1 \le i \le m\\ p_i^2 \lt L}} \#\left\{j \ge i : p_j \le \left\lfloor\frac{L-1}{p_i}\right\rfloor\right\}.$$
Именно эту сумму и вычисляют реализации.
Реализации на C++, Python и Java сначала строят решето Эратосфена до \(Q_{\max}\). Используемая инварианта стандартна: когда алгоритм дошел до простого числа \(r\), все составные числа меньше \(r^2\) уже были отмечены ранее, поэтому новые вычеркивания начинаются с \(r^2\).
После этого код проходит по отсортированному списку простых слева направо и рассматривает текущий простой как меньший множитель \(p\). Если \(p^2 \ge L\), внешний цикл немедленно завершается. Иначе вычисляется граница \(\left\lfloor\frac{L-1}{p}\right\rfloor\), а затем по списку простых выполняется поиск верхней границы.
То, что поиск стартует с текущей позиции, а не с начала списка, и есть программная реализация ограничения \(q \ge p\). Благодаря этому произведения вроде \(2\cdot13\) и \(13\cdot2\) не считаются дважды, а квадраты \(p^2\) сохраняются автоматически. Различия между тремя языками касаются только синтаксиса двоичного поиска.
При
$$Q_{\max}=\left\lfloor\frac{L-1}{2}\right\rfloor$$
фаза решета требует
$$O\!\left(Q_{\max}\log\log Q_{\max}\right)$$
времени и
$$O(Q_{\max})$$
памяти.
Во второй фазе обрабатываются только простые меньше \(\sqrt{L}\), то есть выполняется \(\pi(\sqrt{L})\) итераций, и на каждой из них есть один двоичный поиск по таблице простых. Поэтому дополнительное время равно
$$O\!\left(\pi(\sqrt{L})\log \pi(Q_{\max})\right).$$
Для \(L=10^8\) такой подход несравнимо лучше перебора с факторизацией каждого числа; основная стоимость по-прежнему приходится на построение решета.
تطلب مسألة Project Euler 187 عدَّ الأعداد المركبة \(n \lt 10^8\) التي تملك عاملين أوليين بالضبط عند احتساب التكرار. وهذا يعني أننا نبحث عن الأعداد نصف الأولية الأصغر من الحد، بما في ذلك مربعات الأعداد الأولية مثل \(4=2^2\) و\(9=3^2\) و\(25=5^2\).
الفكرة الحاسمة هي ألّا نفكك كل عدد تحت الحد إلى عوامله. بدلًا من ذلك نعدُّ أزواج الأعداد الأولية مباشرة. فإذا كان \(n\) نصف أولي، فإنه يكتب على الصورة \(n=pq\) حيث \(p\) و\(q\) أوليان و\(p \le q\). ومع فرض هذا الترتيب يصبح لكل عدد تمثيل وحيد.
لنرمز إلى الحد الأعلى بالرمز \(L\). عندئذ تكون الكمية المطلوبة هي
$$S(L)=\#\{n \lt L : n=pq,\ p \le q,\ p,q\text{ prime}\}.$$
جوهر الحل هو تثبيت العامل الأولي الأصغر \(p\)، ثم حساب عدد القيم الأولية \(q\) التي يمكن أن ترافقه.
كل عدد نصف أولي يمكن كتابته على صورة \(n=pq\) مع \(p \le q\). وما دام هذا الترتيب مفروضًا، فلن يوجد تمثيل ثانٍ لنفس العدد. لذلك تتحول المسألة كلها إلى عدِّ الأزواج الأولية التي تحقق
$$pq \lt L,\qquad p \le q.$$
بهذه الصياغة لا نفقد أي عدد صالح، ولا نعدُّ أي عدد مرتين.
في أي زوج صالح يكون العامل الأصغر على الأقل \(2\). لذلك لا بد أن يحقق العامل الأكبر
$$q \le \left\lfloor\frac{L-1}{2}\right\rfloor.$$
فلو كان \(q\) أكبر من هذا الحد، فإن ضربه في أصغر شريك ممكن وهو \(2\) سيعطي عددًا لا يقل عن \(L\). إذن كل عدد أولي يمكن أن يظهر في زوج صالح لا يتجاوز
$$Q_{\max}=\left\lfloor\frac{L-1}{2}\right\rfloor.$$
ولهذا بالضبط تكتفي التطبيقات ببناء الغربال حتى \(Q_{\max}\)، ولا تحتاج إلى الغربلة حتى \(L\) نفسه.
بعد تثبيت \(p\) بوصفه العامل الأصغر، يجب أن يحقق \(q\) شرطين معًا: أن يكون \(q \ge p\)، وأن يبقى حاصل الضرب أصغر من \(L\). إذن المجال المسموح هو
$$p \le q \le \left\lfloor\frac{L-1}{p}\right\rfloor.$$
إذا رمزنا بدالة عدِّ الأعداد الأولية إلى \(\pi(x)\)، فإن مساهمة هذا \(p\) تساوي
$$\pi\!\left(\left\lfloor\frac{L-1}{p}\right\rfloor\right)-\pi(p)+1.$$
لكن التطبيق لا يبني جدولًا مستقلًا لقيم \(\pi(x)\). بل يستفيد من كون قائمة الأعداد الأولية مرتبة، فيجري بحثًا ثنائيًا لإيجاد آخر عدد أولي لا يتجاوز الحد الأعلى المسموح، ومن ثم يعرف عدد العناصر الصالحة مباشرة.
أصغر شريك ممكن للعامل \(p\) هو \(q=p\) نفسه. فإذا تحقق أصلًا
$$p^2 \ge L,$$
فلن يصلح أي \(q\) أكبر منه. لذلك لا نحتاج إلا إلى الأعداد الأولية التي تحقق \(p^2 \lt L\). وهذا هو السبب الرياضي المباشر لشرط التوقف المبكر في جميع التطبيقات.
يذكر نص المسألة أن عدد الأعداد نصف الأولية الأصغر من 30 هو 10. ويمكن رؤية ذلك فورًا من طريقة العد.
لدينا أولًا
$$Q_{\max}=\left\lfloor\frac{29}{2}\right\rfloor=14,$$
ومن ثم تكون الأعداد الأولية ذات الصلة هي \(2,3,5,7,11,13\).
عندما \(p=2\)، يكون
$$q \le \left\lfloor\frac{29}{2}\right\rfloor=14,$$
فتكون القيم الممكنة لـ \(q\) هي \(2,3,5,7,11,13\)، وهذا يعطي ستة أعداد:
$$2\cdot2,\ 2\cdot3,\ 2\cdot5,\ 2\cdot7,\ 2\cdot11,\ 2\cdot13.$$
وعندما \(p=3\)، يصبح
$$q \le \left\lfloor\frac{29}{3}\right\rfloor=9,$$
فتبقى القيم \(3,5,7\)، أي ثلاثة أعداد إضافية:
$$3\cdot3,\ 3\cdot5,\ 3\cdot7.$$
وعندما \(p=5\)، لا يبقى إلا
$$5\cdot5$$
لأن الحد الأعلى يساوي 5. أما عند \(p=7\) فنجد أن \(7^2=49 \ge 30\)، ولذلك تتوقف العملية. والحصيلة النهائية هي
$$6+3+1=10,$$
وهي بالضبط الأعداد \(4,6,9,10,14,15,21,22,25,26\).
إذا كانت \(p_1 \lt p_2 \lt \cdots \lt p_m\) هي جميع الأعداد الأولية حتى \(Q_{\max}\)، فإن الجواب يكتب على الصورة
$$S(L)=\sum_{\substack{1 \le i \le m\\ p_i^2 \lt L}} \#\left\{j \ge i : p_j \le \left\lfloor\frac{L-1}{p_i}\right\rfloor\right\}.$$
وهذا هو المقدار الذي تحسبه التطبيقات حرفيًا.
تبدأ تطبيقات ++C وPython وJava ببناء غربال إراتوستينس حتى \(Q_{\max}\). وثابت العمل هنا معروف: عندما يصل الغربال إلى عدد أولي \(r\)، تكون كل المضاعفات المركبة الأصغر من \(r^2\) قد وُسِمت سابقًا، لذا يكفي أن يبدأ الشطب الجديد من \(r^2\).
بعد تجهيز قائمة الأعداد الأولية المرتبة، يمر التنفيذ عليها من اليسار إلى اليمين ويعامل كل عدد أولي حالي بوصفه العامل الأصغر \(p\). فإذا تحقق \(p^2 \ge L\) تنتهي الحلقة فورًا. وإلا يُحسب الحد \(\left\lfloor\frac{L-1}{p}\right\rfloor\)، ثم يُجرى بحث ثنائي لإيجاد آخر عدد أولي صالح في القائمة.
وكون البحث يبدأ من الموضع الحالي لا من بداية القائمة هو المقابل البرمجي للشرط \(q \ge p\). ولهذا لا يُعدُّ الناتج \(2\cdot13\) مرة ثانية على صورة \(13\cdot2\)، بينما تبقى المربعات مثل \(5\cdot5\) ضمن الجواب بصورة طبيعية. الاختلاف بين اللغات الثلاث شكلي فقط؛ أما الخوارزمية نفسها فهي واحدة.
إذا كان
$$Q_{\max}=\left\lfloor\frac{L-1}{2}\right\rfloor,$$
فإن بناء الغربال يحتاج إلى
$$O\!\left(Q_{\max}\log\log Q_{\max}\right)$$
زمنًا، وإلى
$$O(Q_{\max})$$
من الذاكرة.
أما المرحلة الثانية فتتجول فقط على الأعداد الأولية الأصغر من \(\sqrt{L}\)، أي \(\pi(\sqrt{L})\) دورة، وفي كل دورة يوجد بحث ثنائي واحد في جدول الأعداد الأولية. لذلك تضيف زمنًا مقداره
$$O\!\left(\pi(\sqrt{L})\log \pi(Q_{\max})\right).$$
وبالنسبة إلى الحد \(L=10^8\)، فإن هذه الطريقة أسرع بفارق كبير من تفكيك كل عدد أسفل الحد إلى عوامله، بينما تبقى كلفة توليد الأعداد الأولية هي الجزء المسيطر.