We seek primes \(p \lt 10^6\) such that there exists a positive integer \(n\) with \(n^3+n^2p\) equal to a perfect cube. Writing that cube as \(m^3\), the equation becomes
$$m^3-n^3=pn^2.$$
A naive search over pairs \((n,m)\) would be pointless, because the interesting part of the problem is structural: the prime factor \(p\) forces the difference of the two cubes into a very narrow form. Once that form is identified, the problem collapses to testing a short explicit sequence for primality.
The implementations rely on an exact characterization of all possible primes \(p\), not on a broad search. The whole argument comes from factoring the cube equation carefully and using the fact that \(p\) is prime.
Assume
$$m^3=n^3+pn^2,$$
with \(m,n \gt 0\). Since the right-hand side is larger than \(n^3\), we must have \(m \gt n\).
Let
$$d=\gcd(m,n),\qquad m=du,\qquad n=dv,\qquad \gcd(u,v)=1.$$
Substituting into the equation gives
$$d^3u^3-d^3v^3=pd^2v^2,$$
so after dividing by \(d^2\),
$$d(u^3-v^3)=pv^2.$$
Now \(\gcd(u,v)=1\) implies \(\gcd(u^3-v^3,v)=1\), because any common divisor of \(u^3-v^3\) and \(v\) would also divide \(u\). Therefore the factor \(v^2\) on the right must come entirely from \(d\). In particular,
$$v^2 \mid d.$$
Write
$$d=v^2c.$$
Then the previous equation becomes
$$c(u^3-v^3)=p.$$
Both factors on the left are positive integers. Because \(p\) is prime, there are only two possibilities: either \(c=1\) and \(u^3-v^3=p\), or \(c=p\) and \(u^3-v^3=1\).
The second case cannot happen for positive \(v\). If \(v \ge 1\), then the smallest possible positive cube difference is
$$ (v+1)^3-v^3 = 3v^2+3v+1 \ge 7.$$
So we must have
$$c=1,\qquad p=u^3-v^3,\qquad d=v^2.$$
This already tells us something strong: every valid prime is literally a difference of two cubes, and the associated \(n\) is
$$n=dv=v^3.$$
Factor the difference of cubes:
$$p=u^3-v^3=(u-v)(u^2+uv+v^2).$$
Because \(m \gt n\), we have \(u \gt v \ge 1\). The second factor is therefore greater than 1. Since \(p\) is prime, the first factor must be 1:
$$u-v=1.$$
Set \(v=k\), so \(u=k+1\). Then
$$p=(k+1)^3-k^3=3k^2+3k+1.$$
Conversely, whenever \(3k^2+3k+1\) is prime, choosing
$$n=k^3,\qquad m=k^2(k+1)$$
gives
$$n^3+n^2p=k^9+k^6(3k^2+3k+1)=k^6(k+1)^3=(k^2(k+1))^3=m^3.$$
So the condition is exact: the admissible primes are precisely the prime numbers of the form
$$p=3k^2+3k+1,\qquad k \ge 1.$$
These are often called Cuban primes of the first kind.
Take \(k=2\). Then
$$p=3(2)^2+3(2)+1=19,$$
and the construction gives
$$n=2^3=8,\qquad m=2^2\cdot 3=12.$$
Checking directly,
$$8^3+8^2\cdot 19=512+64\cdot 19=1728=12^3.$$
The small sample below 100 follows immediately from the same formula:
$$k=1,2,3,4 \Longrightarrow p=7,19,37,61,$$
while \(k=5\) gives \(p=91\), which is composite. That is why the sample count is 4.
To solve the actual problem, we only need values with
$$3k^2+3k+1 \lt 10^6.$$
The largest such integer is \(k=576\), because
$$3\cdot 576^2+3\cdot 576+1=997057 \lt 10^6,$$
whereas
$$3\cdot 577^2+3\cdot 577+1=1000519 \gt 10^6.$$
So there are only 576 candidates to test.
The C++, Python, and Java implementations do not search over arbitrary values of \(n\) or \(m\). They use the exact parameterization above and examine only the numbers that can possibly work.
The implementation starts with \(k=1\), computes
$$p=3k^2+3k+1,$$
and stops as soon as \(p\) reaches the upper limit. Because the derivation is an equivalence, this loop misses nothing and produces no duplicates: each loop value corresponds to one possible prime and to the unique witness \(n=k^3\).
Each candidate \(p\) is then checked for primality. The C++ and Java implementations handle the even case separately and test only odd divisors up to \(\sqrt{p}\). The Python implementation uses straightforward trial division from small divisors upward until the square-root bound is reached. Since there are only 576 candidates, this simple approach is entirely sufficient. The C++ version also contains a small checkpoint confirming that the count below 100 is 4.
There are exactly 576 candidate values below \(10^6\). With trial division, each primality test costs \(O(\sqrt{p})\), so the total running time is
$$O\!\left(\sum_{k=1}^{576}\sqrt{3k^2+3k+1}\right),$$
which is comfortably tiny for this input size. In simpler terms, the whole job is just a few hundred square-root-bounded divisibility checks. Memory usage is \(O(1)\), because the implementations keep only a handful of integers and a running count.
Gesucht sind Primzahlen \(p \lt 10^6\), für die es eine positive ganze Zahl \(n\) gibt, so dass \(n^3+n^2p\) ein perfekter Kubus ist. Bezeichnet man diesen Kubus mit \(m^3\), dann lautet die Gleichung
$$m^3-n^3=pn^2.$$
Ein blindes Durchprobieren von Paaren \((n,m)\) wäre hier der falsche Ansatz. Die entscheidende Beobachtung ist, dass der Primfaktor \(p\) die Differenz der beiden Kuben extrem stark einschränkt. Sobald diese Struktur freigelegt ist, bleibt nur noch eine kurze explizite Zahlenfolge übrig, auf der man Primtests ausführt.
Die Implementierungen verwenden eine vollständige Charakterisierung aller möglichen Primzahlen \(p\). Es wird also nicht breit gesucht, sondern zuerst bewiesen, welche Werte überhaupt in Frage kommen.
Angenommen,
$$m^3=n^3+pn^2,$$
wobei \(m,n \gt 0\). Weil die rechte Seite größer als \(n^3\) ist, gilt \(m \gt n\).
Setze
$$d=\gcd(m,n),\qquad m=du,\qquad n=dv,\qquad \gcd(u,v)=1.$$
Einsetzen liefert
$$d^3u^3-d^3v^3=pd^2v^2,$$
also nach Kürzen mit \(d^2\)
$$d(u^3-v^3)=pv^2.$$
Aus \(\gcd(u,v)=1\) folgt auch \(\gcd(u^3-v^3,v)=1\), denn ein gemeinsamer Teiler von \(u^3-v^3\) und \(v\) würde auch \(u\) teilen. Damit muss der Faktor \(v^2\) auf der rechten Seite vollständig aus \(d\) stammen. Insbesondere gilt
$$v^2 \mid d.$$
Schreibe deshalb
$$d=v^2c.$$
Dann wird die Gleichung zu
$$c(u^3-v^3)=p.$$
Beide Faktoren links sind positive ganze Zahlen. Da \(p\) prim ist, bleiben nur zwei Fälle: entweder \(c=1\) und \(u^3-v^3=p\), oder \(c=p\) und \(u^3-v^3=1\).
Der zweite Fall ist für positive \(v\) unmöglich. Für \(v \ge 1\) ist der kleinste positive Kubenunterschied bereits
$$(v+1)^3-v^3=3v^2+3v+1 \ge 7.$$
Also muss gelten
$$c=1,\qquad p=u^3-v^3,\qquad d=v^2.$$
Damit ist schon klar: Jede zulässige Primzahl ist tatsächlich eine Kubendifferenz, und der zugehörige Wert von \(n\) ist
$$n=dv=v^3.$$
Nun faktorisiert man die Kubendifferenz:
$$p=u^3-v^3=(u-v)(u^2+uv+v^2).$$
Wegen \(m \gt n\) gilt \(u \gt v \ge 1\). Damit ist der zweite Faktor sicher größer als 1. Da \(p\) prim ist, muss der erste Faktor gleich 1 sein:
$$u-v=1.$$
Setzt man \(v=k\), so ist \(u=k+1\), und damit
$$p=(k+1)^3-k^3=3k^2+3k+1.$$
Umgekehrt erzeugt jeder prime Wert von \(3k^2+3k+1\) eine gültige Lösung, denn mit
$$n=k^3,\qquad m=k^2(k+1)$$
erhält man
$$n^3+n^2p=k^9+k^6(3k^2+3k+1)=k^6(k+1)^3=(k^2(k+1))^3=m^3.$$
Also gilt exakt: Zulässige Primzahlen sind genau die Primwerte der Form
$$p=3k^2+3k+1,\qquad k \ge 1.$$
Diese Zahlen werden oft als kubanische Primzahlen erster Art bezeichnet.
Nimm \(k=2\). Dann ist
$$p=3(2)^2+3(2)+1=19,$$
und die Konstruktion liefert
$$n=2^3=8,\qquad m=2^2\cdot 3=12.$$
Direkt überprüft:
$$8^3+8^2\cdot 19=512+64\cdot 19=1728=12^3.$$
Auch das Beispiel unter 100 folgt sofort aus derselben Formel:
$$k=1,2,3,4 \Longrightarrow p=7,19,37,61,$$
während \(k=5\) den zusammengesetzten Wert \(91\) ergibt. Daher ist die Beispielanzahl 4.
Für die eigentliche Aufgabe brauchen wir nur Werte mit
$$3k^2+3k+1 \lt 10^6.$$
Der größte zulässige Wert ist \(k=576\), denn
$$3\cdot 576^2+3\cdot 576+1=997057 \lt 10^6,$$
während
$$3\cdot 577^2+3\cdot 577+1=1000519 \gt 10^6.$$
Es gibt also nur 576 Kandidaten.
Die C++-, Python- und Java-Implementierungen durchsuchen nicht beliebige Werte von \(n\) oder \(m\). Stattdessen verwenden sie direkt die hergeleitete Parametrisierung und prüfen nur Zahlen, die mathematisch überhaupt möglich sind.
Die Implementierung beginnt bei \(k=1\), berechnet
$$p=3k^2+3k+1,$$
und stoppt, sobald \(p\) die obere Grenze erreicht. Weil die Herleitung eine Äquivalenz ist, wird dabei weder eine Lösung übersehen noch doppelt gezählt: Jeder Schleifenwert entspricht genau einer möglichen Primzahl und genau einem Zeugen \(n=k^3\).
Danach wird jeder Kandidat \(p\) auf Primzahl geprüft. Die C++- und Java-Implementierungen behandeln den geraden Fall separat und testen anschließend nur ungerade Teiler bis \(\sqrt{p}\). Die Python-Implementierung verwendet eine einfache Probedivision mit aufsteigenden Teilern bis zur gleichen Schranke. Da nur 576 Kandidaten vorkommen, ist diese direkte Methode völlig ausreichend. Die C++-Version enthält außerdem einen kleinen Kontrolltest, der für die Schranke 100 die Beispielanzahl 4 bestätigt.
Unterhalb von \(10^6\) gibt es genau 576 Kandidaten. Mit Probedivision kostet jeder Primzahltest \(O(\sqrt{p})\), also insgesamt
$$O\!\left(\sum_{k=1}^{576}\sqrt{3k^2+3k+1}\right).$$
Für diese Eingabegröße ist das sehr klein. Praktisch bedeutet es nur einige hundert Teilbarkeitstests bis zur Quadratwurzel. Der Speicherverbrauch ist \(O(1)\), weil lediglich wenige Ganzzahlen und ein Zähler gehalten werden.
Aranan şey, \(p \lt 10^6\) koşulunu sağlayan ve bazı pozitif \(n\) için \(n^3+n^2p\) ifadesini tam küp yapan asal sayılardır. Bu tam küpü \(m^3\) diye yazarsak denklem
$$m^3-n^3=pn^2$$
haline gelir. Bu problemde asıl mesele, rastgele \((n,m)\) çiftlerini taramak değildir. Belirleyici nokta, \(p\)'nin asal olması nedeniyle iki küpün farkının çok katı bir biçime zorlanmasıdır. O biçim çıkarılınca geriye yalnızca kısa bir açık formül listesi ve asal testi kalır.
Uygulamalar geniş bir arama yapmıyor; önce hangi \(p\) değerlerinin mümkün olduğunu tam olarak ispatlıyor. Bütün çözüm, küp denklemini dikkatle sadeleştirip asallık bilgisini kullanmaya dayanıyor.
Şunu varsayalım:
$$m^3=n^3+pn^2,$$
burada \(m,n \gt 0\). Sağ taraf \(n^3\)'ten büyük olduğuna göre \(m \gt n\) olmalıdır.
Şimdi
$$d=\gcd(m,n),\qquad m=du,\qquad n=dv,\qquad \gcd(u,v)=1$$
yazalım. Yerine koyunca
$$d^3u^3-d^3v^3=pd^2v^2$$
elde edilir; buradan \(d^2\) sadeleştirilirse
$$d(u^3-v^3)=pv^2$$
kalır. \(\gcd(u,v)=1\) olduğundan \(\gcd(u^3-v^3,v)=1\) de olur; çünkü \(u^3-v^3\) ile \(v\)'yi bölen bir sayı aynı zamanda \(u\)'yu da bölerdi. Bu yüzden sağ taraftaki \(v^2\) çarpanı bütünüyle \(d\)'den gelmek zorundadır. Özellikle
$$v^2 \mid d$$
sonucuna ulaşırız.
O halde
$$d=v^2c$$
yazabiliriz. Bu durumda denklem
$$c(u^3-v^3)=p$$
şekline dönüşür. Soldaki iki çarpan da pozitif tamsayıdır. \(p\) asal olduğuna göre yalnızca iki olasılık vardır: ya \(c=1\) ve \(u^3-v^3=p\) olur, ya da \(c=p\) ve \(u^3-v^3=1\).
İkinci durum pozitif \(v\) için imkansızdır. Çünkü \(v \ge 1\) iken en küçük pozitif küp farkı bile
$$(v+1)^3-v^3=3v^2+3v+1 \ge 7$$
olur. Demek ki zorunlu olarak
$$c=1,\qquad p=u^3-v^3,\qquad d=v^2$$
olmalıdır. Böylece her geçerli asalın gerçekten iki küpün farkı olduğu ve karşılık gelen \(n\) değerinin
$$n=dv=v^3$$
şeklinde geldiği ortaya çıkar.
Küp farkını çarpanlarına ayıralım:
$$p=u^3-v^3=(u-v)(u^2+uv+v^2).$$
\(m \gt n\) olduğu için \(u \gt v \ge 1\). Bu durumda ikinci çarpan kesinlikle 1'den büyüktür. \(p\) asal olduğundan birinci çarpan 1 olmak zorundadır:
$$u-v=1.$$
\(v=k\) dersek \(u=k+1\) olur ve
$$p=(k+1)^3-k^3=3k^2+3k+1$$
elde edilir. Ters yönde de aynı derecede güçlü bir sonuç vardır: \(3k^2+3k+1\) asal ise
$$n=k^3,\qquad m=k^2(k+1)$$
seçimi için
$$n^3+n^2p=k^9+k^6(3k^2+3k+1)=k^6(k+1)^3=(k^2(k+1))^3=m^3$$
olur. Yani tam eşdeğerlik şudur: geçerli asallar tam olarak
$$p=3k^2+3k+1,\qquad k \ge 1$$
biçimindeki asal sayılardır.
Bu sayılar literatürde çoğu zaman birinci tür Küba asalları olarak geçer.
\(k=2\) alalım. O zaman
$$p=3(2)^2+3(2)+1=19$$
olur ve yapı şu değerleri verir:
$$n=2^3=8,\qquad m=2^2\cdot 3=12.$$
Doğrudan kontrol edersek
$$8^3+8^2\cdot 19=512+64\cdot 19=1728=12^3$$
elde edilir. \(100\)'ün altındaki örnek de aynı formülden çıkar:
$$k=1,2,3,4 \Longrightarrow p=7,19,37,61,$$
\(k=5\) ise \(91\) verir ve bu sayı bileşiktir. Bu yüzden örnek sayım sonucu 4'tür.
Asıl problem için yalnızca
$$3k^2+3k+1 \lt 10^6$$
koşulunu sağlayan değerler gerekir. En büyük uygun tamsayı \(k=576\)'dır; çünkü
$$3\cdot 576^2+3\cdot 576+1=997057 \lt 10^6,$$
buna karşılık
$$3\cdot 577^2+3\cdot 577+1=1000519 \gt 10^6.$$
Dolayısıyla test edilecek yalnızca 576 aday vardır.
C++, Python ve Java uygulamaları keyfi \(n\) ya da \(m\) değerleri üzerinde dolaşmaz. Türetilen kapalı formülü doğrudan kullanır ve sadece matematiksel olarak mümkün olan adayları üretir.
Uygulama \(k=1\) ile başlar,
$$p=3k^2+3k+1$$
hesabını yapar ve \(p\) üst sınıra ulaştığında durur. Bu parametrizasyon bir eşdeğerlik olduğu için hiçbir çözüm kaçmaz ve hiçbir aday iki kez sayılmaz; her döngü değeri tek bir olası asal ve tek bir \(n=k^3\) tanığına karşılık gelir.
Her aday \(p\) daha sonra asal testinden geçirilir. C++ ve Java sürümleri önce çift olma durumunu ayırır, sonra yalnızca tek bölenleri \(\sqrt{p}\)'ye kadar dener. Python sürümü daha doğrudan bir deneme bölmesi uygular ve küçük bölenlerden başlayarak aynı sınıra kadar ilerler. Toplam aday sayısı yalnızca 576 olduğu için bu basit yöntem fazlasıyla yeterlidir. C++ sürümünde ayrıca \(100\) sınırı için sonucun 4 olduğunu doğrulayan küçük bir kontrol de vardır.
\(10^6\)'nın altında tam olarak 576 aday vardır. Deneme bölmesi kullanıldığında her asal testi \(O(\sqrt{p})\) maliyetindedir; dolayısıyla toplam süre
$$O\!\left(\sum_{k=1}^{576}\sqrt{3k^2+3k+1}\right)$$
olur. Bu giriş boyutu için maliyet çok küçüktür; pratikte yapılan iş, karekök sınırına kadar birkaç yüz bölünebilirlik kontrolünden ibarettir. Bellek kullanımı \(O(1)\)'dir.
Buscamos números primos \(p \lt 10^6\) para los cuales existe un entero positivo \(n\) tal que \(n^3+n^2p\) sea un cubo perfecto. Si ese cubo se escribe como \(m^3\), la ecuación queda
$$m^3-n^3=pn^2.$$
No conviene intentar una búsqueda ciega sobre pares \((n,m)\). La clave es que el hecho de que \(p\) sea primo impone una forma muy rígida sobre la diferencia entre esos dos cubos. Una vez aislada esa forma, el problema se reduce a comprobar primalidad en una sucesión explícita y muy corta.
Las implementaciones no exploran un espacio grande de posibilidades. Primero prueban exactamente qué valores de \(p\) pueden aparecer, y después solo enumeran esos candidatos.
Supongamos que
$$m^3=n^3+pn^2,$$
con \(m,n \gt 0\). Como el lado derecho es mayor que \(n^3\), necesariamente \(m \gt n\).
Sea
$$d=\gcd(m,n),\qquad m=du,\qquad n=dv,\qquad \gcd(u,v)=1.$$
Al sustituir obtenemos
$$d^3u^3-d^3v^3=pd^2v^2,$$
y al dividir por \(d^2\),
$$d(u^3-v^3)=pv^2.$$
Además, \(\gcd(u,v)=1\) implica \(\gcd(u^3-v^3,v)=1\), porque cualquier divisor común de \(u^3-v^3\) y \(v\) también dividiría a \(u\). Por tanto, el factor \(v^2\) del lado derecho debe venir por completo de \(d\). En particular,
$$v^2 \mid d.$$
Escribimos entonces
$$d=v^2c.$$
La ecuación pasa a ser
$$c(u^3-v^3)=p.$$
Ambos factores del lado izquierdo son enteros positivos. Como \(p\) es primo, solo quedan dos casos: o bien \(c=1\) y \(u^3-v^3=p\), o bien \(c=p\) y \(u^3-v^3=1\).
El segundo caso es imposible para \(v\) positivo. Si \(v \ge 1\), la menor diferencia positiva entre cubos ya es
$$(v+1)^3-v^3=3v^2+3v+1 \ge 7.$$
Así que necesariamente
$$c=1,\qquad p=u^3-v^3,\qquad d=v^2.$$
Con esto ya sabemos que todo primo válido es literalmente una diferencia de cubos y que el valor correspondiente de \(n\) es
$$n=dv=v^3.$$
Factorizamos la diferencia de cubos:
$$p=u^3-v^3=(u-v)(u^2+uv+v^2).$$
Como \(m \gt n\), se tiene \(u \gt v \ge 1\). El segundo factor es entonces mayor que 1. Dado que \(p\) es primo, el primer factor debe ser 1:
$$u-v=1.$$
Si escribimos \(v=k\), entonces \(u=k+1\) y obtenemos
$$p=(k+1)^3-k^3=3k^2+3k+1.$$
La recíproca también vale: cuando \(3k^2+3k+1\) es primo, al elegir
$$n=k^3,\qquad m=k^2(k+1)$$
se cumple
$$n^3+n^2p=k^9+k^6(3k^2+3k+1)=k^6(k+1)^3=(k^2(k+1))^3=m^3.$$
Por tanto, la caracterización exacta es la siguiente: los primos válidos son precisamente los números primos de la forma
$$p=3k^2+3k+1,\qquad k \ge 1.$$
Estos números suelen llamarse primos cubanos de primera especie.
Tomemos \(k=2\). Entonces
$$p=3(2)^2+3(2)+1=19,$$
y la construcción produce
$$n=2^3=8,\qquad m=2^2\cdot 3=12.$$
La comprobación directa es
$$8^3+8^2\cdot 19=512+64\cdot 19=1728=12^3.$$
El ejemplo por debajo de 100 sale de la misma fórmula:
$$k=1,2,3,4 \Longrightarrow p=7,19,37,61,$$
mientras que \(k=5\) da \(91\), que no es primo. Por eso la cuenta de ejemplo es 4.
Para el problema real solo necesitamos los valores con
$$3k^2+3k+1 \lt 10^6.$$
El mayor \(k\) posible es \(576\), ya que
$$3\cdot 576^2+3\cdot 576+1=997057 \lt 10^6,$$
mientras que
$$3\cdot 577^2+3\cdot 577+1=1000519 \gt 10^6.$$
Así, solo hay 576 candidatos que probar.
Las implementaciones en C++, Python y Java no recorren valores arbitrarios de \(n\) ni de \(m\). Usan directamente la parametrización deducida y generan solo los candidatos que la demostración permite.
La implementación empieza en \(k=1\), calcula
$$p=3k^2+3k+1,$$
y se detiene cuando \(p\) alcanza el límite. Como la derivación es una equivalencia, no se pierde ninguna solución ni se cuentan duplicados: cada valor del bucle corresponde a un único posible primo y a un único testigo \(n=k^3\).
Cada candidato \(p\) se somete luego a una prueba de primalidad por división de prueba. Las versiones en C++ y Java tratan primero el caso par y después ensayan solo divisores impares hasta \(\sqrt{p}\). La versión en Python usa una división de prueba directa con divisores crecientes hasta el mismo límite. Como el número de candidatos es solo 576, este enfoque sencillo es más que suficiente. La implementación en C++ también incluye una pequeña comprobación que verifica que el conteo por debajo de 100 es 4.
Por debajo de \(10^6\) hay exactamente 576 candidatos. Con división de prueba, cada test de primalidad cuesta \(O(\sqrt{p})\), así que el tiempo total es
$$O\!\left(\sum_{k=1}^{576}\sqrt{3k^2+3k+1}\right).$$
Para esta entrada el coste es muy pequeño: en la práctica solo se hacen unos pocos cientos de comprobaciones de divisibilidad hasta la raíz cuadrada. El espacio usado es \(O(1)\), porque las implementaciones solo mantienen unos pocos enteros y el contador acumulado.
题目要求统计所有满足 \(p \lt 10^6\) 的素数 \(p\)，使得存在某个正整数 \(n\)，令 \(n^3+n^2p\) 成为一个完全立方。把这个立方记成 \(m^3\)，原式就变成
$$m^3-n^3=pn^2.$$
如果直接枚举 \((n,m)\)，几乎不会得到一个有意义的算法。真正关键的是：右边只有一个额外的素数因子 \(p\)，这会把左边两个立方之差的结构压缩得非常严格。只要把这种结构证明出来，问题就不再是“搜索立方”，而是“枚举一个明确二次式并做素性判定”。
三份实现都建立在同一个事实之上：并不是很多素数都可能满足条件，实际上所有可行的 \(p\) 都可以被完全参数化。下面的推导就是这个参数化的来源。
设
$$m^3=n^3+pn^2,$$
其中 \(m,n \gt 0\)。因为右边严格大于 \(n^3\)，所以一定有 \(m \gt n\)。
令
$$d=\gcd(m,n),\qquad m=du,\qquad n=dv,\qquad \gcd(u,v)=1.$$
代回原式得到
$$d^3u^3-d^3v^3=pd^2v^2,$$
两边约去 \(d^2\) 后是
$$d(u^3-v^3)=pv^2.$$
由于 \(\gcd(u,v)=1\)，可知 \(\gcd(u^3-v^3,v)=1\)。理由是：如果某个数同时整除 \(u^3-v^3\) 和 \(v\)，它也会整除 \(u^3\)，从而整除 \(u\)，这与互素矛盾。因此右边的 \(v^2\) 不可能来自 \(u^3-v^3\)，只能完全包含在 \(d\) 里面，于是
$$v^2 \mid d.$$
于是可以写
$$d=v^2c.$$
带回去以后得到
$$c(u^3-v^3)=p.$$
左边两个因子都是正整数，而 \(p\) 是素数，所以只剩两种可能：要么 \(c=1\) 且 \(u^3-v^3=p\)，要么 \(c=p\) 且 \(u^3-v^3=1\)。
第二种情况对正整数 \(v\) 不可能成立。因为当 \(v \ge 1\) 时，最小的正立方差已经是
$$(v+1)^3-v^3=3v^2+3v+1 \ge 7.$$
所以只能有
$$c=1,\qquad p=u^3-v^3,\qquad d=v^2.$$
这一步非常重要：它说明所有合法素数 \(p\) 都是真正的两个立方数之差，而且与之对应的 \(n\) 已经被唯一锁定为
$$n=dv=v^3.$$
继续把立方差分解：
$$p=u^3-v^3=(u-v)(u^2+uv+v^2).$$
由于 \(m \gt n\)，所以 \(u \gt v \ge 1\)。因此第二个因子一定大于 1。既然整个乘积是素数 \(p\)，那第一个因子只能等于 1：
$$u-v=1.$$
令 \(v=k\)，则 \(u=k+1\)，于是
$$p=(k+1)^3-k^3=3k^2+3k+1.$$
反过来也成立：只要 \(3k^2+3k+1\) 本身是素数，取
$$n=k^3,\qquad m=k^2(k+1),$$
就有
$$n^3+n^2p=k^9+k^6(3k^2+3k+1)=k^6(k+1)^3=(k^2(k+1))^3=m^3.$$
因此条件可以精确写成：所有可行的素数 \(p\)，恰好都是下面这个二次式取得的素数值
$$p=3k^2+3k+1,\qquad k \ge 1.$$
这类素数通常被称为第一类 Cuban prime。
取 \(k=2\)。这时
$$p=3(2)^2+3(2)+1=19,$$
相应地
$$n=2^3=8,\qquad m=2^2\cdot 3=12.$$
直接验证：
$$8^3+8^2\cdot 19=512+64\cdot 19=1728=12^3.$$
题目给出的 \(100\) 以下样例也能立刻解释：当
$$k=1,2,3,4$$
时得到
$$p=7,19,37,61,$$
而 \(k=5\) 时得到 \(91\)，已经不是素数，所以样例总数正好是 4。
真正需要检查的只是满足
$$3k^2+3k+1 \lt 10^6$$
的那些 \(k\)。最大的可行值是 \(k=576\)，因为
$$3\cdot 576^2+3\cdot 576+1=997057 \lt 10^6,$$
而
$$3\cdot 577^2+3\cdot 577+1=1000519 \gt 10^6.$$
所以候选值一共只有 576 个。这就是为什么整个程序完全不需要复杂的数论筛法。
C++、Python 和 Java 三个实现都没有去搜索任意的 \(n\) 与 \(m\)。它们直接使用上面的参数化，只枚举那些理论上可能成为答案的 \(p\)。
实现从 \(k=1\) 开始，反复计算
$$p=3k^2+3k+1,$$
一旦 \(p\) 达到上限就停止。因为推导给出的是充要条件，所以这个循环既不会漏解，也不会重复计数；每个 \(k\) 都对应唯一可能的素数，以及唯一的见证值 \(n=k^3\)。
接下来只需要对每个候选 \(p\) 做素性判断。C++ 和 Java 版本先单独处理偶数情况，然后只检查奇数除数直到 \(\sqrt{p}\)。Python 版本采用更直接的试除法，从小除数开始一直试到平方根上界。由于总共只有 576 个候选，这种简单做法已经足够快。C++ 版本还带有一个小检查，用 \(100\) 这个上限确认样例计数确实是 4。
在 \(10^6\) 以下，候选值总数恰好是 576。用试除法做素性检测时，每次检测的代价是 \(O(\sqrt{p})\)，因此总时间可以写成
$$O\!\left(\sum_{k=1}^{576}\sqrt{3k^2+3k+1}\right).$$
对本题规模来说，这个代价非常小，本质上只是几百次“试到平方根”为止的整除检查。空间复杂度是 \(O(1)\)，因为实现里只维护少量整数和累计计数。
Нужно найти все простые числа \(p \lt 10^6\), для которых существует положительное целое \(n\), такое что \(n^3+n^2p\) является точным кубом. Если обозначить этот куб через \(m^3\), то условие переписывается как
$$m^3-n^3=pn^2.$$
Перебирать пары \((n,m)\) напрямую здесь бессмысленно. Главное наблюдение состоит в том, что простота числа \(p\) резко ограничивает вид разности двух кубов. После этого задача сводится не к поиску по огромному пространству, а к проверке простоты у короткой явной последовательности.
Все три реализации опираются на точное описание всех допустимых простых \(p\). Сначала доказывается, какие значения вообще возможны, и только потом выполняется вычисление.
Пусть
$$m^3=n^3+pn^2,$$
где \(m,n \gt 0\). Так как правая часть больше \(n^3\), обязательно \(m \gt n\).
Обозначим
$$d=\gcd(m,n),\qquad m=du,\qquad n=dv,\qquad \gcd(u,v)=1.$$
Подстановка дает
$$d^3u^3-d^3v^3=pd^2v^2,$$
и после деления на \(d^2\) получаем
$$d(u^3-v^3)=pv^2.$$
Из \(\gcd(u,v)=1\) следует и \(\gcd(u^3-v^3,v)=1\): любой общий делитель \(u^3-v^3\) и \(v\) делил бы также \(u\). Значит, множитель \(v^2\) в правой части не может прийти из \(u^3-v^3\) и должен целиком содержаться в \(d\). Следовательно,
$$v^2 \mid d.$$
Запишем
$$d=v^2c.$$
Тогда равенство принимает вид
$$c(u^3-v^3)=p.$$
Оба множителя слева положительны. Поскольку \(p\) простое, возможны только два варианта: либо \(c=1\) и \(u^3-v^3=p\), либо \(c=p\) и \(u^3-v^3=1\).
Второй вариант невозможен при положительном \(v\). Если \(v \ge 1\), то даже минимальная положительная разность кубов равна
$$(v+1)^3-v^3=3v^2+3v+1 \ge 7.$$
Значит, неизбежно
$$c=1,\qquad p=u^3-v^3,\qquad d=v^2.$$
Отсюда уже видно, что каждый допустимый простой \(p\) действительно является разностью двух кубов, а соответствующее значение \(n\) фиксируется формулой
$$n=dv=v^3.$$
Разложим разность кубов на множители:
$$p=u^3-v^3=(u-v)(u^2+uv+v^2).$$
Так как \(m \gt n\), имеем \(u \gt v \ge 1\). Тогда второй множитель строго больше 1. Поскольку все произведение равно простому числу \(p\), первый множитель обязан быть равен 1:
$$u-v=1.$$
Положим \(v=k\), тогда \(u=k+1\), и получаем
$$p=(k+1)^3-k^3=3k^2+3k+1.$$
Обратное утверждение тоже верно: если \(3k^2+3k+1\) простое, то при выборе
$$n=k^3,\qquad m=k^2(k+1)$$
имеем
$$n^3+n^2p=k^9+k^6(3k^2+3k+1)=k^6(k+1)^3=(k^2(k+1))^3=m^3.$$
Итак, точная характеристика такова: все допустимые простые \(p\) - это в точности простые числа вида
$$p=3k^2+3k+1,\qquad k \ge 1.$$
Эти числа часто называют кубинскими простыми первого рода.
Возьмем \(k=2\). Тогда
$$p=3(2)^2+3(2)+1=19,$$
а построение дает
$$n=2^3=8,\qquad m=2^2\cdot 3=12.$$
Прямая проверка:
$$8^3+8^2\cdot 19=512+64\cdot 19=1728=12^3.$$
Пример ниже 100 получается из той же формулы:
$$k=1,2,3,4 \Longrightarrow p=7,19,37,61,$$
а при \(k=5\) имеем \(91\), что уже составное число. Поэтому примерный ответ равен 4.
Для основной задачи нужны только значения, удовлетворяющие
$$3k^2+3k+1 \lt 10^6.$$
Максимальное такое \(k\) равно 576, потому что
$$3\cdot 576^2+3\cdot 576+1=997057 \lt 10^6,$$
тогда как
$$3\cdot 577^2+3\cdot 577+1=1000519 \gt 10^6.$$
Значит, всего нужно проверить лишь 576 кандидатов.
Реализации на C++, Python и Java не перебирают произвольные \(n\) и \(m\). Они сразу используют полученную параметризацию и рассматривают только те \(p\), которые вообще могут подойти по доказанной формуле.
Алгоритм стартует с \(k=1\), вычисляет
$$p=3k^2+3k+1,$$
и завершает цикл, как только \(p\) достигает верхней границы. Так как вывод выше является эквивалентностью, здесь нет ни пропусков, ни повторов: каждому значению \(k\) соответствует единственный возможный простой и единственный свидетель \(n=k^3\).
Дальше каждый кандидат \(p\) проверяется на простоту методом пробного деления. В версиях на C++ и Java сначала отдельно обрабатывается четный случай, а затем проверяются только нечетные делители до \(\sqrt{p}\). В Python используется прямое пробное деление с возрастающими делителями до той же границы. Поскольку кандидатов всего 576, такого простого метода более чем достаточно. В реализации на C++ есть также маленькая проверка, подтверждающая, что для границы 100 ответ равен 4.
Ниже \(10^6\) имеется ровно 576 кандидатов. При пробном делении одна проверка простоты стоит \(O(\sqrt{p})\), поэтому суммарное время равно
$$O\!\left(\sum_{k=1}^{576}\sqrt{3k^2+3k+1}\right).$$
Для данного входа это очень мало: фактически выполняются лишь несколько сотен проверок делимости до квадратного корня. Память равна \(O(1)\), потому что хранятся только несколько целых чисел и текущий счетчик.
نريد إيجاد جميع الأعداد الأولية \(p \lt 10^6\) التي يوجد من أجلها عدد صحيح موجب \(n\) بحيث يكون التعبير \(n^3+n^2p\) مكعبًا كاملًا. إذا رمزنا لذلك المكعب بالرمز \(m^3\)، تصبح المعادلة
$$m^3-n^3=pn^2.$$
البحث المباشر في الأزواج \((n,m)\) ليس هو الفكرة الصحيحة هنا. جوهر المسألة أن كون \(p\) عددًا أوليًا يفرض بنية شديدة التقييد على الفرق بين المكعبين. وما إن نثبت تلك البنية حتى تتحول المسألة إلى تعداد متتالية صريحة قصيرة ثم اختبار أوليتها.
التنفيذات الثلاثة تعتمد على توصيف دقيق لكل القيم الممكنة لـ \(p\). فهي لا تبدأ من تعداد واسع، بل من برهان يحدد تمامًا أي الأعداد يمكن أن تظهر.
لنفرض أن
$$m^3=n^3+pn^2,$$
حيث \(m,n \gt 0\). بما أن الطرف الأيمن أكبر من \(n^3\)، فلا بد أن يكون \(m \gt n\).
لنكتب
$$d=\gcd(m,n),\qquad m=du,\qquad n=dv,\qquad \gcd(u,v)=1.$$
بالتعويض نحصل على
$$d^3u^3-d^3v^3=pd^2v^2,$$
وبعد القسمة على \(d^2\) نحصل على
$$d(u^3-v^3)=pv^2.$$
ومن \(\gcd(u,v)=1\) ينتج أيضًا أن \(\gcd(u^3-v^3,v)=1\)، لأن أي قاسم مشترك لـ \(u^3-v^3\) و \(v\) سيقسم \(u\) كذلك. إذًا العامل \(v^2\) الموجود في الطرف الأيمن لا يمكن أن يأتي من \(u^3-v^3\)، بل يجب أن يكون محتوى بالكامل في \(d\). أي إن
$$v^2 \mid d.$$
لذلك نكتب
$$d=v^2c.$$
فتصبح المعادلة
$$c(u^3-v^3)=p.$$
العاملان في الطرف الأيسر عددان صحيحان موجبان. وبما أن \(p\) أولي، فلا يبقى إلا احتمالان: إما أن \(c=1\) و\(u^3-v^3=p\)، وإما أن \(c=p\) و\(u^3-v^3=1\).
الاحتمال الثاني مستحيل عندما يكون \(v\) موجبًا. فإذا كان \(v \ge 1\)، فإن أصغر فرق موجب بين مكعبين هو
$$(v+1)^3-v^3=3v^2+3v+1 \ge 7.$$
إذن لا بد من أن
$$c=1,\qquad p=u^3-v^3,\qquad d=v^2.$$
وهنا تظهر أول حقيقة حاسمة: كل عدد أولي صالح \(p\) هو بالفعل فرق بين مكعبين، والقيمة المناظرة لـ \(n\) تصبح محددة بالصورة
$$n=dv=v^3.$$
نحلل فرق المكعبين:
$$p=u^3-v^3=(u-v)(u^2+uv+v^2).$$
وبما أن \(m \gt n\)، فإن \(u \gt v \ge 1\). لذا يكون العامل الثاني أكبر من 1 حتمًا. ولأن حاصل الضرب عدد أولي، فلا بد أن يكون العامل الأول مساويًا لـ 1:
$$u-v=1.$$
إذا وضعنا \(v=k\)، صار \(u=k+1\)، ومن ثم
$$p=(k+1)^3-k^3=3k^2+3k+1.$$
والعكس صحيح أيضًا: متى كان \(3k^2+3k+1\) عددًا أوليًا، فإن اختيار
$$n=k^3,\qquad m=k^2(k+1)$$
يعطي
$$n^3+n^2p=k^9+k^6(3k^2+3k+1)=k^6(k+1)^3=(k^2(k+1))^3=m^3.$$
إذن الوصف الدقيق هو أن جميع القيم الأولية الصالحة لـ \(p\) تأتي بالضبط من الصيغة
$$p=3k^2+3k+1,\qquad k \ge 1.$$
وتعرف هذه الأعداد غالبًا باسم الأعداد الأولية الكوبية من النوع الأول.
خذ \(k=2\). عندئذ
$$p=3(2)^2+3(2)+1=19,$$
ويعطي البناء
$$n=2^3=8,\qquad m=2^2\cdot 3=12.$$
والتحقق المباشر هو
$$8^3+8^2\cdot 19=512+64\cdot 19=1728=12^3.$$
وكذلك المثال تحت 100 يخرج فورًا من الصيغة نفسها:
$$k=1,2,3,4 \Longrightarrow p=7,19,37,61,$$
أما \(k=5\) فيعطي \(91\) وهو عدد غير أولي، ولهذا يكون عدد الحالات في المثال هو 4.
في المسألة الأصلية لا نحتاج إلا القيم التي تحقق
$$3k^2+3k+1 \lt 10^6.$$
أكبر قيمة ممكنة هي \(k=576\)، لأن
$$3\cdot 576^2+3\cdot 576+1=997057 \lt 10^6,$$
بينما
$$3\cdot 577^2+3\cdot 577+1=1000519 \gt 10^6.$$
وبذلك لا يوجد إلا 576 مرشحًا لاختبارهم.
تنفيذات C++ وPython وJava لا تبحث في قيم عشوائية لـ \(n\) أو \(m\). بل تستخدم الصيغة المستنتجة مباشرة وتولد فقط القيم التي يمكن أن تكون صحيحة من الناحية الرياضية.
تبدأ الشيفرة من \(k=1\)، وتحسب مرارًا
$$p=3k^2+3k+1,$$
ثم تتوقف حالما يصل \(p\) إلى الحد الأعلى. ولأن البرهان يعطي تكافؤًا كاملًا، فلا توجد حلول مفقودة ولا حالات مكررة؛ كل قيمة لـ \(k\) تقابل مرشحًا واحدًا فقط، وتقابل معها الشاهد الوحيد \(n=k^3\).
بعد ذلك يختبر كل مرشح \(p\) لاختبار الأولية. نسختا C++ وJava تعالجان حالة الزوجية أولًا، ثم تفحصان القواسم الفردية فقط حتى \(\sqrt{p}\). أما نسخة Python فتستخدم قسمة تجريبية مباشرة بقواسم متزايدة حتى الحد نفسه. وبما أن عدد المرشحين لا يتجاوز 576، فهذه الطريقة البسيطة كافية تمامًا. كما أن نسخة C++ تحتوي على تحقق صغير يؤكد أن العدد تحت 100 يساوي 4.
عدد المرشحين تحت \(10^6\) هو 576 بالضبط. ومع القسمة التجريبية، تكون كلفة اختبار أولية واحد \(O(\sqrt{p})\)، ومن ثم يكون الزمن الكلي
$$O\!\left(\sum_{k=1}^{576}\sqrt{3k^2+3k+1}\right).$$
وهذا صغير جدًا بالنسبة إلى حجم المسألة؛ فعمليًا لا يجري البرنامج إلا بضع مئات من اختبارات القسمة حتى الجذر التربيعي. أما الذاكرة فهي \(O(1)\) لأن التنفيذ يحتفظ بعدد قليل من القيم الصحيحة وعداد واحد فقط.