The task is to find the smallest positive integer that is divisible by every number from \(1\) through \(n\). For the original Project Euler instance, \(n=20\), so the target is the common multiple shared by the entire interval \([1,20]\), but taken as small as possible.
This is not a search problem over many candidates. The answer is a single arithmetic object:
$$L_n=\operatorname{lcm}(1,2,\ldots,n).$$
Once the problem is phrased as an lcm, the mathematics becomes very clean. The only questions are which prime powers must appear, and how to build that value efficiently without factoring every number from scratch.
Any valid answer must be divisible by every \(k\) with \(1 \le k \le n\). By definition, the least common multiple of those numbers is the smallest integer with exactly that property. Therefore
$$\boxed{L_n=\operatorname{lcm}(1,2,\ldots,n).}$$
If a number is divisible by the whole range, then it is a common multiple, so it must be a multiple of \(L_n\). Conversely, \(L_n\) itself already divides by each member of the range. That proves minimality immediately.
By the Fundamental Theorem of Arithmetic, every positive integer has a unique prime factorization. That means the lcm can be determined prime by prime. For each prime \(p \le n\), we ask for the largest exponent that occurs in some integer between \(1\) and \(n\).
Define
$$e_p=\max\{e \ge 0 : p^e \le n\}.$$
Then the exponent of \(p\) in \(L_n\) is exactly \(e_p\), so
$$L_n=\prod_{p \le n} p^{e_p},$$
where the product runs over primes only.
This explains why many numbers contribute nothing new. A composite number only matters when it contains a prime power that has not already appeared. For the original case \(n=20\), the decisive prime powers are
$$2^4,\quad 3^2,\quad 5,\quad 7,\quad 11,\quad 13,\quad 17,\quad 19.$$
Everything else in \(1,\ldots,20\) is already covered by these factors.
The code does not explicitly enumerate primes. Instead it builds the same value incrementally. Let
$$A_1=1,\qquad A_k=\operatorname{lcm}(A_{k-1},k)\quad (k\ge 2).$$
The key invariant is
$$A_k=\operatorname{lcm}(1,2,\ldots,k).$$
The proof is a one-line induction. Assume \(A_{k-1}\) is already the least common multiple of \(1,\ldots,k-1\). Any integer divisible by \(1,\ldots,k\) must then be divisible by both \(A_{k-1}\) and \(k\), so the smallest such integer is exactly \(\operatorname{lcm}(A_{k-1},k)\). After the loop reaches \(k=n\), the accumulator equals \(L_n\).
This also clarifies what each step does: it inserts only the prime-power content of \(k\) that is still missing. If \(k\) brings no larger exponent for any prime, the accumulator stays unchanged.
Each update is computed with the classical identity
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$$
The gcd measures the overlap between the prime factorizations of \(a\) and \(b\), so dividing by it removes the duplicated part before multiplying. The gcd itself is obtained by the Euclidean algorithm:
$$\gcd(a,b)=\gcd(b,a\bmod b),\qquad \gcd(a,0)=a.$$
So the whole solution is built from a very small chain of ideas: the answer is an lcm, pairwise lcm can be expressed through a gcd, and gcd is cheap to compute recursively.
The prime-power description gives
$$L_{10}=2^3\cdot 3^2\cdot 5\cdot 7=2520,$$
because the largest powers not exceeding \(10\) are \(8,9,5,\) and \(7\).
The iterative recurrence reaches the same answer through the sequence
$$1\to 2\to 6\to 12\to 60\to 60\to 420\to 840\to 2520\to 2520.$$
The repeated values are informative: \(6\) does not change the accumulator because its factors \(2\) and \(3\) are already present, and \(10\) does not change it because \(2\cdot 5\) is already covered after earlier steps. This is exactly the behavior exploited by the loop.
The C++, Python, and Java implementations all keep one accumulator, start it at \(1\), and iterate upward from \(2\) to \(n\). After processing \(k\), the accumulator equals the least common multiple of the prefix \(1,\ldots,k\). That invariant is the entire algorithmic core.
The pairwise lcm step is expressed slightly differently in each language, but the mathematics is identical. The C++ implementation delegates the lcm computation to the standard library. The Python implementation builds the lcm from a standard-library gcd. The Java implementation writes the Euclidean loop explicitly and divides by the gcd before multiplying, which keeps the intermediate product smaller. All three versions include the checkpoint \(n=10 \mapsto 2520\). The C++ entry point can also accept another positive value of \(n\), while the Python and Java entry points print the standard \(n=20\) case when run directly.
There are \(n-1\) loop iterations. In the usual arithmetic-step model, each iteration performs one gcd computation, and the Euclidean algorithm needs \(O(\log k)\) remainder steps when paired with \(k\). Summing over \(k=2\) through \(n\) gives \(O(n\log n)\) arithmetic work.
The extra memory usage is \(O(1)\): apart from the loop counter, the algorithm only maintains the current accumulator. If one studies very large \(n\) with full bit complexity, the cost of integer arithmetic grows because \(L_n\) itself grows quickly. For the original Project Euler input \(n=20\), however, the computation is tiny and comfortably fits standard integer types.
Gesucht ist die kleinste positive ganze Zahl, die durch jede Zahl von \(1\) bis \(n\) teilbar ist. Im ursprünglichen Project-Euler-Fall gilt \(n=20\); man sucht also die kleinste Zahl, die gleichzeitig durch alle Zahlen in \([1,20]\) teilbar ist.
Das ist keine offene Suche über viele Kandidaten, sondern ein klar bestimmtes arithmetisches Objekt:
$$L_n=\operatorname{lcm}(1,2,\ldots,n).$$
Sobald man die Aufgabe als kgV eines ganzen Intervalls formuliert, fällt die Struktur der Lösung direkt ins Auge. Man muss nur verstehen, welche Primzahlpotenzen zwingend vorkommen und warum ein schrittweiser Aufbau per kgV exakt denselben Wert liefert.
Jede zulässige Antwort muss durch jedes \(k\) mit \(1 \le k \le n\) teilbar sein. Damit ist sie ein gemeinsames Vielfaches aller Zahlen des Bereichs. Das kleinste gemeinsame Vielfache ist per Definition die kleinste Zahl mit genau dieser Eigenschaft. Also gilt
$$\boxed{L_n=\operatorname{lcm}(1,2,\ldots,n).}$$
Ist eine Zahl durch den ganzen Bereich teilbar, dann ist sie ein gemeinsames Vielfaches und somit ein Vielfaches von \(L_n\). Umgekehrt ist \(L_n\) selbst bereits durch alle Zahlen von \(1\) bis \(n\) teilbar. Damit ist die Minimalität bewiesen.
Nach dem Fundamentalsatz der Arithmetik besitzt jede positive ganze Zahl eine eindeutige Primfaktorzerlegung. Das kgV lässt sich deshalb Primzahl für Primzahl bestimmen. Für jedes Primelement \(p \le n\) braucht man genau den größten Exponenten, der in irgendeiner Zahl zwischen \(1\) und \(n\) vorkommt.
Definiere
$$e_p=\max\{e \ge 0 : p^e \le n\}.$$
Dann ist der Exponent von \(p\) in \(L_n\) genau \(e_p\), also
$$L_n=\prod_{p \le n} p^{e_p},$$
wobei nur über Primzahlen multipliziert wird.
Damit wird auch klar, warum viele zusammengesetzte Zahlen nichts Neues beitragen. Sie bündeln nur Primfaktoren, die bereits durch kleinere Zahlen erzwungen wurden. Für \(n=20\) sind die entscheidenden Primzahlpotenzen
$$2^4,\quad 3^2,\quad 5,\quad 7,\quad 11,\quad 13,\quad 17,\quad 19.$$
Alle übrigen Zahlen in \(1,\ldots,20\) sind durch diese Faktoren bereits abgedeckt.
Der Code zählt Primzahlen nicht explizit auf. Stattdessen baut er denselben Wert schrittweise auf. Man setze
$$A_1=1,\qquad A_k=\operatorname{lcm}(A_{k-1},k)\quad (k\ge 2).$$
Die zentrale Invariante lautet
$$A_k=\operatorname{lcm}(1,2,\ldots,k).$$
Der Beweis ist eine direkte Induktion. Angenommen, \(A_{k-1}\) ist bereits das kgV von \(1,\ldots,k-1\). Jede Zahl, die durch \(1,\ldots,k\) teilbar ist, muss dann sowohl durch \(A_{k-1}\) als auch durch \(k\) teilbar sein. Die kleinste solche Zahl ist folglich \(\operatorname{lcm}(A_{k-1},k)\). Wenn die Schleife bei \(k=n\) endet, steht also genau \(L_n\) im Akkumulator.
Jeder Schleifendurchlauf ergänzt nur die noch fehlenden Primzahlpotenzen von \(k\). Bringt \(k\) keinen größeren Exponenten mit, bleibt der Akkumulator unverändert.
Jeder Aktualisierungsschritt benutzt die klassische Identität
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$$
Der ggT beschreibt genau den überlappenden Teil der Primfaktorzerlegungen von \(a\) und \(b\). Durch die Division entfernt man die doppelt gezählten Faktoren, bevor multipliziert wird. Der ggT selbst wird mit dem euklidischen Algorithmus berechnet:
$$\gcd(a,b)=\gcd(b,a\bmod b),\qquad \gcd(a,0)=a.$$
Die ganze Lösung besteht also aus einer sehr kurzen mathematischen Kette: Gesucht ist ein kgV, ein kgV lässt sich paarweise über einen ggT ausdrücken, und ein ggT ist effizient berechenbar.
Aus der Primzahlpotenz-Sicht erhält man
$$L_{10}=2^3\cdot 3^2\cdot 5\cdot 7=2520,$$
denn die größten Potenzen bis \(10\) sind \(8,9,5\) und \(7\).
Die iterative Konstruktion liefert denselben Wert über die Folge
$$1\to 2\to 6\to 12\to 60\to 60\to 420\to 840\to 2520\to 2520.$$
Gerade die Wiederholungen sind aufschlussreich: Bei \(6\) ändert sich nichts, weil \(2\) und \(3\) bereits vollständig enthalten sind; bei \(10\) ebenso, weil \(2\cdot 5\) nach früheren Schritten schon abgedeckt ist. Genau dieses Verhalten nutzt die Schleife aus.
Die C++-, Python- und Java-Implementierungen halten einen einzigen Akkumulator, initialisieren ihn mit \(1\) und laufen dann von \(2\) bis \(n\) hoch. Nach dem Schritt zu \(k\) ist der Akkumulator das kgV des Präfixes \(1,\ldots,k\). Diese Invariante ist der gesamte algorithmische Kern.
Unterschiede gibt es nur in der Formulierung des paarweisen kgV-Schritts. Die C++-Implementierung verwendet dafür die Standardbibliothek. Die Python-Implementierung baut das kgV aus einem Standard-ggT auf. Die Java-Implementierung schreibt die euklidische Schleife explizit hin und dividiert vor der Multiplikation durch den ggT, damit das Zwischenprodukt kleiner bleibt. Alle drei Versionen enthalten den Kontrollpunkt \(n=10 \mapsto 2520\). Der C++-Einstiegspunkt kann außerdem einen anderen positiven Wert von \(n\) verarbeiten; Python und Java geben beim direkten Start den Standardfall \(n=20\) aus.
Es gibt \(n-1\) Schleifendurchläufe. Im üblichen Modell arithmetischer Operationen enthält jeder Durchlauf genau eine ggT-Berechnung, und der euklidische Algorithmus benötigt dabei \(O(\log k)\) Restschritte. Aufsummiert über \(k=2\) bis \(n\) ergibt das \(O(n\log n)\) arithmetische Arbeit.
Der zusätzliche Speicherbedarf ist \(O(1)\), denn außer Zählvariable und Akkumulator wird nichts Wesentliches gehalten. Betrachtet man sehr große \(n\) mit voller Bitkomplexität, steigen die Kosten der Ganzzahlarithmetik mit, weil \(L_n\) selbst schnell wächst. Für den ursprünglichen Project-Euler-Wert \(n=20\) ist die Rechnung jedoch winzig und passt problemlos in normale Ganzzahltypen.
İstenen şey, \(1\)'den \(n\)'ye kadar her sayıya tam bölünebilen en küçük pozitif tam sayıyı bulmaktır. Orijinal Project Euler sorusunda \(n=20\) alınır; yani \([1,20]\) aralığındaki tüm sayıların ortak katı olan en küçük sayı aranır.
Bu, rastgele adaylar arasında arama yapılan bir problem değildir. Cevap tek bir aritmetik nesnedir:
$$L_n=\operatorname{lcm}(1,2,\ldots,n).$$
Problem EKOK olarak yazıldığında çözümün yapısı hemen görünür. Geriye yalnızca hangi asal kuvvetlerin zorunlu olduğunu görmek ve kodun bunu neden adım adım doğru biçimde kurduğunu açıklamak kalır.
Geçerli her cevap, \(1 \le k \le n\) aralığındaki her \(k\) sayısına bölünmelidir. Bu da cevabın bu sayıların ortak katı olması demektir. En küçük ortak kat tanım gereği bu özelliğe sahip en küçük sayıdır. Dolayısıyla
$$\boxed{L_n=\operatorname{lcm}(1,2,\ldots,n).}$$
Eğer bir sayı bütün aralığa bölünüyorsa, ortak kattır ve bu yüzden \(L_n\)'in katı olmak zorundadır. Ters yönde, \(L_n\) zaten listedeki her sayıya bölünür. Böylece minimallik doğrudan kanıtlanır.
Aritmetiğin Temel Teoremi her pozitif tam sayının asal çarpanlara tekil biçimde ayrıldığını söyler. Bu nedenle EKOK'u asal bazında belirleyebiliriz. Her \(p \le n\) asalı için, \(1\) ile \(n\) arasında görülen en büyük üssü almak yeterlidir.
Şöyle tanımlayalım:
$$e_p=\max\{e \ge 0 : p^e \le n\}.$$
O zaman \(L_n\) içindeki \(p\) üssü tam olarak \(e_p\) olur ve
$$L_n=\prod_{p \le n} p^{e_p},$$
burada çarpım yalnızca asallar üzerindedir.
Bu bakış açısı, birçok bileşik sayının neden yeni bir bilgi getirmediğini de açıklar. Bir bileşik sayı yalnızca daha önce görülmüş asal kuvvetleri bir araya getirir. \(n=20\) için belirleyici asal kuvvetler
$$2^4,\quad 3^2,\quad 5,\quad 7,\quad 11,\quad 13,\quad 17,\quad 19$$
olur. \(1,\ldots,20\) içindeki diğer bütün sayılar bu çarpanların içinde zaten temsil edilir.
Kod asalları tek tek saymaz. Bunun yerine aynı sayıyı artımlı olarak kurar. Şöyle yazalım:
$$A_1=1,\qquad A_k=\operatorname{lcm}(A_{k-1},k)\quad (k\ge 2).$$
Temel değişmez şudur:
$$A_k=\operatorname{lcm}(1,2,\ldots,k).$$
İspat tek satırlık bir tümevarımdır. \(A_{k-1}\)'in zaten \(1,\ldots,k-1\) için EKOK olduğunu varsayalım. \(1,\ldots,k\) aralığındaki her sayıya bölünen herhangi bir sayı, hem \(A_{k-1}\)'e hem de \(k\)'ya bölünmek zorundadır. Böyle sayıların en küçüğü de tam olarak \(\operatorname{lcm}(A_{k-1},k)\) olur. Döngü \(k=n\)'e ulaştığında biriktiricide \(L_n\) vardır.
Yani her adım yalnızca \(k\)'nın henüz eksik olan asal kuvvet katkısını ekler. \(k\) hiçbir asal için daha büyük bir üs getirmiyorsa, biriktirici değişmeden kalır.
Her güncelleme şu klasik özdeşlikle yapılır:
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$$
EBOB, \(a\) ile \(b\)'nin asal çarpan ayrışımlarındaki ortak kısmı ölçer; bu yüzden önce EBOB'a bölmek, çift sayılan kısmı temizler. EBOB da Öklid algoritmasıyla bulunur:
$$\gcd(a,b)=\gcd(b,a\bmod b),\qquad \gcd(a,0)=a.$$
Böylece çözüm çok kısa bir matematik zincirine indirgenir: cevap bir EKOK'tur, ikili EKOK EBOB cinsinden yazılır ve EBOB hızlı biçimde hesaplanır.
Asal kuvvet yaklaşımı
$$L_{10}=2^3\cdot 3^2\cdot 5\cdot 7=2520$$
sonucunu verir; çünkü \(10\)'u aşmayan en büyük kuvvetler sırasıyla \(8,9,5\) ve \(7\)'dir.
İteratif yapı da aynı sonuca şu diziyle ulaşır:
$$1\to 2\to 6\to 12\to 60\to 60\to 420\to 840\to 2520\to 2520.$$
Tekrarlanan değerler özellikle öğreticidir: \(6\) adımında biriktirici değişmez, çünkü \(2\) ve \(3\) zaten vardır; \(10\) adımında da değişmez, çünkü \(2\cdot 5\) daha önce kapsanmıştır. Döngünün kullandığı mantık tam olarak budur.
C++, Python ve Java uygulamalarının hepsi tek bir biriktirici tutar, bunu \(1\) ile başlatır ve sonra \(2\)'den \(n\)'ye kadar ilerler. \(k\) işlendiğinde biriktiricide \(1,\ldots,k\) önekinin EKOK'u vardır. Algoritmanın bütün özü bu değişmezdir.
İkili EKOK adımının yazılışı diller arasında biraz farklıdır, ama matematik aynıdır. C++ sürümü EKOK hesabını standart kütüphaneye bırakır. Python sürümü EKOK'u standart kütüphanedeki EBOB üzerinden kurar. Java sürümü Öklid döngüsünü açıkça yazar ve çarpmadan önce EBOB'a böler; böylece ara çarpım daha küçük kalır. Üç sürüm de \(n=10 \mapsto 2520\) kontrolünü içerir. C++ giriş noktası ayrıca farklı bir pozitif \(n\) değeri alabilir; Python ve Java doğrudan çalıştırıldığında standart \(n=20\) durumunu yazdırır.
\(n-1\) adet döngü adımı vardır. Alışılmış aritmetik adım modelinde her iterasyon bir EBOB hesabı yapar ve Öklid algoritması \(k\) ile eşleştiğinde \(O(\log k)\) kalan adımı gerektirir. \(k=2\)'den \(n\)'ye kadar toplandığında toplam iş \(O(n\log n)\) olur.
Ek bellek kullanımı \(O(1)\)'dir; sayaçlar dışında yalnızca mevcut biriktirici tutulur. Çok büyük \(n\) değerlerinde tam bit karmaşıklığı incelenirse tam sayı aritmetiğinin maliyeti de artar, çünkü \(L_n\) hızla büyür. Ancak orijinal Project Euler girdisi olan \(n=20\) için hesap son derece küçüktür ve standart tam sayı tiplerine rahatça sığar.
Hay que encontrar el menor entero positivo divisible por todos los números entre \(1\) y \(n\). En la versión original de Project Euler se toma \(n=20\), así que el objetivo es el menor número que sea múltiplo de todo el intervalo \([1,20]\).
No hace falta probar candidatos uno por uno. La respuesta es un objeto aritmético perfectamente definido:
$$L_n=\operatorname{lcm}(1,2,\ldots,n).$$
Una vez que la pregunta se expresa como un mcm, la estructura de la solución queda casi resuelta. Solo hay que identificar qué potencias primas son obligatorias y por qué una acumulación iterativa mediante mcm produce exactamente el mismo valor.
Cualquier respuesta válida debe ser divisible por cada \(k\) con \(1 \le k \le n\). Por tanto, debe ser un múltiplo común de todos esos números. El mínimo común múltiplo es, por definición, el menor entero con esa propiedad. Luego
$$\boxed{L_n=\operatorname{lcm}(1,2,\ldots,n).}$$
Si un número es divisible por todo el rango, entonces es un múltiplo común y debe ser múltiplo de \(L_n\). A la vez, \(L_n\) ya es divisible por cada miembro del rango. Con eso la minimalidad queda demostrada.
Por el Teorema Fundamental de la Aritmética, cada entero positivo tiene una factorización prima única. Por eso el mcm puede determinarse primo por primo. Para cada primo \(p \le n\), basta conservar el mayor exponente que aparezca en algún número entre \(1\) y \(n\).
Definimos
$$e_p=\max\{e \ge 0 : p^e \le n\}.$$
Entonces el exponente de \(p\) dentro de \(L_n\) es exactamente \(e_p\), y por tanto
$$L_n=\prod_{p \le n} p^{e_p},$$
donde el producto se toma solo sobre primos.
Esto explica por qué muchos compuestos no añaden nada nuevo. Solo empaquetan potencias primas que ya habían aparecido antes. Para \(n=20\), las potencias decisivas son
$$2^4,\quad 3^2,\quad 5,\quad 7,\quad 11,\quad 13,\quad 17,\quad 19.$$
Todo lo demás en \(1,\ldots,20\) queda cubierto por esos factores.
El código no enumera primos de forma explícita. Construye el mismo valor paso a paso. Sea
$$A_1=1,\qquad A_k=\operatorname{lcm}(A_{k-1},k)\quad (k\ge 2).$$
El invariante central es
$$A_k=\operatorname{lcm}(1,2,\ldots,k).$$
La prueba es una inducción inmediata. Si \(A_{k-1}\) ya es el mínimo común múltiplo de \(1,\ldots,k-1\), entonces cualquier entero divisible por \(1,\ldots,k\) debe ser divisible tanto por \(A_{k-1}\) como por \(k\). El menor de esos enteros es precisamente \(\operatorname{lcm}(A_{k-1},k)\). Cuando el bucle termina en \(k=n\), el acumulador coincide con \(L_n\).
Cada iteración añade solo la parte de \(k\) que todavía falta, es decir, la potencia prima nueva o más alta que aún no estaba representada. Si \(k\) no mejora ningún exponente, el acumulador no cambia.
Cada actualización se calcula con la identidad clásica
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$$
El mcd mide el solapamiento entre las factorizaciones primas de \(a\) y \(b\), así que dividir por él elimina la parte duplicada antes de multiplicar. El mcd se obtiene mediante el algoritmo de Euclides:
$$\gcd(a,b)=\gcd(b,a\bmod b),\qquad \gcd(a,0)=a.$$
Así, toda la solución se apoya en una cadena muy corta de ideas: la respuesta es un mcm, un mcm binario puede expresarse con un mcd, y el mcd se calcula de forma eficiente.
La descripción por potencias primas produce
$$L_{10}=2^3\cdot 3^2\cdot 5\cdot 7=2520,$$
porque las mayores potencias que no superan \(10\) son \(8,9,5\) y \(7\).
La construcción iterativa llega al mismo resultado mediante la sucesión
$$1\to 2\to 6\to 12\to 60\to 60\to 420\to 840\to 2520\to 2520.$$
Los valores repetidos son instructivos. Al incorporar \(6\), el acumulador no cambia porque \(2\) y \(3\) ya estaban completos; al incorporar \(10\), tampoco cambia porque \(2\cdot 5\) ya había quedado cubierto. Ese es exactamente el comportamiento que aprovecha el algoritmo.
Las implementaciones en C++, Python y Java mantienen un único acumulador, lo inicializan en \(1\) y recorren los enteros desde \(2\) hasta \(n\). Después de procesar \(k\), el acumulador coincide con el mcm del prefijo \(1,\ldots,k\). Ese invariante resume todo el algoritmo.
La forma concreta de escribir el paso binario de mcm cambia un poco según el lenguaje, pero la matemática es idéntica. La versión en C++ delega el cálculo del mcm a la biblioteca estándar. La versión en Python construye el mcm a partir de un mcd de biblioteca. La versión en Java escribe explícitamente el bucle de Euclides y divide por el mcd antes de multiplicar, para mantener más pequeño el producto intermedio. Las tres incluyen la comprobación \(n=10 \mapsto 2520\). El programa en C++ también puede recibir otro valor positivo de \(n\); las entradas principales de Python y Java imprimen directamente el caso estándar \(n=20\).
Hay \(n-1\) iteraciones. En el modelo habitual de pasos aritméticos, cada una realiza un cálculo de mcd, y el algoritmo de Euclides necesita \(O(\log k)\) pasos de resto cuando se combina con \(k\). Sumando desde \(k=2\) hasta \(n\), el trabajo total es \(O(n\log n)\).
La memoria adicional es \(O(1)\): aparte del contador del bucle, solo se guarda el acumulador. Si se analizara el problema para valores enormes de \(n\) con complejidad de bits completa, el coste de la aritmética crecería porque \(L_n\) también crece muy deprisa. Para el caso original \(n=20\), sin embargo, el cálculo es diminuto y cabe de sobra en tipos enteros estándar.
这道题要求找出最小的正整数，使它能够被 \(1\) 到 \(n\) 的每一个整数整除。原始的 Project Euler 版本取 \(n=20\)，也就是要求出区间 \([1,20]\) 全部整数的最小公倍数。
因此这不是一个靠枚举候选答案来试除的问题。答案本身就是一个明确的数论对象：
$$L_n=\operatorname{lcm}(1,2,\ldots,n).$$
一旦把题目改写成“求整个区间的最小公倍数”，核心结构就完全清晰了。接下来只需要回答两个问题：哪些素数幂必须出现，以及为什么代码里的逐步累积过程恰好构造出这个数。
任何合法答案都必须被所有 \(1 \le k \le n\) 的整数整除，所以它一定是这些数的一个公倍数。而最小公倍数按定义就是满足这一条件的最小正整数，因此
$$\boxed{L_n=\operatorname{lcm}(1,2,\ldots,n).}$$
如果某个整数能同时被整个区间整除，那么它必然是 \(L_n\) 的倍数；反过来，\(L_n\) 自己已经能被区间中的每个数整除，所以它正是所求的最小值。
算术基本定理告诉我们，每个正整数都可以唯一地分解为素数幂的乘积。因此最小公倍数也可以按素数逐个确定。对每个素数 \(p \le n\)，我们只需要保留在 \(1\) 到 \(n\) 中出现过的最大指数。
定义
$$e_p=\max\{e \ge 0 : p^e \le n\}.$$
那么 \(p\) 在 \(L_n\) 中的指数正好就是 \(e_p\)，于是
$$L_n=\prod_{p \le n} p^{e_p},$$
其中乘积只对素数进行。
这个公式解释了为什么很多合数其实不会带来新的信息。它们只是把已经出现过的素数幂重新组合了一次。以 \(n=20\) 为例，真正决定结果的只有
$$2^4,\quad 3^2,\quad 5,\quad 7,\quad 11,\quad 13,\quad 17,\quad 19.$$
\(1\) 到 \(20\) 中的其他数字都已经被这些素数幂覆盖了。
实现并没有显式枚举素数，而是把同一个答案逐步构造出来。设
$$A_1=1,\qquad A_k=\operatorname{lcm}(A_{k-1},k)\quad (k\ge 2).$$
这里最关键的不变量是
$$A_k=\operatorname{lcm}(1,2,\ldots,k).$$
证明只需要一个直接的归纳。假设 \(A_{k-1}\) 已经是 \(1,\ldots,k-1\) 的最小公倍数，那么任何能同时整除 \(1,\ldots,k\) 的整数，必然同时整除 \(A_{k-1}\) 和 \(k\)。这样的最小整数正是 \(\operatorname{lcm}(A_{k-1},k)\)。因此当循环走到 \(k=n\) 时，累加器中保存的就是 \(L_n\)。
从这个角度看，每一步只会补上 \(k\) 中“之前还没有”的那部分素数幂。如果 \(k\) 没有为任何素数提供更高的指数，累加器就不会变化。
每一步更新都使用经典恒等式
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$$
\(\gcd(a,b)\) 正好表示 \(a\) 和 \(b\) 的素因子重叠部分，所以先除以 gcd，就能把重复计算的那部分去掉，再与另一边相乘。gcd 本身则由欧几里得算法得到：
$$\gcd(a,b)=\gcd(b,a\bmod b),\qquad \gcd(a,0)=a.$$
于是整道题就被压缩成一条非常短的数学链条：答案是一个最小公倍数，二元最小公倍数可以用 gcd 表示，而 gcd 又能高效计算。
用素数幂的观点，可以直接写出
$$L_{10}=2^3\cdot 3^2\cdot 5\cdot 7=2520,$$
因为不超过 \(10\) 的最大相关幂分别是 \(8,9,5,7\)。
而递推式会经过同样清晰的一串状态：
$$1\to 2\to 6\to 12\to 60\to 60\to 420\to 840\to 2520\to 2520.$$
其中重复值特别能说明问题。处理 \(6\) 时，累加器不变，因为 \(2\) 和 \(3\) 早已包含在前面的结果中；处理 \(10\) 时也不变，因为 \(2\cdot 5\) 已经由更早的步骤提供了。代码正是依靠这种“只在必要时增长”的性质来工作的。
C++、Python 和 Java 三个实现都只维护一个累加器，把它初始化为 \(1\)，然后从 \(2\) 一直迭代到 \(n\)。在处理完第 \(k\) 个整数后，累加器就等于前缀 \(1,\ldots,k\) 的最小公倍数。整个算法实际上就是维护这个不变量。
不同语言之间的差别只在于“如何写出二元 lcm 这一步”。C++ 版本把该运算交给标准库。Python 版本通过标准库 gcd 来构造 lcm。Java 版本显式写出欧几里得循环，并且先除以 gcd 再乘，以减小中间乘积。三个实现都包含 \(n=10 \mapsto 2520\) 这一校验。C++ 的入口还可以接收其他正整数 \(n\)；Python 和 Java 直接运行时则输出标准的 \(n=20\) 情况。
循环总共执行 \(n-1\) 次。在通常的算术步模型下，每次迭代包含一次 gcd 计算，而欧几里得算法在与 \(k\) 配对时需要 \(O(\log k)\) 次取余步骤。把 \(k=2\) 到 \(n\) 全部加起来，总工作量是 \(O(n\log n)\)。
额外空间是 \(O(1)\)，因为除了循环变量之外，只保存当前累加器。如果研究非常大的 \(n\)，并且严格按位复杂度计算，那么整数本身越来越大，算术成本也会随之上升，因为 \(L_n\) 增长很快。不过对原题的 \(n=20\) 来说，数值规模很小，用普通整数类型就足够了。
Нужно найти наименьшее положительное целое число, которое делится на каждое число от \(1\) до \(n\). В исходной задаче Project Euler берётся \(n=20\), то есть требуется минимальное общее кратное для всего диапазона \([1,20]\).
Это не перебор кандидатов, а вычисление одного вполне определённого арифметического объекта:
$$L_n=\operatorname{lcm}(1,2,\ldots,n).$$
После такой переформулировки решение становится прозрачным. Нужно понять, какие степени простых чисел обязательно входят в ответ, и почему итеративное накопление через НОК строит тот же самый результат.
Любой допустимый ответ обязан делиться на каждое \(k\) при \(1 \le k \le n\). Значит, это общее кратное всех чисел диапазона. Наименьшее общее кратное по определению и есть наименьшее число с таким свойством. Следовательно,
$$\boxed{L_n=\operatorname{lcm}(1,2,\ldots,n).}$$
Если число делится на весь диапазон, то оно является общим кратным и потому обязано делиться на \(L_n\). Обратно, само \(L_n\) уже делится на каждое число от \(1\) до \(n\). Это и даёт минимальность.
Основная теорема арифметики утверждает, что разложение на простые множители единственно. Поэтому НОК можно определить по каждому простому числу отдельно. Для каждого простого \(p \le n\) нам нужен только наибольший показатель, который встречается в каком-либо числе от \(1\) до \(n\).
Положим
$$e_p=\max\{e \ge 0 : p^e \le n\}.$$
Тогда показатель простого \(p\) в \(L_n\) равен ровно \(e_p\), а значит
$$L_n=\prod_{p \le n} p^{e_p},$$
где произведение берётся только по простым числам.
Это сразу показывает, почему многие составные числа ничего нового не добавляют. Они лишь комбинируют простые степени, уже появившиеся раньше. Для случая \(n=20\) решающими являются
$$2^4,\quad 3^2,\quad 5,\quad 7,\quad 11,\quad 13,\quad 17,\quad 19.$$
Все остальные числа из \(1,\ldots,20\) уже покрываются этими множителями.
Реализации не перечисляют простые числа явно. Вместо этого они пошагово строят тот же ответ. Введём последовательность
$$A_1=1,\qquad A_k=\operatorname{lcm}(A_{k-1},k)\quad (k\ge 2).$$
Главный инвариант таков:
$$A_k=\operatorname{lcm}(1,2,\ldots,k).$$
Доказательство представляет собой прямую индукцию. Пусть \(A_{k-1}\) уже равно НОК чисел \(1,\ldots,k-1\). Тогда любое число, делящееся на \(1,\ldots,k\), обязано делиться и на \(A_{k-1}\), и на \(k\). Наименьшее такое число равно \(\operatorname{lcm}(A_{k-1},k)\). Когда цикл доходит до \(k=n\), в аккумуляторе оказывается именно \(L_n\).
Иными словами, каждый шаг добавляет только ту часть разложения числа \(k\), которой ещё не хватало. Если \(k\) не приносит более высокой степени ни для одного простого, значение не меняется.
Каждое обновление использует классическое тождество
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$$
НОД описывает пересечение простых множителей у \(a\) и \(b\), поэтому деление на него убирает дублированную часть перед умножением. Сам НОД находится алгоритмом Евклида:
$$\gcd(a,b)=\gcd(b,a\bmod b),\qquad \gcd(a,0)=a.$$
Вся математика решения укладывается в короткую цепочку: искомое число является НОК, бинарный НОК выражается через НОД, а НОД вычисляется очень быстро.
Через простые степени получаем
$$L_{10}=2^3\cdot 3^2\cdot 5\cdot 7=2520,$$
поскольку наибольшие степени, не превосходящие \(10\), равны \(8,9,5\) и \(7\).
Итеративное построение приходит к тому же числу по цепочке
$$1\to 2\to 6\to 12\to 60\to 60\to 420\to 840\to 2520\to 2520.$$
Повторяющиеся значения здесь особенно полезны для понимания. При добавлении \(6\) аккумулятор не растёт, потому что множители \(2\) и \(3\) уже полностью присутствуют; при добавлении \(10\) он тоже не растёт, так как \(2\cdot 5\) уже покрыто более ранними шагами. Именно этим свойством пользуется программа.
Во всех трёх реализациях, на C++, Python и Java, поддерживается один аккумулятор, который стартует с \(1\), а затем последовательно обновляется для всех \(k\) от \(2\) до \(n\). После обработки очередного \(k\) аккумулятор равен НОК префикса \(1,\ldots,k\). Этот инвариант и есть весь алгоритм.
Различается только запись бинарного шага НОК. Реализация на C++ использует стандартную библиотеку. Реализация на Python строит НОК через библиотечный НОД. Реализация на Java явно пишет цикл Евклида и сначала делит на НОД, а уже потом умножает, чтобы промежуточное произведение было меньше. Во всех версиях есть проверка \(n=10 \mapsto 2520\). Точка входа C++ может принимать и другой положительный \(n\); Python и Java при прямом запуске печатают стандартный случай \(n=20\).
Выполняется \(n-1\) итераций цикла. В стандартной модели арифметических операций каждая итерация содержит один расчёт НОД, а алгоритм Евклида требует \(O(\log k)\) шагов взятия остатка, когда второй аргумент равен \(k\). Суммарно по всем \(k\) от \(2\) до \(n\) получаем \(O(n\log n)\) арифметической работы.
Дополнительная память равна \(O(1)\): кроме счётчика и текущего аккумулятора, хранить ничего не нужно. Если рассматривать очень большие \(n\) с точной битовой сложностью, стоимость арифметики возрастает, поскольку сам \(L_n\) быстро растёт. Для исходного входа \(n=20\) вычисление, однако, совсем мало и легко помещается в стандартные целочисленные типы.
المطلوب هو إيجاد أصغر عدد صحيح موجب يقبل القسمة على كل عدد من \(1\) إلى \(n\). في الصيغة الأصلية من Project Euler يكون \(n=20\)، أي إننا نبحث عن أصغر عدد يكون مضاعفاً لكل عناصر الفترة \([1,20]\).
إذن المسألة ليست تجربة أعداد كثيرة حتى ننجح، بل هي حساب كائن عددي محدد تماماً:
$$L_n=\operatorname{lcm}(1,2,\ldots,n).$$
عندما نعيد صياغة المطلوب على أنه مضاعف مشترك أصغر لفترة كاملة، تصبح بنية الحل مباشرة جداً. يبقى فقط أن نحدد أي قوى أولية يجب أن تظهر في الناتج، ولماذا يبني التحديث التتابعي في التنفيذ العدد نفسه بالضبط.
أي جواب صحيح يجب أن يكون قابلاً للقسمة على كل \(k\) حيث \(1 \le k \le n\). هذا يعني أنه مضاعف مشترك لجميع تلك الأعداد. وبحسب التعريف، فإن المضاعف المشترك الأصغر هو أصغر عدد يحقق هذه الخاصية. لذلك
$$\boxed{L_n=\operatorname{lcm}(1,2,\ldots,n).}$$
إذا كان عدد ما يقبل القسمة على كامل الفترة، فهو مضاعف مشترك، وبالتالي لا بد أن يكون من مضاعفات \(L_n\). وفي الاتجاه الآخر فإن \(L_n\) نفسه يقبل القسمة على كل عنصر في القائمة، ومن هنا تأتي الأصغرية مباشرة.
تنص المبرهنة الأساسية في الحساب على أن كل عدد صحيح موجب يملك تحليلاً وحيداً إلى عوامل أولية. لذلك يمكن تحديد المضاعف المشترك الأصغر أولياً بعدد أولي. لكل أولي \(p \le n\) نحتاج فقط إلى أكبر أس يظهر في أحد الأعداد بين \(1\) و\(n\).
لنعرّف
$$e_p=\max\{e \ge 0 : p^e \le n\}.$$
عندئذ يكون أسّ \(p\) داخل \(L_n\) مساوياً تماماً لـ \(e_p\)، وبالتالي
$$L_n=\prod_{p \le n} p^{e_p},$$
حيث يؤخذ حاصل الضرب على الأعداد الأولية فقط.
وهذا يوضح لماذا لا تضيف كثير من الأعداد المركبة أي معلومة جديدة. فهي تجمع فقط قوى أولية ظهرت من قبل. في الحالة \(n=20\) تكون القوى الحاسمة هي
$$2^4,\quad 3^2,\quad 5,\quad 7,\quad 11,\quad 13,\quad 17,\quad 19.$$
أما بقية الأعداد في \(1,\ldots,20\) فهي مغطاة بهذه العوامل بالفعل.
التنفيذ لا يسرد الأعداد الأولية صراحة. بدلاً من ذلك يبني القيمة نفسها خطوة بعد خطوة. لنكتب
$$A_1=1,\qquad A_k=\operatorname{lcm}(A_{k-1},k)\quad (k\ge 2).$$
الثابت الأساسي هو
$$A_k=\operatorname{lcm}(1,2,\ldots,k).$$
والبرهان هنا استقراء مباشر. إذا افترضنا أن \(A_{k-1}\) هو بالفعل المضاعف المشترك الأصغر للأعداد \(1,\ldots,k-1\)، فإن أي عدد يقبل القسمة على \(1,\ldots,k\) لا بد أن يقبل القسمة على كل من \(A_{k-1}\) و\(k\). وأصغر عدد يحقق ذلك هو \(\operatorname{lcm}(A_{k-1},k)\). وعندما تصل الحلقة إلى \(k=n\)، يصبح ما في المراكم هو \(L_n\) نفسه.
هذا يعني أن كل خطوة تضيف فقط الجزء المفقود من تحليل \(k\) إلى عوامل أولية. فإذا لم يقدّم \(k\) أساً أكبر لأي أولي، فلن تتغير قيمة المراكم.
كل تحديث يعتمد على الهوية الكلاسيكية
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$$
فالقاسم المشترك الأكبر يقيس الجزء المتداخل بين التحليلين الأوليين لـ \(a\) و\(b\)، والقسمة عليه تزيل الجزء المكرر قبل الضرب. أما \(gcd\) نفسه فيُحسب بخوارزمية إقليدس:
$$\gcd(a,b)=\gcd(b,a\bmod b),\qquad \gcd(a,0)=a.$$
وهكذا تُختزل الفكرة كلها إلى سلسلة قصيرة جداً: الجواب هو مضاعف مشترك أصغر، ويمكن حساب المضاعف المشترك الأصغر لعددين بواسطة \(gcd\)، و\(gcd\) سريع الحساب.
من منظور القوى الأولية نحصل على
$$L_{10}=2^3\cdot 3^2\cdot 5\cdot 7=2520,$$
لأن أكبر القوى التي لا تتجاوز \(10\) هي \(8\) و\(9\) و\(5\) و\(7\).
أما البناء التتابعي فيصل إلى النتيجة نفسها عبر السلسلة
$$1\to 2\to 6\to 12\to 60\to 60\to 420\to 840\to 2520\to 2520.$$
والقيم المتكررة هنا مهمة جداً للفهم. عند إدخال \(6\) لا تتغير القيمة، لأن العاملين \(2\) و\(3\) موجودان بالكامل من قبل. وعند إدخال \(10\) لا يحدث تغير أيضاً، لأن \(2\cdot 5\) أصبح مغطى في خطوات سابقة. هذا بالضبط هو السلوك الذي تستغله الحلقة.
تنفيذات C++ وPython وJava كلها تحتفظ بمراكم واحد يبدأ من \(1\)، ثم تمر على القيم من \(2\) حتى \(n\). بعد معالجة \(k\)، يكون المراكم مساوياً للمضاعف المشترك الأصغر للمقدمة \(1,\ldots,k\). وهذا الثابت هو قلب الخوارزمية كله.
الاختلاف بين اللغات يقتصر على طريقة كتابة خطوة المضاعف المشترك الأصغر الثنائية. نسخة C++ تعتمد على المكتبة القياسية. نسخة Python تبني \(lcm\) انطلاقاً من \(gcd\) في المكتبة. أما نسخة Java فتكتب حلقة إقليدس بشكل صريح وتقسم على \(gcd\) قبل الضرب، حتى يبقى الناتج الوسيط أصغر. جميع النسخ تتضمن نقطة التحقق \(n=10 \mapsto 2520\). كما أن نقطة الدخول في C++ تستطيع التعامل مع قيمة موجبة أخرى لـ \(n\)، بينما تطبع نسختا Python وJava الحالة القياسية \(n=20\) عند التشغيل المباشر.
يوجد \(n-1\) تكراراً في الحلقة. في نموذج الخطوات الحسابية المعتاد، يحتوي كل تكرار على حساب واحد لـ \(gcd\)، وتحتاج خوارزمية إقليدس إلى \(O(\log k)\) خطوات باقٍ عندما يكون أحد العددين هو \(k\). وبجمع ذلك من \(k=2\) إلى \(n\)، نحصل على كلفة كلية مقدارها \(O(n\log n)\).
أما الذاكرة الإضافية فهي \(O(1)\)، لأن الخوارزمية لا تحتفظ إلا بالمراكم الحالي وبعض المتغيرات الصغيرة. وإذا دُرست المسألة لقيم ضخمة جداً من \(n\) مع احتساب تعقيد البتات، فإن كلفة الحساب على الأعداد الصحيحة تكبر أيضاً لأن \(L_n\) نفسه ينمو سريعاً. لكن في مدخل Project Euler الأصلي \(n=20\) تكون العملية صغيرة جداً وتكفيها الأنواع الصحيحة القياسية بسهولة.