The task is to determine the largest prime factor of \(600851475143\). The sample value \(13195\) is useful because it already shows the shape of the question:
$$13195 = 5 \cdot 7 \cdot 13 \cdot 29,$$
so its largest prime factor is \(29\). The implementation solves the same problem for the much larger target integer by repeatedly removing prime divisors from a shrinking remainder.
The solution is a careful form of trial division. Its correctness does not come from blindly testing divisors; it comes from an invariant about what the remaining number can still contain after smaller factors have already been removed.
By the fundamental theorem of arithmetic, every integer \(N \ge 2\) can be written uniquely as
$$N = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}, \qquad 2 \le p_1 \lt p_2 \lt \cdots \lt p_r,$$
with each \(a_i \ge 1\). The answer to the problem is simply \(p_r\), the largest prime appearing in that factorization.
The difficulty is that we do not know the factorization in advance. The algorithm reconstructs only the part it needs: it keeps removing confirmed prime factors until the remaining value is either \(1\) or itself prime.
Suppose we have already finished processing every possible divisor below some odd candidate \(d\). Let the current remainder be \(n\). Then the invariant is:
$$N = \left(\prod_{p \lt d} p^{e_p}\right) n,$$
where the product contains exactly the prime powers that have already been removed, and \(n\) has no prime factor smaller than \(d\).
This immediately explains two key implementation decisions.
First, the factor \(2\) is handled separately at the beginning. After repeatedly dividing by \(2\), the remainder becomes odd, so the rest of the search only needs odd candidates.
Second, when an odd candidate \(d\) divides the current remainder, \(d\) must actually be prime. If it were composite, it would have a prime divisor \(q \lt d\). That same \(q\) would also divide the current remainder, contradicting the invariant that no smaller prime factors remain. So even though the loop steps through all odd integers, every successful odd divisor is automatically a prime factor.
The algorithm also divides that factor out completely. If \(d^k \mid n\), then after the inner loop finishes we have removed all copies of \(d\), which restores the same invariant for the next candidate.
The classical bound is: if a positive integer \(m\) is composite, then it has a prime factor at most \(\sqrt{m}\). Indeed, if \(m = ab\) with \(1 \lt a \le b\), then \(a^2 \le ab = m\), hence \(a \le \sqrt{m}\), and some prime dividing \(a\) also divides \(m\).
Apply that statement not to the original input, but to the current remainder. If the current remainder \(n\) were composite, then some prime factor would be at most \(\sqrt{n}\). Therefore, once the current candidate exceeds \(\sqrt{n}\), there are only two possibilities left:
This is why the stopping condition tightens as the remainder shrinks. The search bound is not fixed at \(\sqrt{N}\); it gets smaller every time a factor is divided out. The C++ implementation expresses this test in an overflow-safe division form, while the Python and Java implementations use the equivalent square comparison.
Start with \(n = 13195\). The number is odd, so there is no factor \(2\) to remove.
Testing odd candidates in increasing order, the first successful divisor is \(5\):
$$13195 \div 5 = 2639.$$
The remainder \(2639\) is not divisible by \(5\) again, so the search continues. The next successful divisor is \(7\):
$$2639 \div 7 = 377.$$
Then \(13\) divides:
$$377 \div 13 = 29.$$
Now the remainder is \(29\). At that point the next candidate would already exceed \(\sqrt{29}\), so the loop stops. Because a composite remainder would need a factor at most \(\sqrt{29}\), the remaining \(29\) must be prime. Hence the largest prime factor is \(29\).
The target number behaves exactly the same way. Repeated trial division removes the prime factors in increasing order:
$$600851475143 = 71 \cdot 839 \cdot 1471 \cdot 6857.$$
After dividing out \(71\), then \(839\), then \(1471\), the remaining value is \(6857\). No smaller factor remains, and once the search bound passes \(\sqrt{6857}\), that remainder is forced to be prime. Therefore the final answer is \(6857\).
The C++, Python, and Java implementations all follow the same mathematical plan: maintain a mutable remainder, keep track of the largest confirmed prime factor seen so far, and shrink the remainder whenever a factor is found.
The first phase repeatedly divides by \(2\) while the input is even. This isolates the only even prime immediately. If at least one such division happens, then the best answer found so far is at least \(2\), and the remainder becomes odd.
After that, the implementation checks odd candidates \(3, 5, 7, \dots\) in ascending order. Whenever the current candidate divides the remainder, the implementation divides repeatedly until that factor disappears completely, and then updates the current best answer. This corresponds exactly to removing the full prime power \(p^a\) from the factorization before moving on.
Because the remainder keeps shrinking, the stopping condition is evaluated against the current remainder rather than against the original input. That is the reason the algorithm is usually much faster than a naive fixed-bound scan would suggest.
When the odd-candidate loop ends, the implementation performs one final check. If the remainder is still greater than \(1\), it must be prime by the square-root argument above, so it becomes the answer. Each implementation also verifies the sample case \(13195 \mapsto 29\) before printing the result for the main input.
In the worst case, trial division checks odd numbers up to about \(\sqrt{N}\), so the running time is \(O(\sqrt{N})\). The algorithm uses only a constant amount of extra memory, so the space complexity is \(O(1)\).
That worst case is already modest for this specific input: \(\sqrt{600851475143}\) is about \(7.75 \times 10^5\), and only odd candidates are tested after the factor \(2\) is handled. In practice the dynamic bound shrinks whenever a factor is removed, so the real running time is smaller than the pessimistic bound suggests.
Gesucht ist der größte Primfaktor von \(600851475143\). Das kleinere Beispiel \(13195\) zeigt bereits exakt, was gemeint ist:
$$13195 = 5 \cdot 7 \cdot 13 \cdot 29,$$
also ist dort der größte Primfaktor \(29\). Die Implementierungen lösen dieselbe Aufgabe für die deutlich größere Zielzahl, indem sie bestätigte Primfaktoren nacheinander aus einem immer kleiner werdenden Rest herausdividieren.
Die Methode ist eine saubere Form der Trial Division. Entscheidend ist nicht bloß das Testen vieler Teiler, sondern ein Invarianzargument darüber, welche Primfaktoren im aktuellen Rest überhaupt noch enthalten sein können.
Nach dem Fundamentalsatz der Arithmetik besitzt jede ganze Zahl \(N \ge 2\) eine eindeutige Darstellung
$$N = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}, \qquad 2 \le p_1 \lt p_2 \lt \cdots \lt p_r,$$
wobei alle \(a_i \ge 1\) sind. Die Antwort des Problems ist \(p_r\), also die größte Primzahl in dieser Zerlegung.
Die vollständige Zerlegung muss jedoch nicht explizit im Voraus bekannt sein. Es genügt, kleine Primfaktoren systematisch zu entfernen, bis der verbleibende Rest entweder \(1\) oder selbst prim ist.
Angenommen, alle möglichen Teiler kleiner als ein aktueller ungerader Kandidat \(d\) sind bereits abgearbeitet. Sei \(n\) der momentane Rest. Dann gilt die Invariante
$$N = \left(\prod_{p \lt d} p^{e_p}\right) n,$$
wobei das Produkt genau die bereits entfernten Primzahlpotenzen enthält und \(n\) keinen Primfaktor kleiner als \(d\) mehr besitzt.
Daraus folgen zwei zentrale Punkte des Verfahrens.
Erstens wird der Faktor \(2\) am Anfang separat behandelt. Nach wiederholtem Teilen durch \(2\) ist der Rest ungerade, also müssen später nur noch ungerade Kandidaten geprüft werden.
Zweitens: Wenn ein ungerader Kandidat \(d\) den aktuellen Rest teilt, dann ist \(d\) automatisch prim. Wäre \(d\) zusammengesetzt, hätte \(d\) einen Primteiler \(q \lt d\). Dann würde auch \(q\) den aktuellen Rest teilen, im Widerspruch zur Invariante. Deshalb darf die Implementierung alle ungeraden Zahlen testen; ein erfolgreicher Treffer kann nur bei einer Primzahl auftreten.
Außerdem wird ein gefundener Teiler vollständig herausdividiert. Wenn also \(d^k \mid n\) gilt, dann entfernt die innere Schleife alle \(k\) Kopien von \(d\), bevor der nächste Kandidat betrachtet wird.
Es gilt der klassische Satz: Ist eine positive Zahl \(m\) zusammengesetzt, dann besitzt sie einen Primfaktor \(\le \sqrt{m}\). Denn aus \(m = ab\) mit \(1 \lt a \le b\) folgt \(a^2 \le ab = m\), also \(a \le \sqrt{m}\), und ein Primteiler von \(a\) ist auch ein Primteiler von \(m\).
Entscheidend ist, diesen Satz auf den aktuellen Rest anzuwenden und nicht auf den ursprünglichen Input. Wenn der momentane Rest \(n\) noch zusammengesetzt wäre, müsste er also einen Primfaktor \(\le \sqrt{n}\) haben. Sobald der aktuelle Kandidat größer als \(\sqrt{n}\) geworden ist, bleiben deshalb nur zwei Möglichkeiten:
Die obere Schranke schrumpft daher dynamisch mit dem Rest mit. Die C++-Implementierung schreibt diesen Test über eine divisionsbasierte Vergleichsform, um Überläufe zu vermeiden; die Python- und Java-Implementierungen verwenden die mathematisch äquivalente Quadratbedingung.
Wir starten mit \(n = 13195\). Die Zahl ist ungerade, also entfällt der Faktor \(2\).
Beim Durchlauf über die ungeraden Kandidaten ist \(5\) der erste erfolgreiche Teiler:
$$13195 \div 5 = 2639.$$
Der Rest \(2639\) ist nicht noch einmal durch \(5\) teilbar, also geht die Suche weiter. Der nächste Treffer ist \(7\):
$$2639 \div 7 = 377.$$
Danach teilt \(13\):
$$377 \div 13 = 29.$$
Nun bleibt der Rest \(29\). Der nächste Kandidat läge bereits oberhalb von \(\sqrt{29}\). Da ein zusammengesetzter Rest einen kleineren Primteiler haben müsste, ist \(29\) selbst prim. Also ist der größte Primfaktor gleich \(29\).
Für die Zielzahl funktioniert dieselbe Logik. Die Trial Division entfernt die Primfaktoren in aufsteigender Reihenfolge:
$$600851475143 = 71 \cdot 839 \cdot 1471 \cdot 6857.$$
Nach dem Herausdividieren von \(71\), dann \(839\) und \(1471\), bleibt \(6857\) übrig. Sobald die Suchgrenze über \(\sqrt{6857}\) hinausgeht, ist klar, dass dieser Rest prim sein muss. Damit lautet die gesuchte Antwort \(6857\).
Die C++-, Python- und Java-Implementierungen setzen alle denselben mathematischen Plan um: Sie halten einen veränderlichen Rest, merken sich den größten bisher bestätigten Primfaktor und verkleinern den Rest sofort, sobald ein Faktor gefunden wurde.
In der ersten Phase wird so lange durch \(2\) geteilt, wie die Zahl gerade ist. Dadurch wird die einzige gerade Primzahl sofort vollständig entfernt. Wenn mindestens eine solche Division stattfindet, ist der bisher beste Kandidat mindestens \(2\), und der Rest wird ungerade.
Danach prüft die Implementierung die ungeraden Kandidaten \(3, 5, 7, \dots\) in aufsteigender Reihenfolge. Immer wenn der aktuelle Kandidat den Rest teilt, wird so lange weitergeteilt, bis dieser Faktor vollständig verschwunden ist; danach wird der größte gefundene Primfaktor aktualisiert. Genau so wird die volle Primzahlpotenz \(p^a\) entfernt, bevor die Suche weitergeht.
Weil der Rest währenddessen schrumpft, bezieht sich auch die Abbruchbedingung auf den aktuellen Rest und nicht auf die ursprüngliche Eingabe. Das erklärt, warum das Verfahren in der Praxis oft schneller ist als eine starre Suche bis \(\sqrt{N}\).
Nach dem Ende der Schleife über die ungeraden Kandidaten folgt noch ein letzter Test. Falls der Rest dann noch größer als \(1\) ist, muss er nach dem Quadratwurzelargument prim sein und ist somit die gesuchte Antwort. Zusätzlich prüfen alle Implementierungen das Beispiel \(13195 \mapsto 29\), bevor der Wert für die eigentliche Aufgabe ausgegeben wird.
Im Worst Case prüft Trial Division ungerade Zahlen bis ungefähr \(\sqrt{N}\); die Laufzeit ist also \(O(\sqrt{N})\). Der zusätzliche Speicherbedarf bleibt konstant, also \(O(1)\).
Für diese konkrete Aufgabe ist selbst der pessimistische Fall klein genug: \(\sqrt{600851475143}\) liegt bei ungefähr \(7{,}75 \times 10^5\), und nach der Behandlung des Faktors \(2\) werden nur noch ungerade Kandidaten betrachtet. In der Praxis wird die effektive Schranke durch das Schrumpfen des Restes zusätzlich kleiner.
İstenen şey \(600851475143\) sayısının en büyük asal çarpanını bulmaktır. Daha küçük olan \(13195\) örneği sorunun tam olarak ne istediğini açıkça gösterir:
$$13195 = 5 \cdot 7 \cdot 13 \cdot 29,$$
dolayısıyla bu örnekte en büyük asal çarpan \(29\)'dur. Uygulamalar aynı fikri çok daha büyük hedef sayı üzerinde uygular ve asal çarpanlar bulundukça kalan sayıyı küçültür.
Kullanılan yöntem düzenli bir deneme bölmesidir. Doğruluk, çok sayıda bölen denemekten değil, küçük çarpanlar temizlendikten sonra elde kalan sayının hangi asal çarpanları hâlâ içerebileceğini anlatan bir değişmezden gelir.
Aritmetiğin temel teoremine göre her \(N \ge 2\) tam sayısı tek biçimde
$$N = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}, \qquad 2 \le p_1 \lt p_2 \lt \cdots \lt p_r,$$
şeklinde yazılır; burada tüm \(a_i \ge 1\)'dir. Sorunun cevabı bu çarpanlaşmadaki en büyük asal olan \(p_r\)'dir.
Ancak çözümün amacı tam çarpanlaşmayı baştan kurmak değildir. Küçük asal çarpanları sırayla temizlemek ve sonunda geriye \(1\) ya da asal bir kalan bırakmak yeterlidir.
Diyelim ki belirli bir tek aday \(d\)'den küçük tüm olası bölenler işlendi ve elimizde güncel kalan \(n\) var. O zaman şu değişmez geçerlidir:
$$N = \left(\prod_{p \lt d} p^{e_p}\right) n,$$
buradaki çarpım daha önce tamamen çıkarılmış asal kuvvetleri içerir ve \(n\)'nin \(d\)'den küçük hiçbir asal böleni kalmamıştır.
Bu gözlem algoritmanın iki önemli özelliğini açıklar.
Birincisi, \(2\) çarpanı en başta ayrı ele alınır. \(2\) tamamen çıkarıldıktan sonra kalan sayı tek olur; böylece devamında yalnızca tek adayları sınamak yeterlidir.
İkincisi, tek bir aday \(d\) güncel kalanı bölüyorsa, bu \(d\) aslında zorunlu olarak asaldır. Çünkü \(d\) bileşik olsaydı \(d\)'nin \(q \lt d\) olacak bir asal böleni bulunurdu. O zaman aynı \(q\) güncel kalanı da bölerdi; bu ise değişmezle çelişir. Demek ki döngü bütün tek sayıları gezse bile, gerçekten bölme yapan her tek aday otomatik olarak asal çarpandır.
Bulunan bölenin tamamen çıkarılması da zorunludur. Eğer \(d^k \mid n\) ise, iç döngü \(d\)'nin tüm kopyalarını temizler ve böylece bir sonraki aday için aynı değişmez yeniden kurulmuş olur.
Klasik sonuç şudur: Pozitif bir \(m\) sayısı bileşikse, \(\sqrt{m}\)'den büyük olmayan bir asal böleni vardır. Gerçekten \(m = ab\) ve \(1 \lt a \le b\) ise \(a^2 \le ab = m\), yani \(a \le \sqrt{m}\). \(a\)'nın bir asal böleni de \(m\)'yi böler.
Buradaki kritik nokta, bu sonucu başlangıç girdisine değil güncel kalana uygulamaktır. Eğer eldeki kalan \(n\) hâlâ bileşik olsaydı, \(\sqrt{n}\)'den büyük olmayan bir asal böleni bulunmak zorundaydı. O hâlde aday \(\sqrt{n}\)'yi geçtiği anda yalnızca iki durum kalır:
Böylece üst sınır sabit kalmaz; kalan küçüldükçe sınır da küçülür. C++ uygulaması bu testi taşma güvenliği için bölme tabanlı eşdeğer bir karşılaştırma ile yazar; Python ve Java uygulamaları ise aynı matematiksel koşulu kare karşılaştırmasıyla ifade eder.
\(n = 13195\) ile başlayalım. Sayı tek olduğu için \(2\) çarpanı yoktur.
Tek adaylar artan sırada denenirken ilk başarılı bölen \(5\) olur:
$$13195 \div 5 = 2639.$$
\(2639\) artık tekrar \(5\)'e bölünmez, bu yüzden arama sürer. Bir sonraki başarılı aday \(7\)'dir:
$$2639 \div 7 = 377.$$
Ardından \(13\) böler:
$$377 \div 13 = 29.$$
Artık kalan \(29\)'dur. Bir sonraki aday \(\sqrt{29}\)'u aşacağı için döngü biter. Bileşik bir kalan daha küçük bir asal bölen içermek zorunda olduğundan, elde kalan \(29\) asaldır. Bu nedenle en büyük asal çarpan \(29\)'dur.
Hedef sayı için de süreç tamamen aynıdır. Deneme bölmesi asal çarpanları artan sırada ayıklar:
$$600851475143 = 71 \cdot 839 \cdot 1471 \cdot 6857.$$
\(71\), sonra \(839\), sonra \(1471\) çıkarıldıktan sonra geriye \(6857\) kalır. Arama sınırı \(\sqrt{6857}\)'yi aştığında bu kalanın asal olması zorunludur. Dolayısıyla son cevap \(6857\)'dir.
C++, Python ve Java uygulamalarının hepsi aynı matematiksel planı uygular: değiştirilebilir bir kalan tutulur, şimdiye kadar doğrulanmış en büyük asal çarpan saklanır ve yeni bir bölen bulunduğunda kalan hemen küçültülür.
İlk fazda sayı çift olduğu sürece \(2\)'ye bölünür. Böylece tek çift asal olan \(2\) tamamen temizlenmiş olur. En az bir bölme gerçekleşirse, o ana kadarki en iyi aday en az \(2\)'dir ve kalan artık tektir.
Daha sonra uygulama \(3, 5, 7, \dots\) biçimindeki tek adayları artan sırada dener. Geçerli aday kalanı bölüyorsa, bu bölen tamamen kaybolana kadar tekrar tekrar bölme yapılır ve ardından bulunan en büyük asal çarpan güncellenir. Bu, asal çarpanlaşmadaki \(p^a\) kuvvetinin tamamını çıkarıp sonra bir sonraki adaya geçmeye karşılık gelir.
Kalan sayı küçüldüğü için durma koşulu da özgün girişe değil güncel kalana göre değerlendirilir. Yöntemin pratikte beklenenden hızlı olmasının temel nedeni budur.
Tek aday döngüsü bittiğinde bir son kontrol yapılır. Kalan hâlâ \(1\)'den büyükse, yukarıdaki karekök argümanı gereği asal olmak zorundadır ve cevap olur. Uygulamaların her biri ana girdi için sonucu üretmeden önce \(13195 \mapsto 29\) örneğini de doğrular.
En kötü durumda deneme bölmesi yaklaşık \(\sqrt{N}\)'e kadar tek sayıları kontrol eder; dolayısıyla zaman karmaşıklığı \(O(\sqrt{N})\)'dir. Ek bellek kullanımı sabittir, yani \(O(1)\).
Bu problem için kötümser üst sınır bile küçüktür: \(\sqrt{600851475143}\) yaklaşık \(7.75 \times 10^5\)'tir ve \(2\) ayrıldıktan sonra yalnızca tek adaylar denenir. Pratikte bir çarpan bulunduğunda kalan küçüldüğü için etkin üst sınır daha da düşer.
La tarea consiste en hallar el mayor factor primo de \(600851475143\). El ejemplo pequeño \(13195\) ya muestra exactamente qué se está buscando:
$$13195 = 5 \cdot 7 \cdot 13 \cdot 29,$$
de modo que su mayor factor primo es \(29\). Las implementaciones resuelven la misma idea para un entero mucho mayor, eliminando factores primos confirmados de un resto que se va encogiendo.
El método es una forma disciplinada de división por tentativa. Su corrección no depende de probar divisores a ciegas, sino de un invariante que describe qué factores primos todavía puede contener el resto una vez que los menores ya han sido eliminados.
Por el teorema fundamental de la aritmética, todo entero \(N \ge 2\) admite una descomposición única
$$N = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}, \qquad 2 \le p_1 \lt p_2 \lt \cdots \lt p_r,$$
con \(a_i \ge 1\) para todo \(i\). La respuesta del problema es \(p_r\), el mayor primo que aparece en esa factorización.
No hace falta conocer toda la factorización desde el principio. Basta con ir retirando los factores pequeños hasta que el valor restante sea \(1\) o sea él mismo un primo.
Supongamos que ya se han procesado todos los posibles divisores menores que un candidato impar actual \(d\). Sea \(n\) el resto actual. Entonces se cumple el invariante
$$N = \left(\prod_{p \lt d} p^{e_p}\right) n,$$
donde el producto contiene exactamente las potencias primas ya retiradas y \(n\) no tiene ningún factor primo menor que \(d\).
De aquí salen dos decisiones fundamentales del algoritmo.
Primero, el factor \(2\) se trata aparte al comienzo. Después de dividir repetidamente por \(2\), el resto queda impar, así que el resto de la búsqueda solo necesita candidatos impares.
Segundo, si un candidato impar \(d\) divide al resto actual, entonces \(d\) tiene que ser primo. Si fuera compuesto, tendría un factor primo \(q \lt d\). Ese mismo \(q\) dividiría también al resto actual, contradiciendo el invariante. Por eso el bucle puede recorrer todos los impares: cualquier candidato impar que llegue a dividir de verdad al resto queda automáticamente certificado como primo.
Además, un factor encontrado se elimina por completo. Si \(d^k \mid n\), el bucle interior divide repetidamente hasta borrar las \(k\) copias de \(d\), restaurando el mismo invariante para el siguiente candidato.
El hecho clásico es el siguiente: si un entero positivo \(m\) es compuesto, entonces tiene un factor primo menor o igual que \(\sqrt{m}\). En efecto, si \(m = ab\) con \(1 \lt a \le b\), se tiene \(a^2 \le ab = m\), luego \(a \le \sqrt{m}\), y cualquier primo que divida a \(a\) también divide a \(m\).
La idea correcta es aplicar este resultado no al número inicial, sino al resto actual. Si el resto \(n\) siguiera siendo compuesto, tendría un factor primo \(\le \sqrt{n}\). Por tanto, cuando el candidato actual supera \(\sqrt{n}\), solo pueden ocurrir dos cosas:
Por eso la cota superior se encoge a medida que el resto se hace más pequeño. La implementación en C++ expresa esta prueba con una comparación basada en división para evitar desbordamientos; las versiones en Python y Java usan la condición equivalente con cuadrados.
Comenzamos con \(n = 13195\). Como es impar, no hay factor \(2\) que retirar.
Al recorrer los candidatos impares en orden creciente, el primero que divide es \(5\):
$$13195 \div 5 = 2639.$$
El resto \(2639\) ya no es divisible por \(5\), así que la búsqueda continúa. El siguiente acierto es \(7\):
$$2639 \div 7 = 377.$$
Después divide \(13\):
$$377 \div 13 = 29.$$
En ese punto el resto es \(29\). El siguiente candidato ya quedaría por encima de \(\sqrt{29}\), y un resto compuesto necesitaría un factor primo más pequeño. Así que \(29\) es primo y, en consecuencia, el mayor factor primo es \(29\).
La misma lógica resuelve el caso principal. La división por tentativa va extrayendo los factores primos en orden creciente:
$$600851475143 = 71 \cdot 839 \cdot 1471 \cdot 6857.$$
Después de retirar \(71\), luego \(839\) y después \(1471\), el resto que queda es \(6857\). Cuando la cota de búsqueda supera \(\sqrt{6857}\), ese resto ya no puede ser compuesto. Por lo tanto, la respuesta final es \(6857\).
Las implementaciones en C++, Python y Java siguen el mismo plan matemático: mantienen un resto mutable, guardan el mayor factor primo confirmado hasta el momento y reducen el resto cada vez que aparece un divisor real.
La primera fase divide por \(2\) mientras el número sea par. Así se elimina por completo el único primo par. Si ocurre al menos una división, entonces el mejor candidato conocido es al menos \(2\), y el resto pasa a ser impar.
Después, la implementación prueba los candidatos impares \(3, 5, 7, \dots\) en orden creciente. Cuando el candidato actual divide al resto, se divide repetidamente hasta que ese factor desaparece por completo, y luego se actualiza el mayor factor primo encontrado. Esto equivale a eliminar la potencia completa \(p^a\) antes de avanzar al siguiente candidato.
Como el resto se va reduciendo, la condición de parada se evalúa con respecto al resto actual y no con respecto al valor original. Esa es la razón por la que el algoritmo suele ser bastante más rápido en la práctica que una exploración ingenua con cota fija.
Cuando termina el bucle de candidatos impares, queda una comprobación final. Si el resto todavía es mayor que \(1\), debe ser primo por el argumento de la raíz cuadrada, y entonces se convierte en la respuesta. Además, cada implementación verifica el ejemplo \(13195 \mapsto 29\) antes de producir el resultado del caso principal.
En el peor caso, la división por tentativa examina impares hasta aproximadamente \(\sqrt{N}\), de modo que el tiempo es \(O(\sqrt{N})\). El uso de memoria adicional es constante, es decir, \(O(1)\).
Para esta entrada concreta, incluso la cota pesimista es pequeña: \(\sqrt{600851475143}\) es aproximadamente \(7.75 \times 10^5\), y después de tratar el factor \(2\) solo se recorren candidatos impares. En la práctica, la cota efectiva disminuye aún más porque el resto se encoge cada vez que se encuentra un factor.
本题要求求出 \(600851475143\) 的最大素因子。较小的示例 \(13195\) 已经把问题的本质说明得很清楚：
$$13195 = 5 \cdot 7 \cdot 13 \cdot 29,$$
因此它的最大素因子是 \(29\)。真正的目标数大得多，但思路完全一致：一边确认素因子，一边把这些因子从当前余数中彻底除掉，直到余数变成 \(1\) 或者本身就是素数。
这道题的核心是带有严格不变量的试除法。算法并不是“从小到大乱试一遍”那么简单；真正保证正确性的，是这样一个事实：当较小的素因子都已经被清除之后，当前余数还能包含哪些因子其实受到很强的约束。
根据算术基本定理，任意 \(N \ge 2\) 都能唯一写成
$$N = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}, \qquad 2 \le p_1 \lt p_2 \lt \cdots \lt p_r,$$
其中每个指数 \(a_i \ge 1\)。本题要求的答案就是最右边那个素数 \(p_r\)，也就是分解中最大的素因子。
不过，实现时并不需要一开始就把整套分解全部写出来。只要不断剥离已经确认的小素因子，最终留下来的数如果大于 \(1\)，它就必然是最后也是最大的那个素因子。
设当前正在考虑的奇数候选为 \(d\)，并且所有小于 \(d\) 的可能因子都已经处理完毕。记此时的余数为 \(n\)。算法始终维持下面这个不变量：
$$N = \left(\prod_{p \lt d} p^{e_p}\right) n,$$
这里乘积部分恰好表示之前已经完整移除的那些素数幂，而剩下的 \(n\) 不再含有任何小于 \(d\) 的素因子。
这个不变量直接解释了程序中的两个关键动作。
第一，因子 \(2\) 要在最开头单独处理。因为 \(2\) 是唯一的偶素数，反复除尽 \(2\) 以后，余数一定变成奇数，后面自然只需要继续检查奇数候选。
第二，如果某个奇数候选 \(d\) 真正整除了当前余数，那么这个 \(d\) 必定是素数。原因很简单：若 \(d\) 是合数，它必然有某个更小的素因子 \(q \lt d\)。既然 \(d\) 整除当前余数，那么 \(q\) 也会整除当前余数，这就与“不再含有小于 \(d\) 的素因子”矛盾。也就是说，虽然外层循环枚举的是所有奇数，但任何真正成功的奇数除数都会被这个不变量自动证明为素数。
此外，一旦找到某个因子，就必须把它全部除尽。如果 \(d^k \mid n\)，那么内层循环会把这 \(k\) 个 \(d\) 全部去掉，然后再继续下一个候选。只有这样，新的余数才重新满足同样的不变量。
经典结论是：如果正整数 \(m\) 是合数，那么它一定有一个不超过 \(\sqrt{m}\) 的素因子。证明很直接。若 \(m = ab\) 且 \(1 \lt a \le b\)，那么 \(a^2 \le ab = m\)，所以 \(a \le \sqrt{m}\)，而 \(a\) 的某个素因子也会整除 \(m\)。
关键在于，这个结论要应用到当前余数上，而不是原始输入上。假设当前余数 \(n\) 仍然是合数，那么它必然还有一个素因子 \(\le \sqrt{n}\)。因此，只要当前候选已经大于 \(\sqrt{n}\)，就只剩下两种可能：
这也是为什么循环上界会随着余数缩小而不断收紧。它并不是固定的 \(\sqrt{N}\)，而是动态依赖于当前余数。C++ 版本把这个判断写成基于除法的等价形式，以避免一般情形下的整数溢出；Python 和 Java 版本则使用数学上等价的平方比较。
从 \(n = 13195\) 开始。它是奇数，所以一开始没有 \(2\) 可以移除。
按升序检查奇数候选时，第一个真正整除的数是 \(5\)：
$$13195 \div 5 = 2639.$$
新的余数 \(2639\) 不再能被 \(5\) 整除，于是继续向后检查。下一个成功的候选是 \(7\)：
$$2639 \div 7 = 377.$$
接着 \(13\) 也能整除：
$$377 \div 13 = 29.$$
此时余数变成 \(29\)。再往后的候选一旦超过 \(\sqrt{29}\)，就不可能再找到新的非平凡因子。因为如果 \(29\) 是合数，它必须含有某个不大于 \(\sqrt{29}\) 的素因子，但事实并没有。因此剩下的 \(29\) 本身就是素数，也就是最大素因子。
目标数的处理过程完全相同。试除法最终按从小到大的顺序剥离出这些素因子：
$$600851475143 = 71 \cdot 839 \cdot 1471 \cdot 6857.$$
先除去 \(71\)，再除去 \(839\)，再除去 \(1471\) 之后，剩下的余数是 \(6857\)。一旦搜索上界超过 \(\sqrt{6857}\)，这个余数就不可能还是合数，于是它必定是素数。由此可知本题答案为 \(6857\)。
C++、Python 和 Java 三个实现都遵循同一个数学方案：维护一个可变余数，保存“目前已经确认的最大素因子”，一旦发现新的因子就立刻把余数缩小。
第一阶段会在数字仍为偶数时不断除以 \(2\)。这样可以一次性把唯一的偶素数完全清除掉。如果至少发生过一次这样的除法，那么当前已知的最大素因子至少是 \(2\)，并且余数从此变成奇数。
之后，实现会按顺序检查 \(3, 5, 7, \dots\) 这些奇数候选。若某个候选能整除当前余数，就不断重复除法，直到这个因子完全消失，然后更新当前已知的最大素因子。这一步在数学上对应于一次性移除某个素因子的整个幂 \(p^a\)。
由于余数会不断变小，停止条件也是针对“当前余数”而不是“原始输入”来判断的。这正是程序在实践中比固定上界的朴素试探更高效的原因。
奇数候选循环结束后，还会做一次最终判断。如果余数仍然大于 \(1\)，根据前面的平方根论证，它必然是素数，因此就是最终答案。三个实现都会先验证示例 \(13195 \mapsto 29\)，然后再输出主问题的结果。
在最坏情况下，试除法需要检查大约到 \(\sqrt{N}\) 为止的奇数，因此时间复杂度是 \(O(\sqrt{N})\)。算法只保存常数个整数状态，所以空间复杂度是 \(O(1)\)。
对于本题给定的数，即使保守估计也不大：\(\sqrt{600851475143}\) 约为 \(7.75 \times 10^5\)，而且在处理完因子 \(2\) 以后只需要检查奇数。实际运行时，一旦找到因子，余数就会缩小，搜索上界也会随之下降，因此通常会比最坏上界更快。
Нужно найти наибольший простой делитель числа \(600851475143\). Малый пример \(13195\) сразу показывает смысл задачи:
$$13195 = 5 \cdot 7 \cdot 13 \cdot 29,$$
значит, для него ответ равен \(29\). Для большого целевого числа используется та же идея: подтверждённые простые множители последовательно удаляются из текущего остатка, который всё время уменьшается.
Используется аккуратный вариант пробного деления. Его корректность основана не на грубом переборе, а на инварианте, описывающем, какие простые множители вообще могут ещё содержаться в текущем остатке после удаления всех меньших.
Согласно основной теореме арифметики, каждое целое \(N \ge 2\) единственным образом представимо в виде
$$N = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}, \qquad 2 \le p_1 \lt p_2 \lt \cdots \lt p_r,$$
где все \(a_i \ge 1\). Ответом является \(p_r\), то есть наибольшее простое число в этом разложении.
Полное разложение заранее знать не нужно. Достаточно последовательно удалять найденные малые простые множители, пока остаток не станет равным \(1\) или сам не окажется простым.
Пусть уже обработаны все возможные делители меньше некоторого текущего нечётного кандидата \(d\), а текущий остаток равен \(n\). Тогда поддерживается инвариант
$$N = \left(\prod_{p \lt d} p^{e_p}\right) n,$$
где произведение содержит ровно те простые степени, которые уже полностью удалены, а у \(n\) нет ни одного простого делителя меньше \(d\).
Из этого сразу следуют два важных свойства алгоритма.
Во-первых, множитель \(2\) обрабатывается отдельно в самом начале. После того как все двойки удалены, остаток становится нечётным, и дальше нет смысла проверять чётные кандидаты.
Во-вторых, если нечётный кандидат \(d\) делит текущий остаток, то \(d\) обязан быть простым. Если бы \(d\) был составным, у него существовал бы простой делитель \(q \lt d\). Тогда тот же \(q\) делил бы и текущий остаток, что противоречит инварианту. Поэтому внешний цикл может идти по всем нечётным числам; любой успешный делитель автоматически оказывается простым.
Найденный множитель удаляется полностью. Если \(d^k \mid n\), внутренний цикл делит до тех пор, пока из остатка не исчезнут все \(k\) копий множителя \(d\). После этого инвариант снова верен для следующего кандидата.
Классический факт: если положительное число \(m\) составное, то у него есть простой делитель, не превосходящий \(\sqrt{m}\). Действительно, если \(m = ab\) и \(1 \lt a \le b\), то \(a^2 \le ab = m\), значит \(a \le \sqrt{m}\), а некоторый простой делитель числа \(a\) делит и \(m\).
Важно применять это рассуждение не к исходному числу, а именно к текущему остатку. Если остаток \(n\) ещё составной, то у него обязан быть простой делитель \(\le \sqrt{n}\). Следовательно, когда текущий кандидат стал больше \(\sqrt{n}\), остаются только два варианта:
Поэтому верхняя граница поиска динамически уменьшается вместе с остатком. В реализации на C++ эта проверка записана в эквивалентной форме через деление, чтобы избежать переполнения; версии на Python и Java используют равносильное сравнение с квадратом.
Начинаем с \(n = 13195\). Число нечётное, поэтому множитель \(2\) отсутствует.
При просмотре нечётных кандидатов по возрастанию первым успешным делителем оказывается \(5\):
$$13195 \div 5 = 2639.$$
После этого \(2639\) уже не делится на \(5\), и поиск продолжается. Следующий успешный кандидат равен \(7\):
$$2639 \div 7 = 377.$$
Затем делит \(13\):
$$377 \div 13 = 29.$$
Теперь остаток равен \(29\). Следующий кандидат уже превышал бы \(\sqrt{29}\). Поскольку составной остаток обязан иметь меньший простой делитель, число \(29\) вынуждено быть простым. Значит, наибольший простой делитель исходного числа равен \(29\).
Для целевого числа работает та же логика. Пробное деление последовательно извлекает простые множители:
$$600851475143 = 71 \cdot 839 \cdot 1471 \cdot 6857.$$
После удаления \(71\), затем \(839\) и затем \(1471\) остаётся \(6857\). Когда граница поиска переходит через \(\sqrt{6857}\), этот остаток уже не может быть составным, а значит он прост. Следовательно, искомый ответ равен \(6857\).
Реализации на C++, Python и Java следуют одному и тому же математическому плану: поддерживается изменяемый остаток, хранится наибольший уже подтверждённый простой множитель, и остаток немедленно уменьшается при нахождении нового делителя.
На первом этапе число делится на \(2\), пока это возможно. Так полностью устраняется единственное чётное простое число. Если хотя бы одно деление произошло, то лучший найденный ответ уже не меньше \(2\), а остаток становится нечётным.
Далее реализация проверяет кандидаты \(3, 5, 7, \dots\) по возрастанию. Когда текущий кандидат делит остаток, деление повторяется до полного исчезновения этого множителя, после чего обновляется наибольший найденный простой делитель. Это в точности соответствует удалению всей простой степени \(p^a\) перед переходом к следующему кандидату.
Поскольку остаток уменьшается, условие остановки сравнивается именно с текущим остатком, а не с исходным числом. Благодаря этому метод на практике быстрее, чем наивный перебор с фиксированной верхней границей.
После завершения цикла по нечётным кандидатам остаётся заключительная проверка. Если остаток всё ещё больше \(1\), то по аргументу с квадратным корнем он обязан быть простым и становится окончательным ответом. Кроме того, все реализации проверяют пример \(13195 \mapsto 29\), прежде чем вывести результат для основного входа.
В худшем случае пробное деление проверяет нечётные числа примерно до \(\sqrt{N}\), поэтому время работы равно \(O(\sqrt{N})\). Дополнительная память постоянна, то есть \(O(1)\).
Для данного числа даже пессимистичная оценка невелика: \(\sqrt{600851475143}\) составляет примерно \(7.75 \times 10^5\), а после удаления фактора \(2\) рассматриваются только нечётные кандидаты. На практике эффективная граница ещё меньше, потому что остаток сокращается при каждом найденном множителе.
المطلوب هو إيجاد أكبر عامل أولي للعدد \(600851475143\). المثال الأصغر \(13195\) يوضح المطلوب مباشرة:
$$13195 = 5 \cdot 7 \cdot 13 \cdot 29,$$
ومن ثم فإن أكبر عامل أولي له هو \(29\). العدد المطلوب في المسألة أكبر بكثير، لكن الفكرة نفسها لا تتغير: نؤكد عاملاً أوليًا، ثم نحذفه بالكامل من الباقي الحالي، ونكرر ذلك حتى يصبح الباقي \(1\) أو يصبح عددًا أوليًا بحد ذاته.
الحل يعتمد على قسمة تجريبية مضبوطة بإحكام. صحة الخوارزمية لا تأتي من مجرد تجربة كثير من القواسم، بل من ثابت منطقي يصف بدقة ما الذي يمكن أن يبقى داخل العدد المتبقي بعد إزالة جميع العوامل الأصغر منه.
بحسب المبرهنة الأساسية في الحساب، يمكن كتابة كل عدد صحيح \(N \ge 2\) بصورة وحيدة على الشكل
$$N = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}, \qquad 2 \le p_1 \lt p_2 \lt \cdots \lt p_r,$$
حيث كل \(a_i \ge 1\). الجواب المطلوب في هذه المسألة هو \(p_r\)، أي أكبر عدد أولي يظهر في هذا التحليل.
لكن لا حاجة إلى معرفة التحليل الكامل مسبقًا. يكفي أن نزيل العوامل الأولية الصغيرة بالتدريج، وعندئذٍ يكون الباقي الأخير - إن كان أكبر من \(1\) - هو العامل الأولي الأكبر نفسه.
لنفترض أننا انتهينا من فحص كل القواسم الممكنة الأصغر من مرشح فردي حالي \(d\)، وأن الباقي الحالي هو \(n\). عندها يبقى الثابت التالي صحيحًا:
$$N = \left(\prod_{p \lt d} p^{e_p}\right) n,$$
حيث يحتوي حاصل الضرب على القوى الأولية التي أزيلت بالكامل سابقًا، بينما لا يملك \(n\) أي عامل أولي أصغر من \(d\).
هذا الثابت يفسر قرارين أساسيين في الحل.
أولاً، يُعالج العامل \(2\) وحده في البداية. بعد قسمة العدد على \(2\) ما دام زوجيًا، يصبح الباقي فرديًا، ولذلك لا نحتاج لاحقًا إلا إلى فحص المرشحات الفردية.
ثانيًا، إذا قسّم مرشح فردي \(d\) الباقي الحالي فعلًا، فإن \(d\) لا بد أن يكون أوليًا. فلو كان مركبًا لامتلك عاملاً أوليًا أصغر \(q \lt d\)، وهذا \(q\) نفسه سيقسم الباقي الحالي، وهو ما يناقض الثابت. لذلك يمكن للحل أن يمر على جميع الأعداد الفردية، لأن أي عدد فردي ينجح في القسمة يكون قد ثبتت أوليته تلقائيًا.
ومن الضروري أيضًا حذف هذا العامل بالكامل. فإذا كان \(d^k \mid n\)، فإن الحلقة الداخلية تستمر في القسمة حتى تختفي جميع نسخ \(d\) من الباقي، وبذلك يعود الثابت صحيحًا قبل الانتقال إلى المرشح التالي.
الحقيقة الكلاسيكية هي: إذا كان عدد موجب \(m\) مركبًا، فلا بد أن يملك عاملاً أوليًا لا يتجاوز \(\sqrt{m}\). والبرهان بسيط: إذا كان \(m = ab\) مع \(1 \lt a \le b\)، فإن \(a^2 \le ab = m\)، ومن ثم \(a \le \sqrt{m}\)، وأي عامل أولي لـ \(a\) سيكون عاملًا لـ \(m\) أيضًا.
المهم هنا هو تطبيق هذه الحقيقة على الباقي الحالي لا على العدد الأصلي. فإذا كان الباقي \(n\) ما يزال مركبًا، وجب أن يملك عاملاً أوليًا \(\le \sqrt{n}\). لذلك ما إن يتجاوز المرشح الحالي \(\sqrt{n}\) حتى لا تبقى إلا حالتان ممكنتان:
لهذا السبب يتقلص حد البحث كلما صغر الباقي. ليس الحد ثابتًا عند \(\sqrt{N}\)، بل يتبع الباقي الحالي خطوةً بخطوة. تنفيذ C++ يكتب هذا الاختبار بصيغة قسمة مكافئة لتجنب مشاكل الفيض عمومًا، أما تنفيذا Python وJava فيستخدمان المقارنة المربعة المكافئة رياضيًا.
نبدأ من \(n = 13195\). هذا العدد فردي، لذا لا يوجد عامل \(2\) لإزالته.
عند تجربة المرشحات الفردية بترتيب تصاعدي، يكون أول عامل ناجح هو \(5\):
$$13195 \div 5 = 2639.$$
العدد \(2639\) لم يعد يقبل القسمة على \(5\)، لذا نتابع الفحص. المرشح الناجح التالي هو \(7\):
$$2639 \div 7 = 377.$$
ثم يقسم \(13\) هذا الباقي:
$$377 \div 13 = 29.$$
أصبح الباقي الآن \(29\). المرشح التالي سيكون أكبر من \(\sqrt{29}\)، ولو كان \(29\) مركبًا لوجب أن يملك عاملاً أوليًا أصغر من ذلك. بما أن هذا لم يحدث، فإن \(29\) أولي، وبالتالي فهو أكبر عامل أولي للعدد الأصلي.
العدد المطلوب في المسألة يُحل بالطريقة نفسها تمامًا. فالقسمة التجريبية تستخرج العوامل الأولية تصاعديًا:
$$600851475143 = 71 \cdot 839 \cdot 1471 \cdot 6857.$$
بعد إزالة \(71\)، ثم \(839\)، ثم \(1471\)، يبقى العدد \(6857\). وعندما يتجاوز حد البحث \(\sqrt{6857}\)، يصبح من المستحيل أن يكون هذا الباقي مركبًا، فيلزم أنه أولي. لذلك تكون الإجابة النهائية هي \(6857\).
تنفيذات C++ وPython وJava تتبع الخطة الرياضية نفسها: تحتفظ بباقٍ قابل للتغيير، وتحتفظ بأكبر عامل أولي تم تأكيده حتى الآن، وتقلص الباقي فور العثور على عامل جديد.
في المرحلة الأولى يُقسم العدد على \(2\) ما دام زوجيًا. بهذه الطريقة يُزال العامل الأولي الزوجي الوحيد بالكامل. وإذا حدثت قسمة واحدة على الأقل، فإن أفضل إجابة مؤكدة حتى تلك اللحظة تكون على الأقل \(2\)، ويصبح الباقي فرديًا.
بعد ذلك تفحص الخوارزمية المرشحات الفردية \(3, 5, 7, \dots\) بترتيب تصاعدي. فإذا قسّم المرشح الحالي الباقي، تتكرر القسمة حتى يختفي هذا العامل تمامًا، ثم يجري تحديث أكبر عامل أولي معروف. وهذا يطابق رياضيًا إزالة القوة الكاملة \(p^a\) قبل الانتقال إلى المرشح التالي.
ولأن الباقي يتناقص باستمرار، فإن شرط التوقف يُقاس بالنسبة إلى الباقي الحالي لا إلى العدد الأصلي. وهذا هو السبب في أن الأداء العملي يكون أفضل عادةً من التقدير الساذج بحد ثابت.
بعد انتهاء حلقة المرشحات الفردية، تبقى خطوة أخيرة. إذا كان الباقي ما يزال أكبر من \(1\)، فإنه يجب أن يكون أوليًا بحسب برهان الجذر التربيعي، وعندئذٍ يكون هو الجواب. كما أن كل تنفيذ يتحقق أولًا من المثال \(13195 \mapsto 29\) قبل طباعة نتيجة الإدخال الرئيسي.
في أسوأ الحالات، تفحص القسمة التجريبية الأعداد الفردية حتى ما يقارب \(\sqrt{N}\)، لذا يكون التعقيد الزمني \(O(\sqrt{N})\). أما الذاكرة الإضافية فتبقى ثابتة، أي \(O(1)\).
وبالنسبة لهذا العدد تحديدًا، حتى الحد المتشائم صغير نسبيًا: \(\sqrt{600851475143}\) يساوي تقريبًا \(7.75 \times 10^5\)، وبعد معالجة العامل \(2\) لا يبقى إلا فحص المرشحات الفردية. وفي التطبيق العملي ينخفض الحد الفعلي أكثر لأن الباقي يصغر كلما عُثر على عامل جديد.