A circular prime is a prime number whose every cyclic digit rotation is also prime. If \(n=197\), the rotations are \(197\), \(971\), and \(719\), so 197 is circular. The task is to count all circular primes below \(10^6\).
The important counting detail is that the problem asks for individual primes, not rotation classes. Thus the orbit \(\{197,971,719\}\) contributes 3, while 11 contributes 1 because its two rotations coincide numerically.
Write a \(k\)-digit number as \(n=d_0d_1\cdots d_{k-1}\). Circular primes are naturally described by the orbit generated by cyclically moving the leftmost digit to the end.
Define the one-step left rotation by
$$R(d_0d_1\cdots d_{k-1})=d_1d_2\cdots d_{k-1}d_0.$$
Then \(n\) is circular exactly when every member of the finite orbit
$$\{n,R(n),R^2(n),\dots,R^{k-1}(n)\}$$
is prime. After \(k\) rotations we return to the starting arrangement, so \(R^k(n)=n\).
The same rotation can be written arithmetically. If \(n\) has \(k\) digits and \(P=10^{k-1}\), then
$$R(n)=10\left(n \bmod P\right)+\left\lfloor \frac{n}{P} \right\rfloor.$$
Most orbits have size \(k\), but repeated digits can shorten the orbit. For example, \(11\) is fixed by rotation, so its orbit has size 1 even though it has two digits.
Suppose a circular prime has at least two digits. If one of its digits were in \(\{0,2,4,5,6,8\}\), some rotation would place that digit in the units position. The rotated number would then be divisible by 2 or 5, so it could not be prime. Therefore every multi-digit circular prime must use only digits from
$$\{1,3,7,9\}.$$
There is a second useful invariant: rotations preserve the sum of the digits. Hence they also preserve the residue modulo 3. If the digit sum were divisible by 3, then every rotation would be divisible by 3, so the only possible circular prime of that kind would be the single-digit prime 3 itself. This explains why circular primes are extremely sparse.
The provided implementations do not explicitly apply these filters, because a direct scan below one million is already fast enough. Still, these facts give the correct mathematical picture of why the brute-force search works so well.
If one element of a rotation orbit is circular, then every element of the same orbit is circular, because they all have exactly the same set of rotations. The problem, however, does not ask for the number of distinct orbits. It asks for the number of circular primes themselves.
So the orbit \(\{197,971,719\}\) contributes 3 to the answer, while the orbit \(\{11\}\) contributes 1. This is precisely why the direct strategy of scanning every prime below the limit and testing it independently gives the right total.
For \(197\), the orbit is
$$197 \to 971 \to 719 \to 197.$$
All three distinct values are prime, so each of them is a circular prime.
For \(101\), the rotations are \(101\), \(011\), and \(110\). Interpreted numerically, these are \(101\), \(11\), and \(110\). Since \(110\) is composite, 101 is not circular. This example shows both why a zero digit is fatal and why converting a rotated digit string back to an integer causes no ambiguity in the primality test.
Completing the full search below \(10^6\) yields 55 circular primes.
The C++, Python, and Java implementations begin by building a Sieve of Eratosthenes slightly beyond the requested search bound. That table lets the main loop answer most primality queries in constant time.
Each implementation then scans upward through the integers below the limit and immediately skips any value that the sieve already marks as composite. For every remaining prime, it generates all cyclic rotations of the decimal representation and tests every rotated value for primality.
The three languages use different syntax for the rotation step, but mathematically they are doing the same thing: computing \(n,R(n),\dots,R^{k-1}(n)\) and requiring all of them to be prime. When a rotated value lies inside the sieve table, the implementation reads the answer directly from the table.
If a user reuses the same programs with a smaller custom bound, a rotation can land beyond the sieve range even though the original number is below the limit. In that case the implementations fall back to ordinary trial division, which preserves correctness for general bounds. For the Project Euler target \(10^6\), every rotation still has at most six digits, so the sieve usually handles the whole job.
Before reporting the final total, the programs verify two small checkpoints: 197 must be recognized as circular, and the number of circular primes below 100 must be 13. Those checks match the mathematics exactly and guard against mistakes in the rotation logic.
If the search limit is \(L\), building the sieve costs \(O(L \log\log L)\) time and \(O(L)\) space. After that, only prime candidates survive the first filter, so the outer scan effectively visits \(\pi(L)\) numbers.
For a \(k\)-digit prime, the literal implementations construct \(k\) rotated strings and convert them back to integers, so the orbit check is \(O(k^2)\) character-level work in the straightforward string model. Under the Project Euler bound \(L=10^6\), we always have \(k \le 6\), so this is a tiny constant. In practice the runtime is dominated by the sieve and a short scan over the roughly \(78{,}498\) primes below one million.
Eine zirkuläre Primzahl ist eine Primzahl, deren jede zyklische Ziffernrotation ebenfalls prim ist. Für \(n=197\) erhält man die Rotationen \(197\), \(971\) und \(719\); daher ist 197 zirkulär. Gesucht ist die Anzahl aller zirkulären Primzahlen unter \(10^6\).
Wichtig ist die Zählweise: Gesucht sind einzelne Primzahlen, nicht Rotationsklassen. Deshalb trägt die Bahn \(\{197,971,719\}\) den Wert 3 bei, während 11 nur 1 beiträgt, weil seine beiden Rotationen numerisch gleich sind.
Schreibe eine \(k\)-stellige Zahl als \(n=d_0d_1\cdots d_{k-1}\). Zirkuläre Primzahlen lassen sich am besten über die Bahn beschreiben, die entsteht, wenn man die linke Ziffer jeweils ans Ende verschiebt.
Definiere die Linksrotation durch
$$R(d_0d_1\cdots d_{k-1})=d_1d_2\cdots d_{k-1}d_0.$$
Dann ist \(n\) genau dann zirkulär, wenn jedes Element der endlichen Bahn
$$\{n,R(n),R^2(n),\dots,R^{k-1}(n)\}$$
prim ist. Nach \(k\) Rotationen ist die ursprüngliche Anordnung wieder erreicht, also \(R^k(n)=n\).
Arithmetisch lässt sich dieselbe Operation so schreiben: Hat \(n\) genau \(k\) Stellen und ist \(P=10^{k-1}\), dann gilt
$$R(n)=10\left(n \bmod P\right)+\left\lfloor \frac{n}{P} \right\rfloor.$$
Meist hat eine solche Bahn Größe \(k\). Wiederholte Ziffern können sie aber verkürzen; bei \(11\) bleibt die Zahl unter Rotation fest, also hat die Bahn trotz zweier Stellen Größe 1.
Hat eine zirkuläre Primzahl mindestens zwei Stellen und enthält sie eine Ziffer aus \(\{0,2,4,5,6,8\}\), dann gibt es eine Rotation, in der genau diese Ziffer an der Einerstelle steht. Die rotierte Zahl ist dann durch 2 oder 5 teilbar und somit nicht prim. Also dürfen mehrstellige zirkuläre Primzahlen nur Ziffern aus
$$\{1,3,7,9\}$$
verwenden.
Ein zweites Invarianzargument nutzt die Ziffernsumme. Rotationen ändern die Ziffernsumme nicht und damit auch nicht den Rest modulo 3. Wäre die Ziffernsumme durch 3 teilbar, dann wäre jede Rotation durch 3 teilbar. Die einzige mögliche Ausnahme ist daher die einstellige Primzahl 3. Auch das erklärt, warum zirkuläre Primzahlen sehr selten sind.
Die vorliegenden Implementierungen kodieren diese Filter nicht ausdrücklich, weil die direkte Suche unter einer Million ohnehin schnell genug ist. Mathematisch erklären sie aber sehr klar, warum die vollständige Durchmusterung nur wenige Treffer liefert.
Wenn ein Element einer Rotationsbahn zirkulär ist, dann gilt das automatisch für alle Elemente derselben Bahn, weil sie dieselbe Rotationsmenge besitzen. Die Aufgabe fragt jedoch nicht nach der Zahl verschiedener Bahnen, sondern nach der Zahl der zirkulären Primzahlen selbst.
Darum trägt die Bahn \(\{197,971,719\}\) den Wert 3 zur Antwort bei, während die Bahn \(\{11\}\) den Wert 1 beiträgt. Genau deshalb ist es korrekt, jede Primzahl unterhalb der Schranke einzeln zu prüfen.
Für \(197\) lautet die Bahn
$$197 \to 971 \to 719 \to 197.$$
Alle drei verschiedenen Werte sind prim, also sind alle drei zirkuläre Primzahlen.
Für \(101\) erhält man die Rotationen \(101\), \(011\) und \(110\). Numerisch sind das \(101\), \(11\) und \(110\). Da \(110\) zusammengesetzt ist, ist 101 nicht zirkulär. Dieses Beispiel zeigt zugleich, warum eine Nullziffer unmöglich ist und warum die Rückumwandlung einer rotieren Ziffernfolge in eine Zahl keine Mehrdeutigkeit verursacht.
Die vollständige Suche unter \(10^6\) liefert insgesamt 55 zirkuläre Primzahlen.
Die C++-, Python- und Java-Implementierungen bauen zuerst ein Sieb des Eratosthenes auf, das etwas über die gewünschte Suchgrenze hinausreicht. Dadurch können die meisten Primzahltests später per Tabellenzugriff in konstanter Zeit beantwortet werden.
Anschließend laufen die Programme über alle Zahlen unterhalb der Grenze und überspringen sofort alles, was das Sieb schon als zusammengesetzt markiert. Für jede verbleibende Primzahl werden alle zyklischen Rotationen der Dezimaldarstellung erzeugt und einzeln auf Primheit geprüft.
Die drei Sprachversionen unterscheiden sich nur syntaktisch. Inhaltlich berechnen sie dieselbe Bahn \(n,R(n),\dots,R^{k-1}(n)\) und verlangen, dass jeder dieser Werte prim ist. Liegt eine Rotation innerhalb des Siebbereichs, wird direkt im Sieb nachgesehen.
Wird dasselbe Programm mit einer kleineren benutzerdefinierten Grenze verwendet, kann eine Rotation außerhalb des Siebs liegen, obwohl die ursprüngliche Zahl noch unter der Grenze liegt. Dann greifen die Implementierungen auf einfache Probedivision zurück. Für das Projekt-Euler-Ziel \(10^6\) behalten alle Rotationen höchstens sechs Stellen, sodass das Sieb praktisch die gesamte Arbeit erledigt.
Vor der Endausgabe prüfen die Programme zwei kleine Referenzfälle: 197 muss als zirkulär erkannt werden, und unter 100 muss die Anzahl 13 sein. Diese Tests stimmen exakt mit der Mathematik überein und schützen die Rotationslogik vor Off-by-one-Fehlern.
Für eine Suchgrenze \(L\) kostet der Aufbau des Siebs \(O(L \log\log L)\) Zeit und \(O(L)\) Speicher. Danach bleiben im äußeren Durchlauf effektiv nur \(\pi(L)\) Primkandidaten übrig.
Für eine \(k\)-stellige Primzahl erzeugen die konkreten Implementierungen \(k\) rotierte Zeichenketten und wandeln sie wieder in ganze Zahlen um. Im naiven Stringmodell kostet die Bahnenprüfung daher \(O(k^2)\) elementare Zeichenoperationen. Unter der Euler-Schranke \(L=10^6\) gilt jedoch stets \(k \le 6\), also ist dieser Anteil nur eine kleine Konstante. Praktisch dominiert das Sieb zusammen mit einem kurzen Durchlauf über die ungefähr \(78{,}498\) Primzahlen unter einer Million.
Dairesel asal, basamaklarının her döngüsel kaydırması da asal kalan sayıdır. \(n=197\) için döndürmeler \(197\), \(971\) ve \(719\) olur; bu yüzden 197 daireseldir. Amaç, \(10^6\) altındaki bütün dairesel asalları saymaktır.
Buradaki önemli sayım ayrıntısı şudur: soru döndürme sınıflarını değil, tek tek asal sayıları sayar. Bu nedenle \(\{197,971,719\}\) yörüngesi 3 katkı yapar; 11 ise iki döndürmesi sayısal olarak aynı çıktığı için 1 katkı yapar.
\(k\) basamaklı bir sayıyı \(n=d_0d_1\cdots d_{k-1}\) biçiminde yazalım. Dairesel asallar, en soldaki basamağı sona taşıyan döngüsel dönüşümün ürettiği yörünge üzerinden doğal biçimde açıklanır.
Bir adımlık sola döndürmeyi
$$R(d_0d_1\cdots d_{k-1})=d_1d_2\cdots d_{k-1}d_0$$
olarak tanımlayalım. O zaman \(n\), ancak ve ancak sonlu yörünge
$$\{n,R(n),R^2(n),\dots,R^{k-1}(n)\}$$
içindeki her eleman asalsa daireseldir. \(k\) kez döndürünce başlangıç dizilişine dönülür; yani \(R^k(n)=n\).
Aynı işlem aritmetik olarak da yazılabilir. \(n\) tam \(k\) basamaklı olsun ve \(P=10^{k-1}\) olsun. O zaman
$$R(n)=10\left(n \bmod P\right)+\left\lfloor \frac{n}{P} \right\rfloor.$$
Çoğu durumda yörüngenin boyu \(k\) olur; fakat tekrar eden basamaklar bu boyu küçültebilir. Örneğin \(11\), döndürme altında değişmez, dolayısıyla iki basamaklı olmasına rağmen yörünge boyu 1'dir.
En az iki basamaklı bir dairesel asalın herhangi bir basamağı \(\{0,2,4,5,6,8\}\) kümesinden gelirse, bir döndürme o basamağı birler hanesine taşır. Ortaya çıkan sayı 2'ye ya da 5'e bölünür ve asal olamaz. Demek ki çok basamaklı her dairesel asalın bütün basamakları
$$\{1,3,7,9\}$$
kümesinden gelmek zorundadır.
İkinci bir değişmez de basamak toplamıdır. Döndürmeler basamak toplamını değiştirmez; dolayısıyla mod 3 kalanı da değişmez. Basamak toplamı 3'e bölünebilseydi bütün döndürmeler 3'e bölünürdü. Bunun tek olası istisnası tek basamaklı asal 3'tür. Bu gözlem dairesel asalların neden bu kadar seyrek olduğunu da açıklar.
Verilen uygulamalar bu filtreleri açıkça kullanmaz; çünkü bir milyon altındaki doğrudan tarama zaten yeterince ucuzdur. Yine de bu gerçekler, kaba kuvvet yaklaşımının neden pratikte çok hızlı olduğunu doğru matematiksel açıdan gösterir.
Bir döndürme yörüngesindeki sayılardan biri daireselse, aynı yörüngedeki bütün sayılar da daireseldir; çünkü hepsi aynı döndürme kümesini paylaşır. Fakat soru farklı yörünge sayısını değil, dairesel asal sayıların kendisini ister.
Bu yüzden \(\{197,971,719\}\) yörüngesi cevaba 3 ekler, \(\{11\}\) yörüngesi ise 1 ekler. Sınırın altındaki her asal sayıyı tek tek test eden doğrudan yöntem tam da bu nedenle doğru toplamı verir.
\(197\) için yörünge
$$197 \to 971 \to 719 \to 197$$
şeklindedir. Üç farklı değerin üçü de asaldır; dolayısıyla her biri dairesel asaldır.
\(101\) için döndürmeler \(101\), \(011\) ve \(110\) olur. Bunların sayısal karşılığı \(101\), \(11\) ve \(110\)'dur. \(110\) bileşik olduğundan 101 dairesel değildir. Bu örnek hem sıfır basamağının neden imkansız olduğunu hem de döndürülmüş basamak dizisini sayıya çevirdiğimizde bir belirsizlik oluşmadığını gösterir.
\(10^6\) altındaki tam tarama sonunda toplam 55 dairesel asal elde edilir.
C++, Python ve Java uygulamaları önce istenen sınırın biraz ötesine kadar bir Eratosthenes eleği kurar. Böylece ana döngü sırasında yapılan asallık sorgularının çoğu sabit zamanda tablo üzerinden cevaplanır.
Daha sonra uygulamalar sınırın altındaki sayıları sırayla gezer ve eleğin bileşik olarak işaretlediği değerleri hemen atlar. Geriye kalan her asal için ondalık gösterimin bütün döngüsel döndürmeleri üretilir ve her döndürmenin asal olup olmadığı tek tek denetlenir.
Üç dildeki sözdizimi farklı olsa da matematik aynı kalır: \(n,R(n),\dots,R^{k-1}(n)\) hesaplanır ve bu değerlerin hepsinin asal olması istenir. Döndürülmüş değer elek tablosunun içinde kalıyorsa sonuç doğrudan tablodan okunur.
Aynı programlar daha küçük bir özel sınırla yeniden kullanılırsa, başlangıç sayısı sınırın altında olsa bile bir döndürme eleğin dışına taşabilir. Bu durumda uygulamalar normal deneme bölmesiyle asallık testi yapar. Project Euler'deki \(10^6\) hedefinde ise bütün döndürmeler en çok altı basamaklı kaldığından, işin neredeyse tamamını elek üstlenir.
Sonucu yazdırmadan önce programlar iki küçük referans kontrolü yapar: 197 dairesel olarak tanınmalı ve 100'ün altındaki dairesel asal sayısı 13 çıkmalıdır. Bu kontroller matematiksel tanımla bire bir uyumludur ve döndürme mantığındaki kayma hatalarını yakalamaya yardım eder.
Arama sınırı \(L\) ise eleği kurmanın maliyeti \(O(L \log\log L)\) zaman ve \(O(L)\) bellektir. Bundan sonra dış taramada etkili biçimde yalnızca \(\pi(L)\) kadar asal aday kalır.
\(k\) basamaklı bir asal için bu doğrudan uygulamalar \(k\) adet döndürülmüş dize üretir ve bunları tekrar tam sayıya çevirir. Dolayısıyla basit dize modelinde yörünge testi \(O(k^2)\) karakter işlemi gerektirir. Fakat Euler sınırında \(L=10^6\) için her zaman \(k \le 6\) olduğundan bu kısım çok küçük bir sabittir. Pratikte süreyi esas olarak elek ve bir milyonun altındaki yaklaşık \(78{,}498\) asal üzerinde yapılan kısa tarama belirler.
Un primo circular es un número primo cuyas rotaciones cíclicas de dígitos también son primas. Si \(n=197\), las rotaciones son \(197\), \(971\) y \(719\), así que 197 es circular. La tarea consiste en contar todos los primos circulares menores que \(10^6\).
El detalle importante del conteo es que se piden primos individuales, no clases de rotación. Por eso la órbita \(\{197,971,719\}\) aporta 3, mientras que 11 aporta 1 porque sus dos rotaciones coinciden numéricamente.
Escribamos un número de \(k\) cifras como \(n=d_0d_1\cdots d_{k-1}\). Los primos circulares se describen de manera natural mediante la órbita generada al mover la cifra más a la izquierda al final.
Definimos la rotación a la izquierda de un paso por
$$R(d_0d_1\cdots d_{k-1})=d_1d_2\cdots d_{k-1}d_0.$$
Entonces \(n\) es circular si y solo si todos los elementos de la órbita finita
$$\{n,R(n),R^2(n),\dots,R^{k-1}(n)\}$$
son primos. Después de \(k\) rotaciones se recupera el orden inicial, de modo que \(R^k(n)=n\).
La misma operación admite una forma aritmética. Si \(n\) tiene exactamente \(k\) cifras y \(P=10^{k-1}\), entonces
$$R(n)=10\left(n \bmod P\right)+\left\lfloor \frac{n}{P} \right\rfloor.$$
En la mayoría de los casos la órbita tiene tamaño \(k\), pero las cifras repetidas pueden reducirlo. Por ejemplo, \(11\) permanece fijo bajo la rotación, así que su órbita tiene tamaño 1 aunque el número tenga dos cifras.
Supongamos que un primo circular tiene al menos dos cifras. Si una de sus cifras estuviera en \(\{0,2,4,5,6,8\}\), alguna rotación la colocaría en la posición de las unidades. El número rotado sería entonces divisible por 2 o por 5, así que no podría ser primo. Por lo tanto, todo primo circular de varias cifras solo puede usar cifras de
$$\{1,3,7,9\}.$$
Hay además un segundo invariante útil: la suma de cifras no cambia bajo las rotaciones. En consecuencia, tampoco cambia el residuo módulo 3. Si la suma de cifras fuese divisible por 3, entonces todas las rotaciones serían divisibles por 3. La única excepción posible es el primo de una sola cifra 3. Esta observación explica por qué los primos circulares son tan escasos.
Las implementaciones dadas no aplican estos filtros de forma explícita, porque el barrido directo por debajo de un millón ya es suficientemente rápido. Aun así, estos hechos dan la explicación matemática correcta de por qué la búsqueda exhaustiva termina tan pronto.
Si un elemento de una órbita de rotación es circular, entonces todos los elementos de esa misma órbita también lo son, porque comparten exactamente el mismo conjunto de rotaciones. Sin embargo, el problema no pide el número de órbitas distintas, sino el número de primos circulares propiamente dichos.
Por eso la órbita \(\{197,971,719\}\) contribuye 3 a la respuesta, mientras que la órbita \(\{11\}\) contribuye 1. Esta es la razón matemática por la que basta recorrer cada primo menor que el límite y comprobarlo por separado.
Para \(197\), la órbita es
$$197 \to 971 \to 719 \to 197.$$
Los tres valores distintos son primos, así que cada uno de ellos es un primo circular.
Para \(101\), las rotaciones son \(101\), \(011\) y \(110\). Numéricamente esto significa \(101\), \(11\) y \(110\). Como \(110\) es compuesto, 101 no es circular. El ejemplo muestra a la vez por qué una cifra 0 es imposible y por qué convertir la rotación a entero no introduce ninguna ambigüedad en la prueba de primalidad.
La búsqueda completa por debajo de \(10^6\) produce en total 55 primos circulares.
Las implementaciones en C++, Python y Java empiezan construyendo un tamiz de Eratóstenes un poco más allá del límite de búsqueda solicitado. Esa tabla permite responder la mayoría de las consultas de primalidad en tiempo constante.
Después recorren los enteros por debajo del límite y descartan de inmediato cualquier valor que el tamiz ya marque como compuesto. Para cada primo restante generan todas las rotaciones cíclicas de su representación decimal y comprueban la primalidad de cada valor rotado.
Las tres versiones usan sintaxis distintas, pero matemáticamente hacen lo mismo: calcular \(n,R(n),\dots,R^{k-1}(n)\) y exigir que todos esos valores sean primos. Cuando una rotación todavía cae dentro de la tabla del tamiz, la respuesta se lee directamente allí.
Si alguien reutiliza los programas con un límite personalizado más pequeño, una rotación puede quedar fuera del tamiz aunque el número original siga estando por debajo del límite. En ese caso las implementaciones recurren a una prueba sencilla por división de ensayo. Para el objetivo de Project Euler \(10^6\), todas las rotaciones siguen teniendo como mucho seis cifras, de modo que el tamiz resuelve prácticamente todo.
Antes de dar el total final, los programas comprueban dos casos pequeños: 197 debe identificarse como circular y el número de primos circulares menores que 100 debe ser 13. Esas comprobaciones coinciden exactamente con la definición matemática y protegen la lógica de rotación frente a errores sutiles.
Si el límite de búsqueda es \(L\), construir el tamiz cuesta \(O(L \log\log L)\) tiempo y \(O(L)\) espacio. Después de ese filtrado inicial, el recorrido exterior trata efectivamente con \(\pi(L)\) candidatos primos.
Para un primo de \(k\) cifras, estas implementaciones literales construyen \(k\) cadenas rotadas y las convierten otra vez en enteros, de modo que la comprobación de la órbita cuesta \(O(k^2)\) trabajo a nivel de caracteres en el modelo directo de cadenas. Bajo el límite de Euler \(L=10^6\), siempre se cumple \(k \le 6\), así que ese factor es una constante muy pequeña. En la práctica domina el tamiz junto con un recorrido corto sobre los aproximadamente \(78{,}498\) primos menores que un millón.
循环素数指的是这样一种素数：把它的十进制数字做任意循环移位之后，得到的数仍然全部是素数。比如 \(n=197\) 时，旋转结果是 \(197\)、\(971\) 和 \(719\)，所以 197 是循环素数。题目要求统计所有小于 \(10^6\) 的循环素数。
这里有一个很关键的计数细节：题目统计的是具体的素数个数，而不是不同旋转轨道的个数。因此轨道 \(\{197,971,719\}\) 贡献 3，而 11 只贡献 1，因为它的两个旋转在数值上其实是同一个数。
把一个 \(k\) 位数写成 \(n=d_0d_1\cdots d_{k-1}\)。对于本题，最自然的数学对象不是单个数字本身，而是不断把最左边一位移到末尾所形成的有限旋转轨道。
定义一步左旋为
$$R(d_0d_1\cdots d_{k-1})=d_1d_2\cdots d_{k-1}d_0.$$
那么 \(n\) 是循环素数，当且仅当有限集合
$$\{n,R(n),R^2(n),\dots,R^{k-1}(n)\}$$
中的每一个元素都是素数。因为旋转 \(k\) 次之后数字排列会回到原状，所以 \(R^k(n)=n\)。
同一个操作也可以写成纯算术形式。若 \(n\) 恰好有 \(k\) 位，且 \(P=10^{k-1}\)，则
$$R(n)=10\left(n \bmod P\right)+\left\lfloor \frac{n}{P} \right\rfloor.$$
大多数时候，轨道大小就是 \(k\)。但如果数字有重复，轨道可能更短。比如 \(11\) 在旋转后仍然是 \(11\)，所以虽然它有两位，轨道大小却只有 1。
设一个循环素数至少有两位。如果它包含 \(\{0,2,4,5,6,8\}\) 中的某一位，那么总可以通过某次旋转把这一位放到个位上。这样得到的数就会被 2 或 5 整除，因此不可能是素数。所以所有多位循环素数的每一位都必须来自
$$\{1,3,7,9\}.$$
还有一个很有用的不变量是数位和。旋转不会改变数位和，因此也不会改变模 3 的余数。如果一个多位数的数位和能被 3 整除，那么它的所有旋转也都能被 3 整除，于是它不可能成为循环素数。唯一的例外只能是单独的素数 3。这也解释了为什么循环素数会如此稀少。
题目给出的实现并没有把这些筛选条件显式写进主算法，因为在一百万以内直接扫描已经足够快了。但从数学上看，这些限制准确说明了为什么朴素枚举依然很高效。
如果某个旋转轨道中的一个数是循环素数，那么同一轨道中的其他数也一定是循环素数，因为它们拥有完全相同的一组旋转结果。可是题目并不是问有多少个不同的轨道，而是问有多少个循环素数。
因此 \(\{197,971,719\}\) 这一轨道要向答案贡献 3，而 \(\{11\}\) 这一轨道只贡献 1。也正因为如此，直接遍历所有小于上界的素数并分别检查它们，恰好就是正确的计数方式。
对 \(197\) 而言，轨道是
$$197 \to 971 \to 719 \to 197.$$
这三个不同的数全部都是素数，所以它们每一个都是循环素数。
对 \(101\) 而言，旋转结果是 \(101\)、\(011\) 和 \(110\)。把它们按数值解释后就是 \(101\)、\(11\) 和 \(110\)。因为 \(110\) 是合数，所以 101 不是循环素数。这个例子同时说明了两件事：一是为什么数字 0 会立即破坏循环素数性质，二是为什么把旋转后的字符串再转回整数并不会影响最终的素性判断。
把所有小于 \(10^6\) 的候选都检查完以后，最终总数是 55。
C++、Python 和 Java 三个实现都会先构造一个略大于目标上界的埃拉托斯特尼筛。这样在主循环里，大部分素性查询都可以直接通过数组查表完成。
随后实现会按顺序扫描所有小于上界的整数，并立即跳过那些已经被筛标记为合数的值。对每一个留下来的素数，程序都会生成它十进制表示的所有循环旋转，并逐个检查这些旋转后的值是否仍然是素数。
三种语言在语法上略有不同，但数学内容完全一致：它们都在计算 \(n,R(n),\dots,R^{k-1}(n)\)，并要求这一整条轨道上的数全部为素数。只要旋转后的值仍在筛表范围内，就直接查表。
如果把同样的程序拿去处理一个更小的自定义上界，原始数字虽然还在范围内，某个旋转结果却可能落到筛表之外。为保证一般情况下仍然正确，实现这时会退回到普通的试除法。对 Project Euler 的 \(10^6\) 目标来说，所有旋转结果都不会超过六位，因此筛表几乎足以完成全部工作。
在输出最终计数之前，程序还会先验证两个小检查点：197 必须被判定为循环素数，而 100 以下的循环素数个数必须是 13。这两个检查和数学定义完全一致，能够防止旋转逻辑里出现细微的边界错误。
若搜索上界为 \(L\)，构造筛需要 \(O(L \log\log L)\) 时间和 \(O(L)\) 空间。完成这一步之后，外层扫描实际只需要认真处理 \(\pi(L)\) 个素数候选。
对于一个 \(k\) 位素数，当前这几份实现会构造 \(k\) 个旋转字符串，并把它们重新解析为整数，因此在直接的字符串模型下，一次轨道检查需要 \(O(k^2)\) 的字符级工作量。可是在 Euler 的范围 \(L=10^6\) 内始终有 \(k \le 6\)，所以这部分只是一个很小的常数。实际运行时，主要成本来自筛法本身，以及对大约 \(78{,}498\) 个百万以内素数所做的那一遍短扫描。
Круговое простое число - это простое число, у которого любая циклическая перестановка цифр тоже является простым числом. Если \(n=197\), то получаем вращения \(197\), \(971\) и \(719\), поэтому 197 является круговым простым. Нужно посчитать все такие числа, меньшие \(10^6\).
Ключевая деталь подсчета состоит в том, что требуется считать сами простые числа, а не разные классы вращений. Поэтому орбита \(\{197,971,719\}\) дает вклад 3, а число 11 дает вклад 1, поскольку его две ротации численно совпадают.
Запишем \(k\)-значное число в виде \(n=d_0d_1\cdots d_{k-1}\). Для этой задачи естественно рассматривать не число само по себе, а конечную орбиту, возникающую при переносе самой левой цифры в конец.
Определим одно левое вращение так:
$$R(d_0d_1\cdots d_{k-1})=d_1d_2\cdots d_{k-1}d_0.$$
Тогда число \(n\) является круговым простым тогда и только тогда, когда каждый элемент конечной орбиты
$$\{n,R(n),R^2(n),\dots,R^{k-1}(n)\}$$
прост. После \(k\) вращений порядок цифр возвращается к исходному, то есть \(R^k(n)=n\).
Ту же операцию можно записать арифметически. Если у \(n\) ровно \(k\) цифр и \(P=10^{k-1}\), то
$$R(n)=10\left(n \bmod P\right)+\left\lfloor \frac{n}{P} \right\rfloor.$$
Обычно размер орбиты равен \(k\), но повторяющиеся цифры могут его уменьшить. Например, \(11\) при вращении не меняется, поэтому его орбита имеет размер 1, хотя число двузначное.
Пусть круговое простое имеет хотя бы две цифры. Если среди его цифр есть элемент из \(\{0,2,4,5,6,8\}\), то некоторый сдвиг поставит эту цифру на последнее место. Тогда получившееся число будет делиться на 2 или на 5, а значит, не будет простым. Следовательно, каждая цифра многозначного кругового простого должна принадлежать множеству
$$\{1,3,7,9\}.$$
Есть и второй полезный инвариант: сумма цифр при вращениях не меняется, а значит, не меняется и остаток по модулю 3. Если бы сумма цифр делилась на 3, то все вращения делились бы на 3. Единственное возможное исключение - однозначное простое число 3. Это еще одна причина редкости круговых простых.
Данные реализации не используют эти фильтры явно, потому что прямой перебор ниже миллиона и без того работает быстро. Но именно эти факты дают правильное математическое объяснение эффективности полного перебора.
Если один элемент некоторой орбиты является круговым простым, то и все остальные элементы этой же орбиты тоже являются круговыми простыми, поскольку набор вращений у них одинаковый. Однако задача спрашивает не число различных орбит, а число самих круговых простых чисел.
Поэтому орбита \(\{197,971,719\}\) добавляет к ответу 3, а орбита \(\{11\}\) добавляет 1. Именно по этой причине достаточно пройти по всем простым числам ниже границы и проверять их по отдельности.
Для \(197\) орбита имеет вид
$$197 \to 971 \to 719 \to 197.$$
Все три различных значения просты, значит, каждое из них является круговым простым.
Для \(101\) вращения равны \(101\), \(011\) и \(110\). Численно это \(101\), \(11\) и \(110\). Поскольку \(110\) составное, 101 не является круговым простым. Этот пример одновременно показывает, почему цифра 0 недопустима и почему обратное преобразование повернутой строки цифр в число не создает двусмысленности для проверки простоты.
Полный перебор всех чисел ниже \(10^6\) дает итоговый ответ 55.
Реализации на C++, Python и Java сначала строят решето Эратосфена немного дальше заданной границы поиска. Благодаря этому большинство запросов на проверку простоты в основном цикле обрабатывается обычным обращением к таблице.
Затем программы проходят по всем числам ниже предела и сразу отбрасывают все, что решето уже отметило как составное. Для каждого оставшегося простого числа генерируются все циклические вращения его десятичной записи, и каждое такое значение проверяется на простоту.
Синтаксис в трех языках различается, но математически выполняется одно и то же: вычисляются \(n,R(n),\dots,R^{k-1}(n)\), и требуется, чтобы все эти числа были простыми. Если вращение попадает в диапазон решета, ответ берется напрямую из таблицы.
Если те же программы использовать с меньшей пользовательской границей, то может случиться, что исходное число еще лежит ниже предела, а одно из вращений уже выходит за границы решета. Тогда реализации переходят к обычному тесту делением на пробные делители. Для целевого случая \(10^6\) все вращения по-прежнему остаются шестизначными или короче, поэтому решето почти всегда покрывает весь процесс.
Перед выводом окончательного результата программы проверяют два маленьких контрольных факта: число 197 обязано распознаваться как круговое простое, а количество круговых простых ниже 100 должно равняться 13. Эти проверки точно соответствуют математическому определению и помогают поймать ошибки в логике вращения.
Если граница поиска равна \(L\), построение решета занимает \(O(L \log\log L)\) времени и \(O(L)\) памяти. После этого внешнему проходу фактически остаются только \(\pi(L)\) простых кандидатов.
Для \(k\)-значного простого числа данные прямые реализации создают \(k\) повернутых строк и снова преобразуют их в целые числа, поэтому в наивной строковой модели проверка орбиты требует \(O(k^2)\) элементарных символьных операций. При ограничении Euler \(L=10^6\) всегда выполнено \(k \le 6\), так что этот множитель является очень маленькой константой. На практике время определяется решетом и коротким проходом по примерно \(78{,}498\) простым числам ниже миллиона.
العدد الأولي الدائري هو عدد أولي تبقى جميع دورانات أرقامه الدورية أعدادًا أولية أيضًا. إذا كان \(n=197\)، فإن الدورانات هي \(197\) و\(971\) و\(719\)، ولذلك يكون 197 عددًا أوليًا دائريًا. المطلوب هو عد جميع الأعداد الأولية الدائرية الأصغر من \(10^6\).
والتفصيل المهم هنا هو أن المسألة تعد الأعداد الأولية نفسها، لا فئات الدوران المختلفة. لهذا تسهم المداراة \(\{197,971,719\}\) بمقدار 3، بينما يسهم العدد 11 بمقدار 1 فقط لأن دورانَيْه يتطابقان عدديًا.
لنكتب عددًا مكوّنًا من \(k\) خانات على الصورة \(n=d_0d_1\cdots d_{k-1}\). أفضل طريقة لفهم المسألة هي النظر إلى المدار الناتج من نقل الخانة اليسرى في كل مرة إلى النهاية.
نعرّف التدوير اليساري بخطوة واحدة كما يأتي:
$$R(d_0d_1\cdots d_{k-1})=d_1d_2\cdots d_{k-1}d_0.$$
وعندئذ يكون \(n\) عددًا أوليًا دائريًا إذا وفقط إذا كان كل عنصر في المدار المنتهي
$$\{n,R(n),R^2(n),\dots,R^{k-1}(n)\}$$
عددًا أوليًا. وبعد \(k\) تدويرات نعود إلى الترتيب الأصلي، أي إن \(R^k(n)=n\).
ويمكن كتابة العملية نفسها بصورة حسابية. إذا كان \(n\) ذا \(k\) خانات تمامًا، ولتكن \(P=10^{k-1}\)، فإن
$$R(n)=10\left(n \bmod P\right)+\left\lfloor \frac{n}{P} \right\rfloor.$$
في معظم الحالات يكون حجم المدار هو \(k\)، لكن تكرار الخانات قد يقلله. فالعدد \(11\) مثلًا يبقى كما هو بعد التدوير، لذلك حجم مداره يساوي 1 رغم أنه مكوّن من خانتين.
إذا كان لدينا عدد أولي دائري مكوّن من خانتين أو أكثر، واحتوى على خانة من المجموعة \(\{0,2,4,5,6,8\}\)، فستوجد تدويرة تضع تلك الخانة في منزلة الآحاد. عندئذ يصبح العدد الناتج قابلًا للقسمة على 2 أو 5، وبالتالي لا يمكن أن يكون أوليًا. إذن كل عدد أولي دائري متعدد الخانات لا بد أن تكون جميع خاناته من
$$\{1,3,7,9\}.$$
وهناك ثابت آخر مفيد هو مجموع الخانات. فالدوران لا يغيّر مجموع الخانات، ومن ثم لا يغيّر الباقي modulo 3 أيضًا. فإذا كان مجموع الخانات قابلًا للقسمة على 3، فإن جميع الدورانات ستكون قابلة للقسمة على 3. والاستثناء الوحيد الممكن هو العدد الأولي الأحادي 3. وهذا يفسر لماذا تكون الأعداد الأولية الدائرية نادرة جدًا.
التنفيذات المعطاة لا تستعمل هذه المرشحات صراحة، لأن المسح المباشر تحت المليون سريع بما يكفي أصلًا. لكن هذه الحقائق تعطي الصورة الرياضية الدقيقة لسبب نجاح البحث الشامل بهذه السرعة.
إذا كان عنصر واحد من مدار دوران ما عددًا أوليًا دائريًا، فإن بقية عناصر المدار نفسه تكون كذلك أيضًا، لأنها تشترك في مجموعة الدورانات نفسها. لكن المسألة لا تطلب عدد المدارات المختلفة، بل عدد الأعداد الأولية الدائرية ذاتها.
ولهذا فإن المدار \(\{197,971,719\}\) يضيف 3 إلى الجواب، بينما يضيف المدار \(\{11\}\) القيمة 1 فقط. ومن هنا تأتي صحة الطريقة المباشرة التي تختبر كل عدد أولي تحت الحد على حدة.
بالنسبة إلى \(197\)، يكون المدار
$$197 \to 971 \to 719 \to 197.$$
وجميع هذه القيم الثلاثة أولية، لذلك كل واحدة منها عدد أولي دائري.
أما \(101\)، فدوراناته هي \(101\) و\(011\) و\(110\). وعند تفسيرها عدديًا نحصل على \(101\) و\(11\) و\(110\). وبما أن \(110\) عدد مركب، فإن 101 ليس عددًا أوليًا دائريًا. يوضح هذا المثال في الوقت نفسه لماذا تكون الخانة 0 مفسدة لهذه الخاصية، ولماذا لا يسبب تحويل السلسلة المدورة مرة أخرى إلى عدد صحيح أي التباس في اختبار الأولية.
وعند إكمال الفحص لكل الأعداد الأصغر من \(10^6\)، يكون المجموع النهائي 55.
تبدأ تنفيذات C++ وPython وJava ببناء منخل إراتوستينس حتى حد يزيد قليلًا على حد البحث المطلوب. وهذا يسمح بالإجابة عن معظم اختبارات الأولية في الحلقة الرئيسية بمجرد الرجوع إلى جدول جاهز.
بعد ذلك تمر التنفيذات على جميع الأعداد الأصغر من الحد وتستبعد فورًا كل قيمة سبق للمنخل أن وسمها بأنها مركبة. ولكل عدد أولي باقٍ، تُنشأ جميع الدورانات الدورية لتمثيله العشري، ثم يُفحص كل عدد ناتج لمعرفة ما إذا كان أوليًا.
تختلف الصياغة بين اللغات الثلاث، لكن المحتوى الرياضي واحد: تُحسب القيم \(n,R(n),\dots,R^{k-1}(n)\)، ويُشترط أن تكون كلها أولية. فإذا بقيت القيمة المدورة داخل مجال المنخل، تُؤخذ النتيجة مباشرة من الجدول.
وإذا استُعملت البرامج نفسها مع حد مخصص أصغر، فقد تقع إحدى الدورانات خارج مجال المنخل رغم أن العدد الأصلي ما زال دون الحد. في هذه الحالة تعود التنفيذات إلى القسمة التجريبية العادية. أما في مسألة Project Euler عند \(10^6\)، فكل الدورانات تبقى في حدود ست خانات على الأكثر، ولذلك يغطي المنخل تقريبًا جميع الحالات.
قبل طباعة المجموع النهائي، تتحقق البرامج من حقيقتين صغيرتين: يجب التعرف على 197 بوصفه عددًا أوليًا دائريًا، ويجب أن يكون عدد الأعداد الأولية الدائرية تحت 100 مساويًا لـ 13. هذان الاختباران يطابقان التعريف الرياضي تمامًا ويساعدان على كشف الأخطاء الدقيقة في منطق التدوير.
إذا كان حد البحث هو \(L\)، فإن بناء المنخل يحتاج إلى زمن \(O(L \log\log L)\) ومساحة \(O(L)\). وبعد هذه الخطوة لا يبقى في الحلقة الخارجية فعليًا إلا \(\pi(L)\) من المرشحين الأوليين.
ولعدد أولي مكوّن من \(k\) خانات، تنشئ هذه التنفيذات المباشرة \(k\) سلاسل مدورة ثم تحوّلها من جديد إلى أعداد صحيحة، ولذلك تكون كلفة فحص المدار \(O(k^2)\) على مستوى العمليات الحرفية في نموذج السلاسل المباشر. وتحت حد Euler حيث \(L=10^6\)، يكون دائمًا \(k \le 6\)، لذا فإن هذا العامل ثابت صغير جدًا. عمليًا يهيمن المنخل مع المرور القصير على ما يقارب \(78{,}498\) عددًا أوليًا تحت المليون.