Start with 1 at the center of a square spiral and wrap the positive integers around it in layers of odd side length \(1,3,5,\dots\). The diagonals isolate a very small subset of those values, and the task is to find the first side length for which the proportion of primes on the two diagonals drops below a chosen threshold, usually \(10\%\).
The key simplification is that when the spiral grows from side length \(s-2\) to side length \(s\), only four new diagonal values appear. So the problem is not about storing the whole spiral; it is about generating those corner values, testing the relevant ones for primality, and maintaining a running ratio.
Let layer \(n \ge 0\) denote the square whose side length is \(s_n = 2n+1\). Layer \(0\) is just the center value \(1\). Every later layer adds one square ring around the previous one, and the only new diagonal entries are the four corners of that ring.
The largest value in layer \(n\) is the square of the side length:
$$s_n^2 = (2n+1)^2.$$
Along the outer ring, the distance between consecutive corners is exactly
$$s_n - 1 = 2n.$$
Therefore the four new corner values are
$$q_{n,k} = (2n+1)^2 - 2kn \qquad (k=0,1,2,3),$$
or, in terms of the side length \(s\),
$$s^2,\quad s^2-(s-1),\quad s^2-2(s-1),\quad s^2-3(s-1).$$
These are exactly the new diagonal values, because every earlier diagonal entry already lies inside the smaller \((s-2)\times(s-2)\) square.
A square of odd side length \(s\) has two diagonals of length \(s\), but the center belongs to both and must be counted once. After layer \(n\), the total number of diagonal entries is therefore
$$D_n = 2s_n - 1 = 4n + 1.$$
This gives the recurrence
$$D_0 = 1,\qquad D_n = D_{n-1} + 4 \quad (n \ge 1),$$
which is the combinatorial reason the implementations increase the diagonal count by 4 on every iteration.
Let \(c_n\) be the number of prime corners added at layer \(n\), and let \(P_n\) be the cumulative number of diagonal primes after that layer. Then
$$P_0 = 0,\qquad P_n = P_{n-1} + c_n.$$
One corner simplifies immediately: \(q_{n,0} = (2n+1)^2\) is a perfect square greater than 1 for every \(n \ge 1\), so it is never prime. Hence
$$c_n \in \{0,1,2,3\},$$
and each new layer requires only three genuine primality tests.
The first layers make the recurrence concrete.
For \(n=1\) we have \(s=3\), step \(=2\), and corners
$$9,\ 7,\ 5,\ 3.$$
Three of them are prime, so \(P_1 = 3\) and \(D_1 = 5\). The diagonal prime ratio is \(3/5 = 60\%\).
For \(n=2\) we have \(s=5\), step \(=4\), and new corners
$$25,\ 21,\ 17,\ 13.$$
Only \(17\) and \(13\) are prime, so \(c_2 = 2\), \(P_2 = 5\), and \(D_2 = 9\). The cumulative ratio becomes \(5/9 \approx 55.56\%\).
This also explains the checkpoint thresholds in the implementations. With threshold \(62\%\), side length \(3\) already qualifies because \(3/5 < 62\%\). With threshold \(60\%\), side length \(3\) does not qualify, because the condition is strictly “below”, not “below or equal”, so the search continues until side length \(5\).
For a threshold \(T\) measured in percent, the target condition is
$$\frac{P_n}{D_n} < \frac{T}{100}.$$
Because all quantities are integers, this is equivalent to
$$100P_n < T D_n.$$
The algorithm uses this cross-multiplied form directly. It preserves the strict inequality exactly and avoids any rounding issues from floating-point arithmetic.
The C++, Python, and Java implementations all follow the same layer-by-layer scan. They begin with only the center present, so the diagonal count is 1 and the prime count is 0. From there they visit the odd side lengths \(3,5,7,\dots\) in increasing order.
At each iteration the implementation computes the current side length, its square, and the corner step. From those values it forms the three non-square corners \(s^2-(s-1)\), \(s^2-2(s-1)\), and \(s^2-3(s-1)\). The corner \(s^2\) is not tested, because its compositeness is known in advance for every nontrivial layer.
Each version uses straightforward trial division. Numbers below 2 are rejected immediately, even numbers are handled as a special case, and then only odd divisors are tried. The loop stops once the divisor would exceed \(\sqrt{n}\); in the fixed-width languages this is written safely as \(p \le n/p\), so no floating-point square root is needed.
After the three primality tests, the implementation adds 4 to the diagonal count and adds the number of newly found primes to the cumulative prime count. It then checks the exact inequality \(100P < TD\). As soon as that condition becomes true, the current odd side length is returned.
The same code path also supports alternative percentage thresholds. Two built-in checkpoints verify the logic: threshold \(62\%\) should stop at side length \(3\), and threshold \(60\%\) should stop at side length \(5\). Those cases confirm both the corner formulas and the strict comparison rule.
If the search stops after layer \(L\), then the largest tested corner is on the order of \((2L+1)^2\). Trial division on a number of that size costs \(O(L)\) odd divisor checks in the worst case. Since each layer performs three primality tests and only \(O(1)\) additional arithmetic, the total running time is
$$O\!\left(\sum_{\ell=1}^{L} \ell\right)=O(L^2).$$
Because the returned side length is \(s = 2L+1\), this is equivalently \(O(s^2)\) in terms of the final answer. The memory usage is \(O(1)\): the implementations keep only the current layer data, the two running counts, and a few temporary integers.
Man beginnt mit der 1 im Zentrum einer quadratischen Spirale und legt die positiven ganzen Zahlen schichtweise darum, sodass die Seitenlängen \(1,3,5,\dots\) sind. Die beiden Diagonalen enthalten nur einen kleinen Teil dieser Werte, und gesucht ist die erste Seitenlänge, bei der der Primzahlanteil auf den Diagonalen unter eine vorgegebene Schwelle, normalerweise \(10\%\), fällt.
Die entscheidende Vereinfachung ist, dass beim Übergang von Seitenlänge \(s-2\) zu Seitenlänge \(s\) nur vier neue Diagonalwerte entstehen. Man muss also nicht die gesamte Spirale speichern, sondern nur diese Eckwerte erzeugen, die relevanten davon auf Primzahl testen und das Verhältnis fortlaufend aktualisieren.
Sei \(n \ge 0\) die Nummer der Schicht und \(s_n = 2n+1\) ihre Seitenlänge. Schicht \(0\) besteht nur aus dem Zentrum \(1\). Jede spätere Schicht fügt einen quadratischen Ring um die bisherige Spirale hinzu, und die einzigen neuen Diagonaleinträge sind die vier Ecken dieses Rings.
Der größte Wert der Schicht \(n\) ist das Quadrat der Seitenlänge:
$$s_n^2 = (2n+1)^2.$$
Entlang des äußeren Rings unterscheiden sich benachbarte Ecken immer um
$$s_n - 1 = 2n.$$
Damit lauten die vier neuen Eckwerte
$$q_{n,k} = (2n+1)^2 - 2kn \qquad (k=0,1,2,3),$$
oder in Abhängigkeit von der Seitenlänge \(s\)
$$s^2,\quad s^2-(s-1),\quad s^2-2(s-1),\quad s^2-3(s-1).$$
Genau diese Werte kommen neu auf den Diagonalen hinzu, denn alle älteren Diagonaleinträge liegen bereits im kleineren \((s-2)\times(s-2)\)-Quadrat.
Ein Quadrat mit ungerader Seitenlänge \(s\) besitzt zwei Diagonalen der Länge \(s\), aber das Zentrum gehört zu beiden und darf nur einmal gezählt werden. Nach Schicht \(n\) ist die Gesamtzahl der Diagonaleinträge also
$$D_n = 2s_n - 1 = 4n + 1.$$
Daraus folgt die Rekursion
$$D_0 = 1,\qquad D_n = D_{n-1} + 4 \quad (n \ge 1),$$
und genau deshalb erhöhen die Implementierungen die Diagonalanzahl in jedem Schritt um 4.
Sei \(c_n\) die Anzahl der primen Ecken, die in Schicht \(n\) hinzukommen, und \(P_n\) die kumulierte Anzahl der Primzahlen auf den Diagonalen nach dieser Schicht. Dann gilt
$$P_0 = 0,\qquad P_n = P_{n-1} + c_n.$$
Eine Ecke vereinfacht die Rechnung sofort: \(q_{n,0} = (2n+1)^2\) ist für jedes \(n \ge 1\) ein echtes Quadrat und damit nie prim. Also gilt
$$c_n \in \{0,1,2,3\},$$
und pro Schicht sind nur drei echte Primzahltests nötig.
Die ersten Schichten zeigen die Rekursion konkret.
Für \(n=1\) ist \(s=3\), die Schrittweite ist \(2\), und die Ecken sind
$$9,\ 7,\ 5,\ 3.$$
Drei davon sind prim, also \(P_1 = 3\) und \(D_1 = 5\). Das Verhältnis der Primzahlen auf den Diagonalen ist \(3/5 = 60\%\).
Für \(n=2\) ist \(s=5\), die Schrittweite ist \(4\), und die neuen Ecken sind
$$25,\ 21,\ 17,\ 13.$$
Nur \(17\) und \(13\) sind prim, also \(c_2 = 2\), \(P_2 = 5\) und \(D_2 = 9\). Das kumulative Verhältnis wird zu \(5/9 \approx 55{,}56\%\).
Genau daran erkennt man auch die strikte Ungleichung der Implementierungen. Bei einer Schwelle von \(62\%\) reicht Seitenlänge \(3\), weil \(3/5 < 62\%\). Bei einer Schwelle von \(60\%\) reicht Seitenlänge \(3\) dagegen nicht, weil „unter“ hier wirklich strikt gemeint ist; die erste passende Seitenlänge ist dann \(5\).
Für eine Prozent-Schwelle \(T\) lautet die Zielbedingung
$$\frac{P_n}{D_n} < \frac{T}{100}.$$
Da alle beteiligten Größen ganzzahlig sind, ist das äquivalent zu
$$100P_n < T D_n.$$
Die Implementierungen verwenden genau diese kreuzmultiplizierte Form. Dadurch bleibt die strikte Ungleichung exakt erhalten, und es entstehen keine Rundungsprobleme durch Fließkommazahlen.
Die C++-, Python- und Java-Implementierungen durchlaufen dieselbe Schicht-für-Schicht-Schleife. Sie starten nur mit dem Zentrum, also mit Diagonalanzahl 1 und Primzahlanzahl 0. Danach werden die ungeraden Seitenlängen \(3,5,7,\dots\) der Reihe nach betrachtet.
In jeder Iteration berechnet die Implementierung die aktuelle Seitenlänge, ihr Quadrat und die Eckschrittweite. Daraus entstehen die drei nichtquadratischen Ecken \(s^2-(s-1)\), \(s^2-2(s-1)\) und \(s^2-3(s-1)\). Die Ecke \(s^2\) wird nicht auf Primzahl geprüft, weil ihre Zusammengesetztheit für jede nichttriviale Schicht bereits bekannt ist.
Alle drei Versionen verwenden eine direkte Probedivision. Zahlen kleiner als 2 werden sofort verworfen, gerade Zahlen separat behandelt, und danach werden nur ungerade Teiler ausprobiert. Der Test endet, sobald der Teiler größer als \(\sqrt{n}\) wäre; in den Sprachen mit fester Wortbreite steht das sicher als Vergleich \(p \le n/p\), sodass keine Fließkommawurzel berechnet werden muss.
Nach den drei Primzahltests erhöht die Implementierung die Diagonalanzahl um 4 und addiert die Anzahl der neu gefundenen Primzahlen zur kumulierten Primzahlanzahl. Anschließend prüft sie die exakte Ungleichung \(100P < TD\). Sobald sie erfüllt ist, wird die aktuelle ungerade Seitenlänge zurückgegeben.
Der gleiche Codepfad unterstützt auch andere Prozent-Schwellen. Zwei eingebaute Kontrollfälle prüfen die Logik: Bei \(62\%\) muss die Suche bei Seitenlänge \(3\) enden, bei \(60\%\) erst bei Seitenlänge \(5\). Diese Tests bestätigen sowohl die Eckformeln als auch die strenge Vergleichsregel.
Wenn die Suche nach Schicht \(L\) stoppt, dann liegt die größte getestete Ecke in der Größenordnung \((2L+1)^2\). Probedivision für Zahlen dieser Größe kostet im schlechtesten Fall \(O(L)\) ungerade Teilbarkeitsprüfungen. Da jede Schicht drei Primzahltests und nur \(O(1)\) zusätzliche Arithmetik benötigt, ergibt sich insgesamt
$$O\!\left(\sum_{\ell=1}^{L} \ell\right)=O(L^2).$$
Mit \(s = 2L+1\) ist das äquivalent zu \(O(s^2)\) in der zurückgegebenen Seitenlänge. Der Speicherverbrauch ist \(O(1)\): Es werden nur die Daten der aktuellen Schicht, die beiden laufenden Zähler und einige Hilfszahlen gehalten.
Merkezde 1 ile başlayan kare biçimli bir spiralde pozitif tam sayılar katman katman dışarı doğru yerleştirilir ve kenar uzunlukları \(1,3,5,\dots\) olur. İki köşegen, tüm sayılar içinden çok küçük bir alt kümeyi seçer; amaç, köşegenlerdeki asal oranının verilen bir eşikten, genellikle \(10\%\)'dan, ilk kez daha aşağı düştüğü kenar uzunluğunu bulmaktır.
Temel sadeleştirme şudur: spiral \(s-2\) kenar uzunluğundan \(s\) kenar uzunluğuna büyüdüğünde, köşegenlere yalnızca dört yeni değer eklenir. Dolayısıyla bütün spirali kurmak gerekmez; yalnızca bu köşe değerlerini üretmek, gerekli olanları asallık açısından sınamak ve oranı kümülatif olarak güncellemek yeterlidir.
\(n \ge 0\) olmak üzere \(n\). katmanın kenar uzunluğu \(s_n = 2n+1\) olsun. \(0\). katman yalnızca merkezdeki \(1\)'dir. Sonraki her katman, önceki şeklin çevresine bir kare halka ekler; köşegenlere yeni gelen tek değerler de bu halkanın dört köşesidir.
\(n\). katmandaki en büyük sayı, kenar uzunluğunun karesidir:
$$s_n^2 = (2n+1)^2.$$
Dış halka üzerinde ardışık köşeler arasındaki fark sabittir ve
$$s_n - 1 = 2n$$
değerine eşittir. Bu yüzden dört yeni köşe değeri
$$q_{n,k} = (2n+1)^2 - 2kn \qquad (k=0,1,2,3)$$
şeklindedir; kenar uzunluğu \(s\) cinsinden yazarsak
$$s^2,\quad s^2-(s-1),\quad s^2-2(s-1),\quad s^2-3(s-1).$$
Bunlar gerçekten de yeni köşegen değerlerinin tamamıdır, çünkü daha eski bütün köşegen elemanları zaten içteki \((s-2)\times(s-2)\) karede bulunur.
Tek kenar uzunluklu bir karenin iki köşegeni vardır ve her birinin uzunluğu \(s\)'dir; ancak merkez her iki köşegende de yer aldığı için bir kez sayılmalıdır. Bu nedenle \(n\). katmandan sonra köşegen üzerindeki toplam eleman sayısı
$$D_n = 2s_n - 1 = 4n + 1$$
olur. Aynı bilgi şu özyinelemeyi de verir:
$$D_0 = 1,\qquad D_n = D_{n-1} + 4 \quad (n \ge 1).$$
Uygulamaların her döngüde köşegen sayısını 4 artırmasının nedeni tam olarak budur.
\(n\). katmanda eklenen asal köşe sayısı \(c_n\), bu katmandan sonra köşegenlerde görülen toplam asal sayısı da \(P_n\) olsun. O zaman
$$P_0 = 0,\qquad P_n = P_{n-1} + c_n.$$
Burada bir köşe baştan elenir: \(q_{n,0} = (2n+1)^2\), \(n \ge 1\) için 1'den büyük tam karedir ve dolayısıyla asal olamaz. Bu yüzden
$$c_n \in \{0,1,2,3\},$$
yani her katmanda en fazla üç gerçek asallık testi gerekir.
İlk katmanlar bu mekanizmayı açıkça gösterir.
\(n=1\) için \(s=3\), adım \(2\) ve köşeler
$$9,\ 7,\ 5,\ 3$$
olur. Bunların üçü asaldır; dolayısıyla \(P_1 = 3\) ve \(D_1 = 5\). Köşegenlerdeki asal oranı \(3/5 = 60\%\)'tir.
\(n=2\) için \(s=5\), adım \(4\) ve yeni köşeler
$$25,\ 21,\ 17,\ 13$$
olur. Yalnızca \(17\) ve \(13\) asaldır; bu nedenle \(c_2 = 2\), \(P_2 = 5\) ve \(D_2 = 9\). Kümülatif oran \(5/9 \approx 55{,}56\%\) olur.
Bu örnek, uygulamalardaki sıkı karşılaştırmayı da açıklar. Eşik \(62\%\) ise \(3/5 < 62\%\) olduğundan kenar uzunluğu \(3\) yeterlidir. Ama eşik \(60\%\) ise \(3/5\) tam olarak \(60\%\) yaptığı için koşul sağlanmaz; arama \(5\) kenar uzunluğuna kadar devam eder.
Yüzde cinsinden eşik \(T\) olsun. Hedef koşul
$$\frac{P_n}{D_n} < \frac{T}{100}$$
şeklindedir. Tüm büyüklükler tam sayı olduğundan bu koşul tam olarak
$$100P_n < T D_n$$
biçimine çevrilebilir. Algoritma doğrudan bu çapraz çarpılmış eşitsizliği kullanır. Böylece hem sıkı küçüklük korunur hem de kayan nokta yuvarlama hataları tamamen ortadan kalkar.
C++, Python ve Java uygulamaları aynı katman-döngüsünü izler. Başlangıçta yalnızca merkez bulunduğundan köşegen sayısı 1, asal sayısı 0'dır. Sonra \(3,5,7,\dots\) biçimindeki tek kenar uzunlukları sırayla taranır.
Her adımda uygulama güncel kenar uzunluğunu, bu uzunluğun karesini ve köşe adım farkını hesaplar. Bu üç değerden hareketle \(s^2-(s-1)\), \(s^2-2(s-1)\) ve \(s^2-3(s-1)\) biçimindeki üç kare-olmayan köşe üretilir. \(s^2\) köşesi ise test edilmez; çünkü trivial olmayan her katmanda bileşik olduğu önceden bilinmektedir.
Üç dilde de basit deneme bölmesi kullanılır. 2'den küçük sayılar hemen elenir, çift sayılar ayrı bir durum olarak işlenir, ardından yalnızca tek bölenler denenir. Döngü, bölen \(\sqrt{n}\)'i aşacağı anda durur; sabit genişlikli dillerde bu güvenli biçimde \(p \le n/p\) karşılaştırmasıyla yazılır, böylece kayan noktalı karekök hesabına ihtiyaç kalmaz.
Üç asallık sınamasından sonra uygulama köşegen sayısına 4 ekler ve o katmanda bulunan asal köşe sayısını toplam asal sayısına ekler. Ardından tam sayı eşitsizliği \(100P < TD\) kontrol edilir. Koşul ilk kez doğru olduğunda o andaki tek kenar uzunluğu döndürülür.
Aynı yapı farklı yüzde eşiklerini de destekler. İçeride iki küçük kontrol senaryosu vardır: \(62\%\) için sonuç \(3\), \(60\%\) için ise \(5\) olmalıdır. Bu kontroller hem köşe üretimini hem de karşılaştırmanın sıkı biçimde yapıldığını doğrular.
Arama \(L\). katmanda duruyorsa test edilen en büyük köşe yaklaşık \((2L+1)^2\) büyüklüğündedir. Bu boyuttaki bir sayı için deneme bölmesi en kötü durumda \(O(L)\) tek bölen denemesi gerektirir. Her katmanda üç asallık testi ve \(O(1)\) ek aritmetik bulunduğundan toplam süre
$$O\!\left(\sum_{\ell=1}^{L} \ell\right)=O(L^2)$$
olur. Döndürülen kenar uzunluğu \(s = 2L+1\) olduğundan bu, cevap cinsinden \(O(s^2)\) ile aynıdır. Bellek kullanımı \(O(1)\)'dir; yalnızca güncel katman bilgileri, iki kümülatif sayaç ve birkaç geçici tam sayı tutulur.
Se comienza con el 1 en el centro de una espiral cuadrada y se colocan los enteros positivos en capas sucesivas, de modo que las longitudes de lado sean \(1,3,5,\dots\). Las dos diagonales seleccionan solo una pequeña fracción de esos valores, y la tarea consiste en encontrar la primera longitud de lado para la cual la proporción de primos sobre las diagonales cae por debajo de un umbral dado, normalmente \(10\%\).
La simplificación decisiva es que, cuando la espiral crece de lado \(s-2\) a lado \(s\), solo aparecen cuatro nuevos valores diagonales. Por eso no hace falta construir toda la espiral: basta con generar esos valores de esquina, comprobar cuáles son primos y mantener la proporción acumulada.
Sea \(n \ge 0\) el número de capa y \(s_n = 2n+1\) su longitud de lado. La capa \(0\) contiene únicamente el valor central \(1\). Cada capa posterior añade un anillo cuadrado alrededor de la anterior, y las únicas entradas diagonales nuevas son las cuatro esquinas de ese anillo.
El mayor valor de la capa \(n\) es el cuadrado de la longitud de lado:
$$s_n^2 = (2n+1)^2.$$
A lo largo del anillo exterior, la diferencia entre esquinas consecutivas es constante y vale
$$s_n - 1 = 2n.$$
Por tanto, las cuatro nuevas esquinas son
$$q_{n,k} = (2n+1)^2 - 2kn \qquad (k=0,1,2,3),$$
o, en términos de la longitud de lado \(s\),
$$s^2,\quad s^2-(s-1),\quad s^2-2(s-1),\quad s^2-3(s-1).$$
Esos son exactamente los nuevos valores diagonales, porque todas las entradas diagonales anteriores ya estaban dentro del cuadrado más pequeño de tamaño \((s-2)\times(s-2)\).
Un cuadrado de lado impar \(s\) tiene dos diagonales de longitud \(s\), pero el centro pertenece a ambas y debe contarse una sola vez. Después de la capa \(n\), el número total de entradas diagonales es entonces
$$D_n = 2s_n - 1 = 4n + 1.$$
Eso produce la recurrencia
$$D_0 = 1,\qquad D_n = D_{n-1} + 4 \quad (n \ge 1),$$
que explica por qué las implementaciones aumentan el contador diagonal en 4 en cada iteración.
Sea \(c_n\) el número de esquinas primas añadidas en la capa \(n\), y sea \(P_n\) el número acumulado de primos sobre las diagonales después de esa capa. Entonces
$$P_0 = 0,\qquad P_n = P_{n-1} + c_n.$$
Una de las esquinas se descarta de inmediato: \(q_{n,0} = (2n+1)^2\) es un cuadrado perfecto mayor que 1 para todo \(n \ge 1\), así que nunca es primo. Por consiguiente,
$$c_n \in \{0,1,2,3\},$$
y cada capa necesita solo tres pruebas reales de primalidad.
Las primeras capas muestran con claridad cómo evoluciona la cuenta acumulada.
Para \(n=1\) tenemos \(s=3\), paso \(=2\), y las esquinas
$$9,\ 7,\ 5,\ 3.$$
Tres de ellas son primas, de modo que \(P_1 = 3\) y \(D_1 = 5\). La razón de primos en las diagonales es \(3/5 = 60\%\).
Para \(n=2\) tenemos \(s=5\), paso \(=4\), y las nuevas esquinas
$$25,\ 21,\ 17,\ 13.$$
Solo \(17\) y \(13\) son primos, así que \(c_2 = 2\), \(P_2 = 5\) y \(D_2 = 9\). La razón acumulada pasa a ser \(5/9 \approx 55{,}56\%\).
Este ejemplo también explica el carácter estricto de la comparación usada en las implementaciones. Con umbral \(62\%\), la longitud de lado \(3\) ya sirve porque \(3/5 < 62\%\). Con umbral \(60\%\), en cambio, el lado \(3\) no vale, porque la condición es “menor que” y no “menor o igual”; la búsqueda continúa hasta longitud \(5\).
Si \(T\) es el umbral expresado en porcentaje, la condición objetivo es
$$\frac{P_n}{D_n} < \frac{T}{100}.$$
Como todas las cantidades son enteras, esto equivale exactamente a
$$100P_n < T D_n.$$
El algoritmo usa directamente esta forma con multiplicación cruzada. Así conserva la desigualdad estricta y evita cualquier problema de redondeo por aritmética de coma flotante.
Las implementaciones en C++, Python y Java siguen el mismo barrido capa por capa. Empiezan solo con el centro, por lo que el número de elementos diagonales es 1 y el número de primos es 0. A partir de ahí recorren las longitudes de lado impares \(3,5,7,\dots\) en orden creciente.
En cada iteración la implementación calcula la longitud de lado actual, su cuadrado y el salto entre esquinas. Con esos valores forma las tres esquinas no cuadradas \(s^2-(s-1)\), \(s^2-2(s-1)\) y \(s^2-3(s-1)\). La esquina \(s^2\) no se somete a prueba de primalidad porque se sabe de antemano que es compuesta en toda capa no trivial.
Las tres versiones usan división por prueba. Los valores menores que 2 se rechazan de inmediato, los números pares se tratan aparte y después solo se prueban divisores impares. El bucle se detiene cuando el divisor superaría \(\sqrt{n}\); en los lenguajes de ancho fijo eso se expresa de forma segura como \(p \le n/p\), evitando calcular una raíz cuadrada en coma flotante.
Tras las tres pruebas de primalidad, la implementación suma 4 al contador diagonal y añade al contador acumulado de primos la cantidad de nuevas esquinas primas. Luego comprueba la desigualdad exacta \(100P < TD\). En cuanto la condición se cumple, devuelve la longitud de lado impar actual.
El mismo camino de ejecución también admite otros umbrales porcentuales. Dos comprobaciones internas validan la lógica: con \(62\%\) el proceso debe detenerse en lado \(3\), y con \(60\%\) debe hacerlo en lado \(5\). Esos casos verifican tanto las fórmulas de las esquinas como el hecho de que la comparación es estricta.
Si la búsqueda termina en la capa \(L\), la mayor esquina analizada es del orden de \((2L+1)^2\). Probar primalidad por división de prueba en números de ese tamaño cuesta \(O(L)\) verificaciones de divisibilidad impar en el peor caso. Como cada capa realiza tres pruebas de primalidad y solo \(O(1)\) aritmética adicional, el tiempo total es
$$O\!\left(\sum_{\ell=1}^{L} \ell\right)=O(L^2).$$
Dado que la longitud devuelta es \(s = 2L+1\), esto equivale a \(O(s^2)\) en función de la respuesta final. El uso de memoria es \(O(1)\): solo se conservan los datos de la capa actual, los dos contadores acumulados y unos pocos enteros temporales.
题目从中心的 1 出发，把正整数按方形螺旋一层一层向外写开，因此边长依次是 \(1,3,5,\dots\)。两条对角线只经过其中极少的一部分数字，要求的是：当对角线上的素数比例第一次低于某个阈值（通常是 \(10\%\)）时，这个方形螺旋的边长是多少。
真正重要的简化在于：螺旋从边长 \(s-2\) 扩展到边长 \(s\) 时，对角线上只会新增 4 个数。于是问题并不需要把整张螺旋表构造出来，而只需要生成这 4 个角点值，判断其中哪些是素数，并持续维护累计比例。
设第 \(n \ge 0\) 层的边长为 \(s_n = 2n+1\)。第 \(0\) 层只有中心数字 \(1\)。之后每增加一层，就是在原来的正方形外面再套上一圈新的方环，而新增到对角线上的元素恰好就是这圈方环的 4 个角。
第 \(n\) 层中的最大值等于边长的平方：
$$s_n^2 = (2n+1)^2.$$
沿着最外层边框，从一个角走到下一个角，数值的差始终相同，等于
$$s_n - 1 = 2n.$$
因此这一层新增的 4 个角点可写为
$$q_{n,k} = (2n+1)^2 - 2kn \qquad (k=0,1,2,3),$$
如果直接用边长 \(s\) 表示，就是
$$s^2,\quad s^2-(s-1),\quad s^2-2(s-1),\quad s^2-3(s-1).$$
这 4 个数正是这一层全部新增的对角线元素，因为更早的对角线元素都已经包含在里面那个 \((s-2)\times(s-2)\) 的小正方形中。
边长为奇数 \(s\) 的正方形有两条长度都为 \(s\) 的对角线，但中心点同时属于两条对角线，所以只能算一次。于是第 \(n\) 层之后，对角线上的元素总数是
$$D_n = 2s_n - 1 = 4n + 1.$$
这也给出递推式
$$D_0 = 1,\qquad D_n = D_{n-1} + 4 \quad (n \ge 1),$$
这正对应实现里每扩展一层就把对角线计数加 4 的做法。
设第 \(n\) 层新增的素数角点个数为 \(c_n\)，第 \(n\) 层结束后对角线上的累计素数个数为 \(P_n\)。那么
$$P_0 = 0,\qquad P_n = P_{n-1} + c_n.$$
其中有一个角点可以立即排除：\(q_{n,0} = (2n+1)^2\) 对所有 \(n \ge 1\) 都是大于 1 的完全平方数，因此绝不可能是素数。于是
$$c_n \in \{0,1,2,3\},$$
也就是说，每一层实际上只需要做 3 次真正的素性检测。
前两层就足以把整个递推机制看清楚。
当 \(n=1\) 时，\(s=3\)，步长为 \(2\)，四个角点是
$$9,\ 7,\ 5,\ 3.$$
其中 3 个是素数，所以 \(P_1 = 3\)，\(D_1 = 5\)，对角线素数比例为 \(3/5 = 60\%\)。
当 \(n=2\) 时，\(s=5\)，步长为 \(4\)，新增角点是
$$25,\ 21,\ 17,\ 13.$$
只有 \(17\) 和 \(13\) 是素数，因此 \(c_2 = 2\)，\(P_2 = 5\)，\(D_2 = 9\)，累计比例变成 \(5/9 \approx 55{,}56\%\)。
这个例子同时说明了代码中为什么使用严格不等号。若阈值是 \(62\%\)，那么 \(3/5 < 62\%\)，边长 \(3\) 已经满足条件；但若阈值是 \(60\%\)，边长 \(3\) 并不满足，因为题目要求的是“低于”而不是“不高于”，所以搜索必须继续到边长 \(5\)。
若阈值记为百分数 \(T\)，目标条件是
$$\frac{P_n}{D_n} < \frac{T}{100}.$$
由于所有量都是整数，这与下式完全等价：
$$100P_n < T D_n.$$
实现直接使用这个交叉相乘后的形式。这样既能精确保留严格不等号，又完全避免了浮点运算带来的舍入问题。
C++、Python 和 Java 实现都采用同样的逐层扫描。初始时螺旋里只有中心，因此对角线元素数为 1，素数个数为 0。之后按顺序考察奇数边长 \(3,5,7,\dots\)。
每次迭代先计算当前边长、边长平方以及角点之间的步长，再据此构造 3 个不是完全平方数的角点： \(s^2-(s-1)\)、\(s^2-2(s-1)\) 和 \(s^2-3(s-1)\)。至于 \(s^2\) 这个角点，由于在所有非平凡层里都确定是合数，所以根本不需要做素性检测。
三个版本都使用直接试除法。小于 2 的数立即判为非素数；偶数单独处理；之后只尝试奇数除数。循环在除数即将超过 \(\sqrt{n}\) 时停止；在固定宽度整数语言里，这一点通过安全比较 \(p \le n/p\) 来表达，因此不必调用浮点平方根。
完成 3 次素性检测后，实现把对角线总数加 4，并把新发现的素数个数加到累计素数计数上。然后检查精确的不等式 \(100P < TD\)。一旦该条件第一次成立，当前奇数边长就是答案。
同一套逻辑还支持别的百分比阈值。实现中内置了两个小检查：阈值 \(62\%\) 时应该在边长 \(3\) 停止，阈值 \(60\%\) 时应该在边长 \(5\) 停止。这两个检查同时验证了角点公式与严格比较规则。
如果搜索在第 \(L\) 层停止，那么被检测到的最大角点数量级是 \((2L+1)^2\)。对这种规模的整数做试除法，在最坏情况下需要 \(O(L)\) 次奇数除数检查。由于每层只做 3 次素性检测以及 \(O(1)\) 的额外整数运算，总时间复杂度为
$$O\!\left(\sum_{\ell=1}^{L} \ell\right)=O(L^2).$$
又因为最终返回的边长 \(s = 2L+1\)，所以也可以把它写成相对于答案边长的 \(O(s^2)\)。空间复杂度是 \(O(1)\)：实现只保留当前层的信息、两个累计计数以及少量临时整数。
В центре квадратной спирали стоит число 1, а положительные целые числа раскладываются вокруг него по слоям, поэтому длины сторон равны \(1,3,5,\dots\). Две диагонали проходят лишь через малую часть этих значений, и требуется найти первую длину стороны, при которой доля простых чисел на диагоналях опускается ниже заданного порога, обычно \(10\%\).
Главное упрощение состоит в том, что при переходе от стороны \(s-2\) к стороне \(s\) на диагоналях появляются только четыре новых числа. Поэтому нет необходимости строить всю спираль целиком: достаточно генерировать эти угловые значения, проверять нужные из них на простоту и поддерживать накопленное отношение.
Пусть слой \(n \ge 0\) имеет длину стороны \(s_n = 2n+1\). Слой \(0\) состоит только из центрального значения \(1\). Каждый следующий слой добавляет квадратное кольцо вокруг предыдущего, и единственные новые элементы диагоналей — это четыре угла этого кольца.
Наибольшее значение в слое \(n\) равно квадрату длины стороны:
$$s_n^2 = (2n+1)^2.$$
При переходе от одного угла внешнего кольца к следующему число уменьшается на постоянный шаг
$$s_n - 1 = 2n.$$
Следовательно, четыре новые угловые величины имеют вид
$$q_{n,k} = (2n+1)^2 - 2kn \qquad (k=0,1,2,3),$$
или, если писать через длину стороны \(s\),
$$s^2,\quad s^2-(s-1),\quad s^2-2(s-1),\quad s^2-3(s-1).$$
Это и есть все новые диагональные элементы, потому что все прежние диагональные значения уже лежат внутри меньшего квадрата \((s-2)\times(s-2)\).
У квадрата с нечетной длиной стороны \(s\) две диагонали длины \(s\), но центр принадлежит обеим и должен учитываться только один раз. Поэтому после слоя \(n\) общее число элементов на диагоналях равно
$$D_n = 2s_n - 1 = 4n + 1.$$
Отсюда получается рекуррентная формула
$$D_0 = 1,\qquad D_n = D_{n-1} + 4 \quad (n \ge 1),$$
и именно поэтому реализации увеличивают счётчик диагональных элементов на 4 на каждой итерации.
Пусть \(c_n\) — число простых углов, добавленных на слое \(n\), а \(P_n\) — накопленное число простых чисел на диагоналях после этого слоя. Тогда
$$P_0 = 0,\qquad P_n = P_{n-1} + c_n.$$
Один угол можно исключить сразу: \(q_{n,0} = (2n+1)^2\) для любого \(n \ge 1\) является полным квадратом, большим 1, а значит никогда не бывает простым. Следовательно,
$$c_n \in \{0,1,2,3\},$$
и на каждом слое нужно выполнять только три реальные проверки на простоту.
Первые слои хорошо показывают, как работает накопление.
При \(n=1\) имеем \(s=3\), шаг \(=2\), а углы равны
$$9,\ 7,\ 5,\ 3.$$
Три из них простые, поэтому \(P_1 = 3\) и \(D_1 = 5\). Доля простых на диагоналях равна \(3/5 = 60\%\).
При \(n=2\) имеем \(s=5\), шаг \(=4\), а новые углы равны
$$25,\ 21,\ 17,\ 13.$$
Простыми являются только \(17\) и \(13\), значит \(c_2 = 2\), \(P_2 = 5\) и \(D_2 = 9\). Накопленное отношение становится равным \(5/9 \approx 55{,}56\%\).
Этот пример также объясняет строгую проверку в реализациях. Для порога \(62\%\) длина стороны \(3\) уже подходит, потому что \(3/5 < 62\%\). Для порога \(60\%\) длина \(3\) уже не подходит, потому что условие требует именно «меньше», а не «меньше или равно»; поэтому поиск продолжается до стороны \(5\).
Если порог в процентах обозначить через \(T\), то целевое условие имеет вид
$$\frac{P_n}{D_n} < \frac{T}{100}.$$
Так как все величины целые, оно в точности равносильно неравенству
$$100P_n < T D_n.$$
Алгоритм использует именно эту форму с перекрёстным умножением. Она точно сохраняет строгую проверку и полностью избавляет от ошибок округления.
Реализации на C++, Python и Java выполняют один и тот же послойный проход. В начале в спирали есть только центр, поэтому число диагональных элементов равно 1, а число простых — 0. Затем последовательно рассматриваются нечетные длины сторон \(3,5,7,\dots\).
На каждой итерации реализация вычисляет текущую длину стороны, её квадрат и шаг между углами. Из этих величин строятся три неквадратных угла: \(s^2-(s-1)\), \(s^2-2(s-1)\) и \(s^2-3(s-1)\). Угол \(s^2\) не проверяется на простоту, потому что для любого нетривиального слоя заранее известно, что он составной.
Во всех трёх версиях используется обычное пробное деление. Числа меньше 2 сразу отвергаются, чётные числа обрабатываются отдельно, затем перебираются только нечётные делители. Цикл прекращается, когда делитель должен был бы превысить \(\sqrt{n}\); в языках с фиксированной разрядностью это записано безопасным сравнением \(p \le n/p\), без вычисления вещественного квадратного корня.
После трёх проверок на простоту реализация прибавляет 4 к числу диагональных элементов и добавляет число новых простых углов к накопленному счётчику простых. Затем проверяется точное неравенство \(100P < TD\). Как только оно впервые выполняется, возвращается текущая нечетная длина стороны.
Та же логика поддерживает и другие процентные пороги. Встроены две маленькие контрольные проверки: при \(62\%\) поиск должен остановиться на стороне \(3\), а при \(60\%\) — на стороне \(5\). Они подтверждают и формулы углов, и строгость сравнения.
Если поиск заканчивается на слое \(L\), то наибольший проверяемый угол имеет порядок \((2L+1)^2\). Пробное деление для чисел такого размера требует в худшем случае \(O(L)\) проверок нечётных делителей. Поскольку на каждом слое выполняются три проверки на простоту и только \(O(1)\) дополнительной арифметики, общее время равно
$$O\!\left(\sum_{\ell=1}^{L} \ell\right)=O(L^2).$$
Так как возвращаемая длина стороны равна \(s = 2L+1\), это то же самое, что \(O(s^2)\) по величине ответа. Память имеет порядок \(O(1)\): сохраняются только данные текущего слоя, два накопленных счётчика и несколько временных целых чисел.
نبدأ بالعدد 1 في مركز حلزون مربّع، ثم نرتب الأعداد الصحيحة الموجبة في طبقات متتالية بحيث تكون أطوال الأضلاع \(1,3,5,\dots\). القطران يمران عبر نسبة صغيرة جدًا من هذه الأعداد، والمطلوب هو إيجاد أول طول ضلع تهبط عنده نسبة الأعداد الأولية على القطرين إلى أقل من حد معيّن، وغالبًا ما يكون \(10\%\).
التبسيط الحاسم هو أن الانتقال من مربع ضلعه \(s-2\) إلى مربع ضلعه \(s\) لا يضيف إلى القطرين إلا أربعة أعداد جديدة فقط. لذلك ليست هناك حاجة إلى بناء الحلزون كاملًا؛ يكفي توليد قيم الزوايا الجديدة، وفحص ما يلزم منها من حيث الأولية، ثم تحديث النسبة التراكمية.
لنرمز إلى الطبقة رقم \(n \ge 0\) بطول ضلع \(s_n = 2n+1\). الطبقة \(0\) لا تحتوي إلا على القيمة المركزية \(1\). وكل طبقة لاحقة تضيف إطارًا مربعًا حول الشكل السابق، والعناصر الجديدة الوحيدة على القطرين هي زوايا هذا الإطار الأربع.
أكبر قيمة في الطبقة \(n\) تساوي مربع طول الضلع:
$$s_n^2 = (2n+1)^2.$$
وعلى الإطار الخارجي يكون الفرق بين زاويتين متتاليتين ثابتًا ويساوي
$$s_n - 1 = 2n.$$
لذلك فإن قيم الزوايا الأربع الجديدة هي
$$q_{n,k} = (2n+1)^2 - 2kn \qquad (k=0,1,2,3),$$
أو بصيغة تعتمد مباشرة على طول الضلع \(s\):
$$s^2,\quad s^2-(s-1),\quad s^2-2(s-1),\quad s^2-3(s-1).$$
وهذه هي بالضبط جميع القيم الجديدة على القطرين، لأن كل القيم القطرية الأقدم موجودة أصلًا داخل المربع الأصغر \((s-2)\times(s-2)\).
للمربع ذي الضلع الفردي \(s\) قطران طول كل منهما \(s\)، لكن المركز ينتمي إلى القطرين معًا ويجب أن يُحسب مرة واحدة فقط. لذلك يصبح العدد الكلي لعناصر القطرين بعد الطبقة \(n\)
$$D_n = 2s_n - 1 = 4n + 1.$$
ومن هنا نحصل أيضًا على العلاقة التراجعية
$$D_0 = 1,\qquad D_n = D_{n-1} + 4 \quad (n \ge 1),$$
وهذا يفسّر مباشرة لماذا تزيد التطبيقات عدّاد عناصر القطرين بمقدار 4 في كل دورة.
ليكن \(c_n\) عدد الزوايا الأولية التي أُضيفت في الطبقة \(n\)، وليكن \(P_n\) العدد التراكمي للأعداد الأولية على القطرين بعد هذه الطبقة. عندئذٍ
$$P_0 = 0,\qquad P_n = P_{n-1} + c_n.$$
وهنا توجد ملاحظة تختصر العمل فورًا: الزاوية \(q_{n,0} = (2n+1)^2\) هي مربع كامل أكبر من 1 لكل \(n \ge 1\)، ولذلك لا يمكن أن تكون أولية أبدًا. إذن
$$c_n \in \{0,1,2,3\},$$
وهذا يعني أن كل طبقة تتطلب ثلاث اختبارات أولية حقيقية فقط.
الطبقات الأولى تكشف آلية العد بشكل مباشر.
عند \(n=1\) يكون \(s=3\)، والخطوة تساوي \(2\)، والزوايا هي
$$9,\ 7,\ 5,\ 3.$$
ثلاث قيم منها أولية، ومن ثم \(P_1 = 3\) و\(D_1 = 5\). نسبة الأوليات على القطرين تساوي \(3/5 = 60\%\).
وعند \(n=2\) يكون \(s=5\)، والخطوة \(4\)، والزوايا الجديدة هي
$$25,\ 21,\ 17,\ 13.$$
القيمتان الأوليتان فقط هما \(17\) و\(13\)، ولذلك \(c_2 = 2\)، و\(P_2 = 5\)، و\(D_2 = 9\). تصبح النسبة التراكمية \(5/9 \approx 55{,}56\%\).
وهذا المثال يوضح أيضًا معنى المقارنة الصارمة المستخدمة في التنفيذ. إذا كان الحد \(62\%\)، فإن طول الضلع \(3\) يكفي لأن \(3/5 < 62\%\). أما إذا كان الحد \(60\%\)، فإن طول الضلع \(3\) لا ينجح، لأن الشرط هو “أصغر من” وليس “أصغر من أو يساوي”، ولذلك يستمر البحث حتى طول الضلع \(5\).
إذا رمزنا للحد المئوي بالرمز \(T\)، فإن الشرط المطلوب هو
$$\frac{P_n}{D_n} < \frac{T}{100}.$$
وبما أن جميع الكميات صحيحة، فهذا يكافئ تمامًا
$$100P_n < T D_n.$$
الخوارزمية تستخدم هذه الصيغة بعد الضرب التبادلي مباشرة. وبهذا تحافظ على صرامة المتباينة وتتفادى أي أخطاء تقريب ناتجة عن الحساب العائم.
تتبع تطبيقات C++ وPython وJava الحلقة نفسها طبقةً بعد طبقة. في البداية لا يوجد إلا المركز، لذلك يكون عدد عناصر القطرين 1 وعدد الأوليات 0. بعد ذلك تمر التطبيقات على أطوال الأضلاع الفردية \(3,5,7,\dots\) بالترتيب.
في كل تكرار يحسب التنفيذ طول الضلع الحالي، ومربعه، وفارق الزوايا. ومن هذه القيم تُبنى الزوايا الثلاث غير المربعة: \(s^2-(s-1)\) و\(s^2-2(s-1)\) و\(s^2-3(s-1)\). أما الزاوية \(s^2\) فلا تُختبر أصلًا، لأن كونها عددًا غير أولي معلوم مسبقًا في كل طبقة غير تافهة.
النسخ الثلاث تستخدم القسمة التجريبية المباشرة. كل عدد أصغر من 2 يُرفض فورًا، وتُعالج الأعداد الزوجية كحالة خاصة، ثم تُجرَّب القواسم الفردية فقط. وتتوقف الحلقة عندما يصبح القاسم أكبر من \(\sqrt{n}\)؛ وفي اللغات ذات الأعداد ثابتة العرض يُكتب ذلك بصورة آمنة على شكل \(p \le n/p\)، من دون الحاجة إلى جذر تربيعي عائم.
بعد اختبارات الأولية الثلاثة، يضيف التنفيذ 4 إلى عدد عناصر القطرين، ويضيف عدد الزوايا الأولية الجديدة إلى العدّاد التراكمي للأوليات. ثم يفحص المتباينة الدقيقة \(100P < TD\). وعندما تتحقق للمرة الأولى، يُعاد طول الضلع الفردي الحالي.
المسار نفسه يدعم أيضًا حدودًا مئوية مختلفة. توجد حالتا فحص صغيرتان مضمّنتان: عند حد \(62\%\) يجب التوقف عند طول ضلع \(3\)، وعند حد \(60\%\) يجب التوقف عند طول ضلع \(5\). هاتان الحالتان تؤكدان صحة صيغ الزوايا وصحة المقارنة الصارمة معًا.
إذا توقّف البحث بعد الطبقة \(L\)، فإن أكبر زاوية مختبرة تكون في حدود \((2L+1)^2\). واختبار الأولية بالقسمة التجريبية لعدد من هذا الحجم يحتاج في أسوأ الأحوال إلى \(O(L)\) من اختبارات القسمة على القواسم الفردية. وبما أن كل طبقة تتطلب ثلاث اختبارات أولية و\(O(1)\) فقط من العمليات الإضافية، فإن الزمن الكلي يساوي
$$O\!\left(\sum_{\ell=1}^{L} \ell\right)=O(L^2).$$
ولأن طول الضلع المُعاد هو \(s = 2L+1\)، فيمكن كتابة ذلك أيضًا على صورة \(O(s^2)\) بالنسبة إلى الجواب النهائي. أما الذاكرة فهي \(O(1)\)، لأن التنفيذ يحتفظ فقط ببيانات الطبقة الحالية، والعدادين التراكميين، وعدد قليل من القيم المؤقتة.