The task is to determine the 10001st prime number. If \(p_n\) denotes the \(n\)-th prime and \(\pi(x)\) denotes the number of primes not exceeding \(x\), then the problem is equivalent to finding the smallest integer \(x\) such that \(\pi(x) \ge 10001\).
The implementations do not test primality one candidate at a time. Instead, they choose a finite interval that is expected to contain \(p_n\), generate every prime in that interval with a sieve, and then read off the desired entry from the ordered list.
The whole method rests on two ideas: turning the question into a counting problem, and using a sieve whose correctness follows from a simple factorization invariant.
The prime-counting function is
$$\pi(x)=\#\{q \le x : q \text{ is prime}\}.$$
With this notation, the \(n\)-th prime can be written as
$$p_n=\min\{x \ge 2 : \pi(x)\ge n\}.$$
So the problem becomes: find some upper limit \(U\) with \(\pi(U)\ge n\), list all primes up to \(U\), and take the \(n\)-th element of that increasing list.
For \(n \ge 6\), a standard explicit estimate for the \(n\)-th prime is
$$p_n \lt n(\log n+\log\log n).$$
The implementations therefore start from
$$U(n)=\left\lfloor n(\log n+\log\log n)\right\rfloor+16.$$
The extra 16 is a safety margin. For very small indices the formula is inconvenient because of the \(\log\log n\) term, so the code uses the fixed bound \(64\) instead, and for \(n=1\) it returns \(2\) immediately. This matches the actual control flow in all three languages.
Correctness does not depend on the first estimate being perfect. If the sieve up to \(U\) produces fewer than \(n\) primes, then \(U \lt p_n\), so the program doubles \(U\) and tries again. Because primes are infinite in number, repeated doubling must eventually reach a bound above \(p_n\).
The sieve keeps a Boolean table for the integers \(0,1,\dots,U\). At the beginning, every entry at least 2 is treated as a prime candidate. When the outer loop reaches an integer \(p\) that is still marked, \(p\) must actually be prime: if \(p\) were composite, it would have some prime divisor \(r \lt p\), and that smaller prime would already have crossed \(p\) off.
Once \(p\) is known to be prime, the code marks
$$p^2,\ p^2+p,\ p^2+2p,\ \dots$$
as composite. Starting at \(p^2\) is enough. Any smaller multiple \(kp\) with \(2 \le k \lt p\) already has a factor below \(p\), so it was eliminated earlier. After every prime \(p \le \sqrt{U}\) has been processed, every unmarked number in the table is prime and every marked number is composite.
The checkpoint example used by the implementations is \(n=6\). The first six primes are
$$2,3,5,7,11,13,$$
so \(p_6=13\).
For the actual Project Euler input \(n=10001\), the initial estimate is
$$U(10001)=\left\lfloor 10001\bigl(\log 10001+\log\log 10001\bigr)\right\rfloor+16=114335.$$
This already gives a modest interval in which to search for the 10001st prime.
The C++, Python, and Java implementations all share the same computational core. They first handle the trivial first-prime case directly, then choose an initial upper bound: \(64\) for small indices and the logarithmic estimate above for \(n \ge 6\).
Next, the implementation allocates a Boolean array of length \(U+1\), marks 0 and 1 as non-prime, and runs the classical Eratosthenes loop for every candidate \(p\) with \(p^2 \le U\). Whenever \(p\) is still marked, all multiples starting at \(p^2\) are crossed off. A final scan through the table collects the surviving entries in increasing order.
If the resulting list contains at least \(n\) primes, the implementation returns the \(n\)-th entry. Otherwise it doubles the bound and rebuilds the sieve on the larger interval. The surrounding input and output details differ slightly between languages, but the number-theoretic algorithm is identical.
One sieve pass up to \(U\) uses \(O(U)\) memory and \(O(U\log\log U)\) time. Since the chosen bound satisfies \(U=\Theta(n\log n)\), the dominant cost is
$$O\!\bigl(n\log n\,\log\log(n\log n)\bigr).$$
The retry loop does not change the asymptotic order. If the final successful bound is \(U_{\ast}\), then the total amount of sieving over repeated doublings is bounded by a geometric series:
$$U_{\ast}+\frac{U_{\ast}}{2}+\frac{U_{\ast}}{4}+\cdots \lt 2U_{\ast}.$$
So even in the fallback case, the total work stays within a constant factor of the last successful sieve.
Gesucht ist die 10001. Primzahl. Wenn \(p_n\) die \(n\)-te Primzahl und \(\pi(x)\) die Anzahl der Primzahlen bis \(x\) bezeichnet, dann ist das genau die kleinste ganze Zahl \(x\) mit \(\pi(x)\ge 10001\).
Die Implementierungen testen also nicht eine Zahl nach der anderen auf Primzahl-Eigenschaft. Stattdessen wählen sie ein endliches Intervall, in dem \(p_n\) liegen soll, erzeugen alle Primzahlen in diesem Intervall mit einem Sieb und lesen dann den gesuchten Eintrag aus der sortierten Primzahlliste ab.
Die Lösung kombiniert zwei Bausteine: eine obere Schranke für \(p_n\) und das Invarianzargument, das die Korrektheit des Siebs erklärt.
Die Primzahlzählfunktion ist
$$\pi(x)=\#\{q \le x : q \text{ is prime}\}.$$
Damit lässt sich die \(n\)-te Primzahl schreiben als
$$p_n=\min\{x \ge 2 : \pi(x)\ge n\}.$$
Sobald also eine Grenze \(U\) bekannt ist, für die \(\pi(U)\ge n\) gilt, genügt es, alle Primzahlen bis \(U\) in aufsteigender Reihenfolge zu bestimmen und den \(n\)-ten Eintrag zu nehmen.
Für \(n \ge 6\) gilt eine klassische explizite Abschätzung
$$p_n \lt n(\log n+\log\log n).$$
Daher starten die Implementierungen mit
$$U(n)=\left\lfloor n(\log n+\log\log n)\right\rfloor+16.$$
Die zusätzliche 16 dient als Sicherheitsreserve. Für sehr kleine Indizes ist der Ausdruck mit \(\log\log n\) unpraktisch, deshalb verwendet der Code dort stattdessen die feste Grenze \(64\). Für \(n=1\) wird die Antwort \(2\) sofort zurückgegeben. Genau diese Fallunterscheidung steht in allen drei Programmen.
Die Korrektheit hängt nicht davon ab, dass die erste Grenze schon perfekt ist. Falls das Sieb bis \(U\) noch weniger als \(n\) Primzahlen liefert, dann ist \(U \lt p_n\), und das Programm verdoppelt \(U\) und startet den Siebdurchlauf erneut. Da es unendlich viele Primzahlen gibt, muss dieser Prozess irgendwann über \(p_n\) hinausreichen.
Das Sieb verwaltet eine boolesche Tabelle für die Zahlen \(0,1,\dots,U\). Anfangs wird jede Zahl ab 2 als möglicher Primkandidat markiert. Wenn die äußere Schleife eine Zahl \(p\) erreicht, die immer noch markiert ist, dann ist \(p\) tatsächlich prim: Wäre \(p\) zusammengesetzt, hätte \(p\) einen Primteiler \(r \lt p\), und dieser kleinere Primteiler hätte \(p\) bereits gestrichen.
Danach markiert der Code
$$p^2,\ p^2+p,\ p^2+2p,\ \dots$$
als zusammengesetzt. Dass man erst bei \(p^2\) beginnt, ist entscheidend und korrekt. Jedes kleinere Vielfache \(kp\) mit \(2 \le k \lt p\) besitzt schon einen Faktor unterhalb von \(p\) und wurde deshalb früher eliminiert. Sind alle Primzahlen \(p \le \sqrt{U}\) verarbeitet, dann sind genau die unmarkierten Einträge prim.
Das Kontrollbeispiel der Implementierungen ist \(n=6\). Die ersten sechs Primzahlen sind
$$2,3,5,7,11,13,$$
also gilt \(p_6=13\).
Für die eigentliche Project-Euler-Eingabe \(n=10001\) ergibt die Startschranke
$$U(10001)=\left\lfloor 10001\bigl(\log 10001+\log\log 10001\bigr)\right\rfloor+16=114335.$$
Damit reicht schon ein relativ kleines Suchintervall, um die 10001. Primzahl sicher einzuschließen.
Die C++-, Python- und Java-Implementierungen besitzen denselben Rechenkern. Zuerst behandeln sie den trivialen Fall der ersten Primzahl direkt. Danach wählen sie eine Anfangsgrenze: \(64\) für kleine Indizes und sonst die logarithmische Abschätzung.
Anschließend wird ein boolesches Feld der Länge \(U+1\) angelegt, 0 und 1 werden als nicht prim markiert, und die klassische Eratosthenes-Schleife läuft für alle Kandidaten \(p\) mit \(p^2 \le U\). Immer wenn \(p\) noch markiert ist, werden alle Vielfachen ab \(p^2\) gestrichen. Ein abschließender linearer Durchlauf sammelt die verbleibenden Primzahlen in aufsteigender Reihenfolge.
Enthält diese Liste schon mindestens \(n\) Einträge, wird der \(n\)-te zurückgegeben. Andernfalls wird die Grenze verdoppelt und das Sieb auf dem größeren Bereich neu aufgebaut. Die Ein- und Ausgabe ist in den drei Sprachen leicht unterschiedlich organisiert, aber der Zahlentheorie-Kern ist derselbe.
Ein Siebdurchlauf bis \(U\) benötigt \(O(U)\) Speicher und \(O(U\log\log U)\) Zeit. Da die gewählte Grenze \(U=\Theta(n\log n)\) erfüllt, ergibt sich insgesamt
$$O\!\bigl(n\log n\,\log\log(n\log n)\bigr).$$
Auch die Verdopplungsschleife ändert diese Größenordnung nicht. Ist \(U_{\ast}\) die erste erfolgreiche Grenze, dann ist die Gesamtarbeit aller vorherigen Versuche durch eine geometrische Reihe beschränkt:
$$U_{\ast}+\frac{U_{\ast}}{2}+\frac{U_{\ast}}{4}+\cdots \lt 2U_{\ast}.$$
Die gesamte Laufzeit bleibt also bis auf einen konstanten Faktor gleich der letzten erfolgreichen Siebung.
İstenen şey 10001. asal sayıyı bulmaktır. \(p_n\) \(n\). asal sayıyı, \(\pi(x)\) ise \(x\)'i aşmayan asal sayıların sayısını göstersin. Bu durumda problem, \(\pi(x)\ge 10001\) koşulunu sağlayan en küçük tamsayı \(x\)'i bulmakla aynıdır.
Uygulamalar her sayıyı tek tek asal testiyle ele almaz. Bunun yerine \(p_n\)'i içermesi beklenen sonlu bir aralık seçer, o aralıktaki tüm asalları elekle üretir ve sonra sıralı listeden istenen elemanı alır.
Çözüm iki fikre dayanır: \(p_n\) için kullanılabilir bir üst sınır bulmak ve Eratosthenes eleğinin neden doğru çalıştığını bir değişmez üzerinden açıklamak.
Asal sayma fonksiyonu
$$\pi(x)=\#\{q \le x : q \text{ is prime}\}$$
şeklinde tanımlanır. Bu gösterimle
$$p_n=\min\{x \ge 2 : \pi(x)\ge n\}$$
olur. Dolayısıyla \(\pi(U)\ge n\) sağlayan bir \(U\) bulunduğunda, \(U\)'ya kadar olan asalları artan sırada listelemek ve listenin \(n\). elemanını almak yeterlidir.
\(n \ge 6\) için klasik açık bir tahmin şudur:
$$p_n \lt n(\log n+\log\log n).$$
Bu yüzden uygulamalar başlangıçta
$$U(n)=\left\lfloor n(\log n+\log\log n)\right\rfloor+16$$
değerini kullanır. Buradaki ek 16 bir güvenlik payıdır. Çok küçük indekslerde \(\log\log n\) ifadesi pratik değildir; bu nedenle kod orada sabit \(64\) sınırını seçer. \(n=1\) için ise doğrudan \(2\) döndürülür. Üç dildeki çözümün akışı gerçekten böyledir.
Doğruluk ilk tahminin tam isabetli olmasına bağlı değildir. Eğer \(U\)'ya kadar yapılan elekten çıkan asal sayılar \(n\)'den azsa, bu \(U \lt p_n\) demektir ve program \(U\)'yu iki katına çıkarıp işlemi tekrarlar. Asal sayıların sonsuz olması nedeniyle bu tekrar süreci eninde sonunda \(p_n\)'i aşan bir sınıra ulaşır.
Elek, \(0,1,\dots,U\) tamsayıları için bir Boolean tablo tutar. Başlangıçta 2 ve üzerindeki her sayı asal adayı kabul edilir. Dış döngü, hâlâ işaretli olan bir \(p\) sayısına ulaştığında \(p\)'nin gerçekten asal olması gerekir; çünkü \(p\) bileşik olsaydı \(p\)'yi bölen ve \(p\)'den küçük olan bir asal çarpan bulunurdu, o küçük asal da \(p\)'yi daha önce elemiş olurdu.
Bundan sonra kod
$$p^2,\ p^2+p,\ p^2+2p,\ \dots$$
değerlerini bileşik diye işaretler. \(p^2\)'den başlamak yeterlidir. Çünkü \(2 \le k \lt p\) için her \(kp\) katı, \(p\)'den küçük bir çarpana zaten sahiptir ve daha önce elenmiştir. Tüm \(p \le \sqrt{U}\) değerleri işlendiğinde tabloda işaretli kalan sayılar tam olarak asal sayılardır.
Uygulamaların kullandığı kontrol örneği \(n=6\)'dır. İlk altı asal sayı
$$2,3,5,7,11,13$$
olduğundan \(p_6=13\) elde edilir.
Asıl Project Euler girdisi olan \(n=10001\) için başlangıç tahmini
$$U(10001)=\left\lfloor 10001\bigl(\log 10001+\log\log 10001\bigr)\right\rfloor+16=114335$$
olur. Yani 10001. asalı bulmak için gereken ilk aralık oldukça makul büyüklüktedir.
C++, Python ve Java uygulamalarının hesaplama çekirdeği aynıdır. Önce birinci asal durumunu doğrudan ele alırlar. Ardından küçük indeksler için \(64\), daha büyük indeksler için de yukarıdaki logaritmik tahminden bir başlangıç üst sınırı seçerler.
Sonra uzunluğu \(U+1\) olan bir Boolean dizi oluşturulur, 0 ile 1 asal değil diye işaretlenir ve \(p^2 \le U\) koşulunu sağlayan adaylar için klasik Eratosthenes döngüsü çalıştırılır. Hâlâ işaretli kalan her \(p\) için \(p^2\)'den başlayan bütün katlar elenir. Son taramada tabloda kalan asallar artan sırayla bir listeye alınır.
Liste en az \(n\) eleman içeriyorsa \(n\). asal geri döndürülür. İçermiyorsa sınır iki katına çıkarılır ve daha büyük aralıkta elek baştan kurulur. Diller arasındaki giriş çıkış ayrıntıları biraz farklı olsa da kullanılan sayı kuramı algoritması aynıdır.
\(U\)'ya kadar tek bir elek geçişi \(O(U)\) bellek ve \(O(U\log\log U)\) zaman gerektirir. Seçilen sınır \(U=\Theta(n\log n)\) olduğundan toplam baskın maliyet
$$O\!\bigl(n\log n\,\log\log(n\log n)\bigr)$$
olur.
İki katına çıkarma döngüsü bu mertebeyi değiştirmez. İlk başarılı sınır \(U_{\ast}\) ise, önceki denemelerin toplam elek maliyeti bir geometrik seriyle sınırlanır:
$$U_{\ast}+\frac{U_{\ast}}{2}+\frac{U_{\ast}}{4}+\cdots \lt 2U_{\ast}.$$
Bu yüzden geri dönüşlü denemeler olsa bile toplam iş son başarılı eleğin yalnızca sabit katsayı kadar üzerine çıkar.
Hay que encontrar el primo número 10001. Si \(p_n\) denota el \(n\)-ésimo primo y \(\pi(x)\) cuenta cuántos primos no superan \(x\), entonces el problema equivale a hallar el menor entero \(x\) tal que \(\pi(x)\ge 10001\).
Las implementaciones no van comprobando uno por uno si cada entero es primo. En cambio, eligen un intervalo finito que debería contener a \(p_n\), generan todos los primos de ese intervalo con una criba y después toman la entrada deseada de la lista ordenada resultante.
La solución se apoya en dos piezas: una cota superior para \(p_n\) y el invariante de factorización que hace correcta a la criba de Eratóstenes.
La función contadora de primos es
$$\pi(x)=\#\{q \le x : q \text{ is prime}\}.$$
Con esta notación,
$$p_n=\min\{x \ge 2 : \pi(x)\ge n\}.$$
Así que basta encontrar una cota \(U\) para la cual \(\pi(U)\ge n\), listar los primos hasta \(U\) en orden creciente y tomar el \(n\)-ésimo elemento.
Para \(n \ge 6\) se usa la estimación explícita
$$p_n \lt n(\log n+\log\log n).$$
Por ello las implementaciones arrancan con
$$U(n)=\left\lfloor n(\log n+\log\log n)\right\rfloor+16.$$
El \(+16\) añade un pequeño margen de seguridad. Para índices muy pequeños la expresión con \(\log\log n\) es poco cómoda, así que el código toma directamente la cota fija \(64\). Y para \(n=1\) devuelve \(2\) sin construir ninguna criba. Ese es exactamente el comportamiento presente en los tres lenguajes.
La corrección no depende de que la primera cota sea exacta. Si la criba hasta \(U\) produce menos de \(n\) primos, entonces \(U \lt p_n\) y el programa duplica \(U\) y vuelve a empezar. Como existen infinitos primos, este proceso de duplicación termina necesariamente con una cota que ya contiene al objetivo.
La criba mantiene una tabla booleana para los enteros \(0,1,\dots,U\). Al principio, todo número al menos igual a 2 se considera candidato a primo. Cuando el bucle exterior llega a un \(p\) que sigue marcado, \(p\) tiene que ser primo: si fuera compuesto, tendría un divisor primo \(r \lt p\), y ese divisor más pequeño ya habría tachado a \(p\) antes.
Una vez identificado ese primo, el código marca
$$p^2,\ p^2+p,\ p^2+2p,\ \dots$$
como compuestos. Empezar en \(p^2\) basta, porque cualquier múltiplo menor \(kp\) con \(2 \le k \lt p\) ya posee un factor por debajo de \(p\) y fue eliminado en una etapa previa. Cuando se han procesado todos los \(p \le \sqrt{U}\), las entradas aún marcadas son exactamente los primos.
El ejemplo de control que usan las implementaciones es \(n=6\). Los seis primeros primos son
$$2,3,5,7,11,13,$$
así que \(p_6=13\).
Para la entrada real de Project Euler, \(n=10001\), la cota inicial vale
$$U(10001)=\left\lfloor 10001\bigl(\log 10001+\log\log 10001\bigr)\right\rfloor+16=114335.$$
Eso muestra que el intervalo inicial ya es lo bastante pequeño como para que una criba completa sea una estrategia razonable.
Las implementaciones en C++, Python y Java comparten el mismo núcleo algorítmico. Primero resuelven directamente el caso trivial del primer primo. Después eligen una cota inicial: \(64\) para índices pequeños y, en otro caso, la estimación logarítmica indicada arriba.
A continuación reservan un arreglo booleano de tamaño \(U+1\), marcan 0 y 1 como no primos y ejecutan el bucle clásico de Eratóstenes para todos los candidatos \(p\) con \(p^2 \le U\). Cada vez que \(p\) sigue marcado, se tachan todos sus múltiplos a partir de \(p^2\). Un recorrido final sobre la tabla recoge los índices supervivientes en orden creciente.
Si la lista resultante ya contiene al menos \(n\) primos, el programa devuelve la entrada número \(n\). Si no, duplica la cota y reconstruye la criba desde cero sobre el intervalo ampliado. Las diferencias entre lenguajes están en los detalles de entrada y salida, no en la matemática del algoritmo.
Una pasada de criba hasta \(U\) usa \(O(U)\) memoria y \(O(U\log\log U)\) tiempo. Como la cota elegida cumple \(U=\Theta(n\log n)\), el coste dominante es
$$O\!\bigl(n\log n\,\log\log(n\log n)\bigr).$$
El bucle de reintento tampoco cambia el orden asintótico. Si \(U_{\ast}\) es la primera cota que ya contiene a \(p_n\), el trabajo total invertido en todas las cribas previas queda acotado por
$$U_{\ast}+\frac{U_{\ast}}{2}+\frac{U_{\ast}}{4}+\cdots \lt 2U_{\ast}.$$
En consecuencia, incluso si hay que duplicar la cota varias veces, el coste total sigue siendo solo un factor constante mayor que el de la última criba exitosa.
题目要求求出第 10001 个素数。若用 \(p_n\) 表示第 \(n\) 个素数，用 \(\pi(x)\) 表示不超过 \(x\) 的素数个数，那么这道题等价于寻找满足 \(\pi(x)\ge 10001\) 的最小整数 \(x\)。
实现并不是对每个整数逐个做素性判定，而是先选出一个应当包含 \(p_n\) 的有限区间，在这个区间内用筛法一次性生成全部素数，再从升序列表中取出第 \(n\) 个元素。
整个方法由两部分构成：先为 \(p_n\) 建立一个可操作的上界，再利用埃拉托斯特尼筛法的基本不变性证明筛选过程一定正确。
素数计数函数定义为
$$\pi(x)=\#\{q \le x : q \text{ is prime}\}.$$
于是第 \(n\) 个素数可以写成
$$p_n=\min\{x \ge 2 : \pi(x)\ge n\}.$$
这一定义非常重要，因为它把“找第 \(n\) 个素数”转成了“找到一个上界 \(U\)，使得到 \(U\) 为止至少已经出现了 \(n\) 个素数”。一旦有了这样的 \(U\)，只需把 \(2\) 到 \(U\) 之间的所有素数按从小到大列出来，取第 \(n\) 项即可。
当 \(n \ge 6\) 时，可以使用经典显式估计
$$p_n \lt n(\log n+\log\log n).$$
因此代码采用
$$U(n)=\left\lfloor n(\log n+\log\log n)\right\rfloor+16$$
作为初始上界。这里额外加上的 16 只是保守余量。对于很小的 \(n\)，\(\log\log n\) 这一项并不方便直接使用，所以实现改用固定上界 \(64\)。而当 \(n=1\) 时，答案就是 \(2\)，无需做任何筛选。这些分支都真实存在于三份实现中。
更关键的是，算法的正确性并不依赖第一次估计就完全命中。如果筛到 \(U\) 以后得到的素数个数仍然少于 \(n\)，那就说明 \(U \lt p_n\)。这时程序把 \(U\) 翻倍，再重新做一次完整筛法。由于素数有无穷多个，反复翻倍以后总会超过真正的 \(p_n\)，因此循环必然终止。
筛法维护一个布尔表，记录 \(0,1,\dots,U\) 中每个整数当前是否仍被视为素数候选。开始时，除了 0 和 1 之外，所有数都暂时保留。外层循环走到某个仍未被划掉的 \(p\) 时，\(p\) 必然是素数。原因是：如果 \(p\) 是合数，那么它一定有某个小于 \(p\) 的素因子 \(r\)，而当处理 \(r\) 时，\(p\) 就应该已经被标记为合数了。
确认 \(p\) 为素数后，程序会划去
$$p^2,\ p^2+p,\ p^2+2p,\ \dots$$
这些倍数。之所以可以从 \(p^2\) 开始，而不必从 \(2p\) 开始，是因为任何更小的倍数 \(kp\) 若满足 \(2 \le k \lt p\)，就已经拥有一个小于 \(p\) 的因子，因此必定在更早阶段被处理过。等到所有满足 \(p \le \sqrt{U}\) 的素数都完成划除后，表中剩下的未划去整数就恰好全部是素数。
实现中的检查样例是 \(n=6\)。前六个素数为
$$2,3,5,7,11,13,$$
因此 \(p_6=13\)。这个例子很小，但足以验证“生成有序素数表，再取第 \(n\) 项”这一思路完全正确。
对题目的真实输入 \(n=10001\)，初始估计为
$$U(10001)=\left\lfloor 10001\bigl(\log 10001+\log\log 10001\bigr)\right\rfloor+16=114335.$$
这说明程序一开始需要筛的范围其实并不大，完全适合用普通的埃拉托斯特尼筛法直接求解。
C++、Python 和 Java 三份实现的核心算法完全一致。首先处理最简单的边界情形，也就是第一个素数直接返回 2。然后根据输入规模选择上界：小输入用固定值 64，较大输入用上面的对数估计式。
接下来，程序建立长度为 \(U+1\) 的布尔数组，把 0 和 1 设为非素数。之后执行经典的筛法主循环，对每个满足 \(p^2 \le U\) 的候选 \(p\)，若它还没有被划掉，就从 \(p^2\) 开始按步长 \(p\) 划去所有倍数。主循环结束后，再顺序扫描整张表，把仍然为真的下标依次收集起来，它们就是从小到大排列的全部素数。
如果收集到的素数数量已经不少于 \(n\)，程序就返回其中第 \(n\) 个；如果还不够，就把上界翻倍，在更大的区间上重新构造筛表并重复。三种语言在输入输出包装上略有差异，但数论层面的流程完全相同。
筛到上界 \(U\) 的一次完整过程需要 \(O(U)\) 空间和 \(O(U\log\log U)\) 时间。由于这里采用的上界满足 \(U=\Theta(n\log n)\)，所以主导复杂度可以写成
$$O\!\bigl(n\log n\,\log\log(n\log n)\bigr).$$
即使发生“上界不够，需要翻倍重来”的情况，渐近量级也不会改变。若第一次成功的上界记为 \(U_{\ast}\)，那么此前所有失败尝试的总工作量最多形成一个几何级数：
$$U_{\ast}+\frac{U_{\ast}}{2}+\frac{U_{\ast}}{4}+\cdots \lt 2U_{\ast}.$$
因此，总成本至多只是最后一次成功筛法的常数倍，而不会多出新的数量级。
Нужно найти 10001-е простое число. Если \(p_n\) обозначает \(n\)-е простое, а \(\pi(x)\) обозначает количество простых чисел, не превосходящих \(x\), то задача равносильна поиску наименьшего целого \(x\), для которого \(\pi(x)\ge 10001\).
Реализации не проверяют числа на простоту по одному. Вместо этого они выбирают конечный интервал, который должен содержать \(p_n\), строят все простые числа на этом интервале с помощью решета, а затем берут нужный элемент из полученного упорядоченного списка.
Вся идея состоит из двух частей: нужна явная верхняя оценка для \(p_n\) и нужен инвариант, объясняющий, почему решето Эратосфена действительно отбрасывает ровно составные числа.
Функция подсчета простых задается формулой
$$\pi(x)=\#\{q \le x : q \text{ is prime}\}.$$
Тогда
$$p_n=\min\{x \ge 2 : \pi(x)\ge n\}.$$
Это значит, что достаточно подобрать такое \(U\), для которого \(\pi(U)\ge n\), перечислить все простые числа до \(U\) в возрастающем порядке и взять \(n\)-й элемент списка.
Для \(n \ge 6\) используется стандартная явная оценка
$$p_n \lt n(\log n+\log\log n).$$
Поэтому реализации начинают с величины
$$U(n)=\left\lfloor n(\log n+\log\log n)\right\rfloor+16.$$
Добавка 16 играет роль запаса. Для совсем малых \(n\) выражение с \(\log\log n\) неудобно, поэтому код берет фиксированную границу \(64\). А в случае \(n=1\) ответ \(2\) возвращается сразу. Именно так устроены все три реализации.
Важно, что корректность не зависит от точности первого приближения. Если после решета до \(U\) получено меньше \(n\) простых, это означает \(U \lt p_n\), и программа просто удваивает \(U\) и повторяет вычисление. Поскольку простых чисел бесконечно много, последовательность удвоений неизбежно дойдет до границы, превышающей \(p_n\).
Решето хранит булеву таблицу для чисел \(0,1,\dots,U\). Изначально каждое число не меньше 2 считается кандидатом в простые. Когда внешний цикл доходит до значения \(p\), которое все еще не вычеркнуто, число \(p\) обязано быть простым. Иначе у него был бы простой делитель \(r \lt p\), и при обработке этого меньшего делителя число \(p\) уже оказалось бы вычеркнутым.
После этого код помечает как составные числа
$$p^2,\ p^2+p,\ p^2+2p,\ \dots$$
Начинать именно с \(p^2\) достаточно. Любое меньшее кратное \(kp\) при \(2 \le k \lt p\) уже имеет множитель меньше \(p\), а значит, было удалено раньше. Когда обработаны все простые \(p \le \sqrt{U}\), в таблице остаются невычеркнутыми ровно простые числа.
Проверочный пример в реализациях использует \(n=6\). Первые шесть простых чисел таковы:
$$2,3,5,7,11,13,$$
следовательно, \(p_6=13\).
Для настоящего входа Project Euler, то есть для \(n=10001\), начальная оценка равна
$$U(10001)=\left\lfloor 10001\bigl(\log 10001+\log\log 10001\bigr)\right\rfloor+16=114335.$$
Значит, уже первый рабочий интервал имеет вполне умеренный размер, и полный проход решетом оказывается практичным.
Реализации на C++, Python и Java используют один и тот же вычислительный шаблон. Сначала они отдельно обрабатывают тривиальный случай первого простого числа. Затем выбирают начальную верхнюю границу: \(64\) для малых индексов и логарифмическую формулу для больших.
Далее создается булев массив длины \(U+1\), значения 0 и 1 объявляются непростыми, после чего запускается классический цикл решета для всех кандидатов \(p\), удовлетворяющих \(p^2 \le U\). Если очередное \(p\) не вычеркнуто, то все его кратные, начиная с \(p^2\), помечаются как составные. Затем один линейный проход собирает все оставшиеся индексы в возрастающий список простых чисел.
Если в списке уже не меньше \(n\) элементов, возвращается \(n\)-й. Если нет, граница удваивается, и решето строится заново на расширенном диапазоне. Внешняя организация ввода и вывода в языках немного различается, но сама арифметическая идея везде одинакова.
Один проход решета до \(U\) требует \(O(U)\) памяти и \(O(U\log\log U)\) времени. Поскольку выбранная граница удовлетворяет \(U=\Theta(n\log n)\), итоговая доминирующая сложность равна
$$O\!\bigl(n\log n\,\log\log(n\log n)\bigr).$$
Цикл с удвоением не меняет этого порядка. Если через \(U_{\ast}\) обозначить первую удачную границу, то суммарная работа всех предыдущих попыток ограничивается геометрическим рядом
$$U_{\ast}+\frac{U_{\ast}}{2}+\frac{U_{\ast}}{4}+\cdots \lt 2U_{\ast}.$$
Значит, даже при повторных перезапусках полная стоимость остается лишь постоянным множителем от последнего успешного прохода решета.
المطلوب هو إيجاد العدد الأولي رقم 10001. إذا رمزنا للعدد الأولي رقم \(n\) بالرمز \(p_n\)، ولعدد الأعداد الأولية التي لا تتجاوز \(x\) بالرمز \(\pi(x)\)، فإن المسألة تصبح البحث عن أصغر عدد صحيح \(x\) يحقق \(\pi(x)\ge 10001\).
التنفيذات لا تفحص الأعداد واحدا بعد واحد باختبار أولية مستقل لكل عدد. بدلا من ذلك تختار مجالا منتهيا يفترض أن يحتوي \(p_n\)، ثم تولد كل الأعداد الأولية في ذلك المجال بواسطة الغربال، ثم تأخذ العنصر المطلوب من القائمة المرتبة الناتجة.
تعتمد الفكرة كلها على جزأين: تقدير علوي مناسب لـ \(p_n\)، ولازم منطقي يفسر لماذا يحذف غربال إراتوستينس جميع الأعداد المركبة ولا يحذف عددا أوليا.
دالة عد الأعداد الأولية تعرف بالصيغة
$$\pi(x)=\#\{q \le x : q \text{ is prime}\}.$$
وبهذا الترميز نحصل على
$$p_n=\min\{x \ge 2 : \pi(x)\ge n\}.$$
إذن يكفي أن نجد حدا أعلى \(U\) يحقق \(\pi(U)\ge n\)، ثم نسرد جميع الأعداد الأولية حتى \(U\) بترتيب تصاعدي، ونأخذ العنصر رقم \(n\) من هذه القائمة.
عندما يكون \(n \ge 6\)، يمكن استعمال التقدير الصريح
$$p_n \lt n(\log n+\log\log n).$$
ولذلك تبدأ التنفيذات من القيمة
$$U(n)=\left\lfloor n(\log n+\log\log n)\right\rfloor+16.$$
العدد 16 هنا هامش أمان فقط. أما عندما يكون \(n\) صغيرا جدا فالتعبير الذي يحتوي \(\log\log n\) ليس مريحا، لذلك يستخدم الكود الحد الثابت \(64\). وإذا كان \(n=1\) فالإجابة هي \(2\) مباشرة من دون بناء غربال. هذا يطابق فعلا ما تفعله الحلول الثلاثة.
الصحة لا تعتمد على أن يكون هذا التقدير الأول دقيقا تماما. فإذا أعطى الغربال حتى \(U\) عددا من الأعداد الأولية أقل من \(n\)، فهذا يعني أن \(U \lt p_n\)، وعندها يضاعف البرنامج \(U\) ويعيد المحاولة. وبما أن الأعداد الأولية غير منتهية، فلا بد أن يصل التكرار في النهاية إلى حد يتجاوز \(p_n\).
يحتفظ الغربال بجدول منطقي للأعداد \(0,1,\dots,U\). في البداية يعتبر كل عدد لا يقل عن 2 مرشحا لأن يكون أوليا. وعندما يصل الدور في الحلقة الخارجية إلى عدد \(p\) ما زال غير مشطوب، فلا بد أن \(p\) أولي فعلا. فلو كان مركبا لكان له قاسم أولي \(r \lt p\)، وعند معالجة ذلك القاسم الأصغر لكان \(p\) قد شطب مسبقا.
بعد التأكد من أولية \(p\)، يقوم الكود بشطب
$$p^2,\ p^2+p,\ p^2+2p,\ \dots$$
بوصفها أعدادا مركبة. والبدء من \(p^2\) يكفي تماما، لأن أي مضاعف أصغر من ذلك على صورة \(kp\) حيث \(2 \le k \lt p\) يملك عاملا أصغر من \(p\)، ولذلك يكون قد حذف في خطوة سابقة. وبعد الانتهاء من جميع القيم \(p \le \sqrt{U}\)، تكون كل القيم التي بقيت غير مشطوبة في الجدول أعدادا أولية بالضبط.
مثال التحقق المستخدم في التنفيذات هو \(n=6\). أول ستة أعداد أولية هي
$$2,3,5,7,11,13,$$
ومن ثم \(p_6=13\).
أما لمدخل Project Euler الحقيقي، أي \(n=10001\)، فإن التقدير الابتدائي يساوي
$$U(10001)=\left\lfloor 10001\bigl(\log 10001+\log\log 10001\bigr)\right\rfloor+16=114335.$$
وهذا يبين أن المجال الأول الذي يغربله البرنامج يبقى متوسط الحجم، ولذلك يكون الحل المباشر بالغربال عمليا تماما.
تنفيذات C++ وPython وJava تشترك في البنية الحسابية نفسها. فهي تعالج أولا الحالة البسيطة الخاصة بأول عدد أولي، ثم تختار حدا أعلى ابتدائيا: \(64\) للفهارس الصغيرة، أو التقدير اللوغاريتمي السابق عندما يكون الإدخال أكبر.
بعد ذلك تنشئ مصفوفة منطقية بطول \(U+1\)، وتعلم 0 و1 على أنهما غير أوليين، ثم تنفذ الحلقة الكلاسيكية لغربال إراتوستينس على كل مرشح \(p\) يحقق \(p^2 \le U\). وكلما بقي \(p\) غير مشطوب، تشطب جميع مضاعفاته ابتداء من \(p^2\). وفي نهاية العملية يمر البرنامج مرة أخيرة على الجدول ليجمع القيم الباقية بترتيب تصاعدي.
إذا احتوت القائمة على \(n\) عددا أوليا أو أكثر، يعاد العنصر رقم \(n\). وإذا لم يحدث ذلك، يضاعف البرنامج الحد الأعلى ويعيد بناء الغربال من الصفر على المجال الأكبر. تفاصيل الإدخال والإخراج تختلف قليلا بين اللغات، لكن الجوهر الرياضي واحد.
المرور الواحد للغربال حتى \(U\) يستهلك \(O(U)\) من الذاكرة و\(O(U\log\log U)\) من الزمن. وبما أن الحد المختار يحقق \(U=\Theta(n\log n)\)، فإن الكلفة الغالبة تصبح
$$O\!\bigl(n\log n\,\log\log(n\log n)\bigr).$$
حلقة إعادة المحاولة لا تغير هذا الرتبة. فإذا رمزنا بأول حد ناجح إلى \(U_{\ast}\)، فإن مجموع أعمال الغربلة عبر كل مراحل التضعيف السابقة محكوم بمتسلسلة هندسية:
$$U_{\ast}+\frac{U_{\ast}}{2}+\frac{U_{\ast}}{4}+\cdots \lt 2U_{\ast}.$$
لذلك يبقى العمل الكلي، حتى في حالة إعادة المحاولة، ضمن عامل ثابت من آخر غربال ناجح.