The target quantity is the sum of the prime factors of the binomial coefficient \(\binom{20{,}000{,}000}{15{,}000{,}000}\), where each prime is counted with multiplicity. If a positive integer \(N\) has prime factorisation
$$N=\prod_{p \text{ prime}} p^{e_p},$$
then the required weighted sum is
$$S(N)=\sum_{p \text{ prime}} p\,e_p.$$
So for this problem we must compute
$$S\!\left(\binom{20{,}000{,}000}{15{,}000{,}000}\right)=\sum_{p \le 20{,}000{,}000} p\,v_p\!\left(\binom{20{,}000{,}000}{15{,}000{,}000}\right),$$
where \(v_p(x)\) is the exponent of the prime \(p\) in \(x\). Directly expanding or factoring the binomial coefficient is impossible in practice, so the solution works entirely with prime exponents.
The whole method rests on one idea: instead of building the enormous integer \(\binom{n}{k}\), determine how many times each prime occurs in it and add the weighted contributions \(p \cdot v_p\).
Write
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$
Prime exponents are additive across multiplication and subtractive across division, so for every prime \(p\),
$$v_p\!\left(\binom{n}{k}\right)=v_p(n!) - v_p(k!) - v_p((n-k)!).$$
This is the exact cancellation pattern used by the implementations. It turns the problem into three factorial-valuation queries per prime. The complement \(n-k\) matters naturally because the denominator contains both \(k!\) and \((n-k)!\), and the identity \(\binom{n}{k}=\binom{n}{n-k}\) explains why the two smaller factorials play symmetric roles.
To evaluate \(v_p(m!)\), the code uses Legendre's formula:
$$v_p(m!)=\sum_{j \ge 1}\left\lfloor \frac{m}{p^j}\right\rfloor.$$
Each term has a clean meaning. The term \(\left\lfloor m/p \right\rfloor\) counts the multiples of \(p\) in \(1,2,\dots,m\); the term \(\left\lfloor m/p^2 \right\rfloor\) counts the extra copies contributed by multiples of \(p^2\); the next term does the same for \(p^3\), and so on. The sum is finite because once \(p^j > m\), every later floor is zero.
Computationally, this means we can start with \(x=m\), repeatedly divide by \(p\), and add the quotients:
$$v_p(m!)=\left\lfloor \frac{m}{p}\right\rfloor+\left\lfloor \frac{m}{p^2}\right\rfloor+\left\lfloor \frac{m}{p^3}\right\rfloor+\cdots.$$
Substituting Legendre's formula into the binomial identity gives
$$v_p\!\left(\binom{n}{k}\right)=\sum_{j \ge 1}\left(\left\lfloor \frac{n}{p^j}\right\rfloor-\left\lfloor \frac{k}{p^j}\right\rfloor-\left\lfloor \frac{n-k}{p^j}\right\rfloor\right).$$
Therefore
$$S\!\left(\binom{n}{k}\right)=\sum_{p \le n} p \sum_{j \ge 1}\left(\left\lfloor \frac{n}{p^j}\right\rfloor-\left\lfloor \frac{k}{p^j}\right\rfloor-\left\lfloor \frac{n-k}{p^j}\right\rfloor\right).$$
Only primes up to \(n\) can contribute, because no prime larger than \(n\) appears in \(n!\). That is why the first phase of the algorithm is simply to list all primes \(p \le n\) with a sieve.
Once those primes are known, every contribution is independent. For each prime \(p\), compute its exponent in \(n!\), subtract the two denominator exponents, multiply by \(p\), and add the result to the total.
The small checkpoint used by the implementations is
$$\binom{10}{3}=120=2^3 \cdot 3 \cdot 5,$$
so the weighted prime-factor sum should be
$$S\!\left(\binom{10}{3}\right)=2 \cdot 3 + 3 \cdot 1 + 5 \cdot 1 = 14.$$
Legendre's formula reproduces that value directly. For \(p=2\),
$$v_2(10!)=5+2+1=8,\qquad v_2(3!)=1,\qquad v_2(7!)=3+1=4,$$
hence
$$v_2\!\left(\binom{10}{3}\right)=8-1-4=3.$$
For \(p=3\),
$$v_3(10!)=3+1=4,\qquad v_3(3!)=1,\qquad v_3(7!)=2,$$
so
$$v_3\!\left(\binom{10}{3}\right)=4-1-2=1.$$
For \(p=5\),
$$v_5(10!)=2,\qquad v_5(3!)=0,\qquad v_5(7!)=1,$$
thus
$$v_5\!\left(\binom{10}{3}\right)=2-0-1=1.$$
And for \(p=7\), the cancellation is complete:
$$v_7(10!)=1,\qquad v_7(3!)=0,\qquad v_7(7!)=1,\qquad v_7\!\left(\binom{10}{3}\right)=0.$$
This example shows exactly why the method is reliable: the binomial coefficient never has to be formed explicitly, yet every prime exponent is recovered correctly.
The C++, Python, and Java implementations all follow the same three-stage computation.
First, the implementation runs a sieve of Eratosthenes up to \(n\). A byte or boolean array marks which integers are still prime, composite multiples are crossed out, and the surviving indices are collected into a prime list. Because the target instance uses \(n=20{,}000{,}000\), this precomputation is large but still straightforward.
For each prime \(p\), the implementation computes \(v_p(m!)\) by repeatedly dividing \(m\) by \(p\) and accumulating the quotients. The same routine is applied to \(n\), to \(k\), and to the complementary value \(n-k\). This is a direct implementation of Legendre's formula and avoids any factorisation of individual integers.
After the three valuations are known, the exponent of \(p\) in the binomial coefficient is obtained by subtraction:
$$v_p\!\left(\binom{n}{k}\right)=v_p(n!) - v_p(k!) - v_p((n-k)!).$$
The implementation then adds
$$p \cdot v_p\!\left(\binom{n}{k}\right)$$
to a running integer total. The C++ implementation also includes a small checkpoint for \(\binom{10}{3}\), verifying that the method returns 14 before the main instance is processed. The Python and Java versions perform the same mathematics with the same default parameters.
The sieve up to \(n\) costs \(O(n \log \log n)\) time and \(O(n)\) memory. That is the dominant memory expense, because the implementation stores one primality mark per integer up to \(n\).
After the sieve, each prime \(p\) requires \(O(\log_p n)\) divisions to evaluate Legendre's sum, so the valuation phase costs
$$O\!\left(\sum_{p \le n}\log_p n\right).$$
Combining both parts gives total running time
$$O\!\left(n \log \log n + \sum_{p \le n}\log_p n\right),$$
with memory usage \(O(n)\). For the actual problem size, the algorithm is efficient because it never manipulates the gigantic binomial coefficient itself; it only works with prime counts.
Gesucht ist die Summe der Primfaktoren des Binomialkoeffizienten \(\binom{20{,}000{,}000}{15{,}000{,}000}\), wobei jede Primzahl mit ihrer Vielfachheit gezählt wird. Hat eine positive ganze Zahl \(N\) die Primfaktorzerlegung
$$N=\prod_{p \text{ prim}} p^{e_p},$$
dann ist die verlangte gewichtete Summe
$$S(N)=\sum_{p \text{ prim}} p\,e_p.$$
Für diese Aufgabe muss also
$$S\!\left(\binom{20{,}000{,}000}{15{,}000{,}000}\right)=\sum_{p \le 20{,}000{,}000} p\,v_p\!\left(\binom{20{,}000{,}000}{15{,}000{,}000}\right)$$
berechnet werden, wobei \(v_p(x)\) den Exponenten von \(p\) in \(x\) bezeichnet. Das explizite Ausmultiplizieren oder Faktorisieren des Binomialkoeffizienten ist praktisch unmöglich; deshalb arbeitet die Lösung ausschließlich mit Primexponenten.
Der gesamte Lösungsweg folgt einer einzigen Leitidee: Die riesige Zahl \(\binom{n}{k}\) wird nie aufgebaut. Stattdessen bestimmt man für jede Primzahl, wie oft sie vorkommt, und addiert die gewichteten Beiträge \(p \cdot v_p\).
Es gilt
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$
Primexponenten addieren sich bei Produkten und subtrahieren sich bei Quotienten. Daher folgt für jede Primzahl \(p\),
$$v_p\!\left(\binom{n}{k}\right)=v_p(n!) - v_p(k!) - v_p((n-k)!).$$
Genau dieses Kürzungsmuster verwenden die Implementierungen. Damit reduziert sich das Problem auf drei Auswertungen von Fakultätsbewertungen pro Primzahl. Der Term \(n-k\) ist unvermeidlich, weil im Nenner sowohl \(k!\) als auch \((n-k)!\) vorkommen; zugleich erklärt die Symmetrie \(\binom{n}{k}=\binom{n}{n-k}\), warum diese beiden Faktoren gleichberechtigt sind.
Zur Berechnung von \(v_p(m!)\) wird die Legendre-Formel verwendet:
$$v_p(m!)=\sum_{j \ge 1}\left\lfloor \frac{m}{p^j}\right\rfloor.$$
Jeder Summand hat eine klare Bedeutung. \(\left\lfloor m/p \right\rfloor\) zählt die Vielfachen von \(p\) unter \(1,\dots,m\), \(\left\lfloor m/p^2 \right\rfloor\) zählt die zusätzlichen Faktoren aus Vielfachen von \(p^2\), und so weiter. Die Summe endet effektiv, sobald \(p^j > m\), weil dann alle weiteren Abrundungen null sind.
Rechnerisch heißt das: Man startet mit \(x=m\), teilt wiederholt durch \(p\) und addiert die Quotienten:
$$v_p(m!)=\left\lfloor \frac{m}{p}\right\rfloor+\left\lfloor \frac{m}{p^2}\right\rfloor+\left\lfloor \frac{m}{p^3}\right\rfloor+\cdots.$$
Setzt man die Legendre-Formel in die Binomialidentität ein, erhält man
$$v_p\!\left(\binom{n}{k}\right)=\sum_{j \ge 1}\left(\left\lfloor \frac{n}{p^j}\right\rfloor-\left\lfloor \frac{k}{p^j}\right\rfloor-\left\lfloor \frac{n-k}{p^j}\right\rfloor\right).$$
Damit folgt
$$S\!\left(\binom{n}{k}\right)=\sum_{p \le n} p \sum_{j \ge 1}\left(\left\lfloor \frac{n}{p^j}\right\rfloor-\left\lfloor \frac{k}{p^j}\right\rfloor-\left\lfloor \frac{n-k}{p^j}\right\rfloor\right).$$
Nur Primzahlen bis \(n\) können beitragen, denn keine größere Primzahl kann in \(n!\) auftreten. Deshalb besteht der erste Algorithmusschritt darin, mit einem Sieb alle Primzahlen \(p \le n\) zu erzeugen.
Sobald diese Primzahlen vorliegen, ist jeder Beitrag unabhängig: Für jede Primzahl \(p\) berechnet man den Exponenten in \(n!\), zieht die beiden Exponenten aus dem Nenner ab, multipliziert mit \(p\) und addiert alles auf.
Die kleine Kontrollrechnung der Implementierungen lautet
$$\binom{10}{3}=120=2^3 \cdot 3 \cdot 5,$$
also muss die gewichtete Primfaktorsumme
$$S\!\left(\binom{10}{3}\right)=2 \cdot 3 + 3 \cdot 1 + 5 \cdot 1 = 14$$
sein. Mit der Legendre-Formel erhält man diesen Wert direkt. Für \(p=2\) gilt
$$v_2(10!)=5+2+1=8,\qquad v_2(3!)=1,\qquad v_2(7!)=3+1=4,$$
also
$$v_2\!\left(\binom{10}{3}\right)=8-1-4=3.$$
Für \(p=3\) gilt
$$v_3(10!)=3+1=4,\qquad v_3(3!)=1,\qquad v_3(7!)=2,$$
daher
$$v_3\!\left(\binom{10}{3}\right)=4-1-2=1.$$
Für \(p=5\) ist
$$v_5(10!)=2,\qquad v_5(3!)=0,\qquad v_5(7!)=1,$$
und somit
$$v_5\!\left(\binom{10}{3}\right)=2-0-1=1.$$
Bei \(p=7\) hebt sich alles weg:
$$v_7(10!)=1,\qquad v_7(3!)=0,\qquad v_7(7!)=1,\qquad v_7\!\left(\binom{10}{3}\right)=0.$$
Dieses Beispiel zeigt genau, warum die Methode funktioniert: Der Binomialkoeffizient selbst muss nie gebildet werden, und dennoch wird jeder Primexponent korrekt rekonstruiert.
Die C++-, Python- und Java-Implementierungen folgen demselben dreistufigen Ablauf.
Zuerst führt die Implementierung ein Sieb des Eratosthenes bis \(n\) aus. Ein Byte- oder Bool-Array markiert mögliche Primzahlen, zusammengesetzte Vielfache werden gestrichen, und die verbleibenden Indizes werden als Primzahlliste gesammelt. Für den Zielwert \(n=20{,}000{,}000\) ist diese Vorberechnung groß, aber vollkommen geradlinig.
Für jede Primzahl \(p\) berechnet die Implementierung \(v_p(m!)\), indem \(m\) wiederholt durch \(p\) geteilt und jeder Quotient aufsummiert wird. Dieselbe Prozedur wird auf \(n\), auf \(k\) und auf den komplementären Wert \(n-k\) angewendet. Das ist eine direkte Umsetzung der Legendre-Formel und vermeidet jede Faktorisierung einzelner großer Zahlen.
Sobald die drei Bewertungen vorliegen, wird der Exponent von \(p\) im Binomialkoeffizienten durch Subtraktion bestimmt:
$$v_p\!\left(\binom{n}{k}\right)=v_p(n!) - v_p(k!) - v_p((n-k)!).$$
Anschließend addiert die Implementierung
$$p \cdot v_p\!\left(\binom{n}{k}\right)$$
zu einer laufenden Ganzzahlsumme. Die C++-Version enthält zusätzlich eine kleine Kontrollrechnung für \(\binom{10}{3}\), die vor dem Haupteinsatz den Wert 14 bestätigt. Die Python- und Java-Versionen führen dieselbe Mathematik mit denselben Standardparametern aus.
Das Sieb bis \(n\) benötigt \(O(n \log \log n)\) Zeit und \(O(n)\) Speicher. Das ist zugleich der dominante Speicheranteil, weil pro Zahl bis \(n\) genau eine Primalitätsmarkierung gehalten wird.
Danach braucht jede Primzahl \(p\) genau \(O(\log_p n)\) Divisionen für die Legendre-Summe, also kostet die Bewertungsphase insgesamt
$$O\!\left(\sum_{p \le n}\log_p n\right).$$
Insgesamt ergibt sich damit die Laufzeit
$$O\!\left(n \log \log n + \sum_{p \le n}\log_p n\right),$$
bei Speicherverbrauch \(O(n)\). Für die eigentliche Aufgabenstellung ist das effizient, weil die riesige Zahl \(\binom{20{,}000{,}000}{15{,}000{,}000}\) nie explizit konstruiert wird.
İstenen büyüklük, \(\binom{20{,}000{,}000}{15{,}000{,}000}\) binom katsayısının asal çarpanlarının, üsleriyle birlikte ağırlıklı toplamıdır. Bir pozitif tam sayının asal çarpanlarına ayrılışı
$$N=\prod_{p \text{ asal}} p^{e_p}$$
şeklindeyse, aranan toplam
$$S(N)=\sum_{p \text{ asal}} p\,e_p$$
olur. Dolayısıyla bu problemde hesaplanması gereken ifade
$$S\!\left(\binom{20{,}000{,}000}{15{,}000{,}000}\right)=\sum_{p \le 20{,}000{,}000} p\,v_p\!\left(\binom{20{,}000{,}000}{15{,}000{,}000}\right)$$
biçimindedir. Burada \(v_p(x)\), \(x\) içinde asal \(p\)'nin üssünü gösterir. Binom katsayısını açıkça üretip sonra asal çarpanlarına ayırmak pratik değildir; çözüm baştan sona yalnızca asal üsleriyle çalışır.
Tüm yöntem şu fikre dayanır: \(\binom{n}{k}\) gibi devasa bir sayıyı oluşturmaya çalışmak yerine, her asalın kaç kez geçtiğini bulup katkıları \(p \cdot v_p\) olarak toplarız.
Önce
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}$$
yazalım. Çarpımda asal üsleri toplanır, bölümde çıkarılır. Bu yüzden her asal \(p\) için
$$v_p\!\left(\binom{n}{k}\right)=v_p(n!) - v_p(k!) - v_p((n-k)!)$$
olur. Uygulamaların kullandığı temel özdeşlik tam olarak budur. Böylece her asal için üç tane faktöriyel değerlemesi hesaplamak yeterli hale gelir. \(n-k\) terimi doğal olarak ortaya çıkar; çünkü paydada hem \(k!\) hem de \((n-k)!\) vardır. Ayrıca \(\binom{n}{k}=\binom{n}{n-k}\) simetrisi, bu iki küçük faktöriyel bloğunun neden eşit önemde olduğunu açıklar.
\(v_p(m!)\) değerini bulmak için Legendre formülü kullanılır:
$$v_p(m!)=\sum_{j \ge 1}\left\lfloor \frac{m}{p^j}\right\rfloor.$$
Her terimin açık bir anlamı vardır. \(\left\lfloor m/p \right\rfloor\), \(1\) ile \(m\) arasındaki \(p\) katlarını sayar. \(\left\lfloor m/p^2 \right\rfloor\), \(p^2\) katlarından gelen ek \(p\) kopyalarını sayar. Sonraki terimler de aynı mantıkla \(p^3, p^4,\dots\) için devam eder. \(p^j > m\) olduğunda bütün ileriki terimler sıfır olduğu için toplam zaten sonludur.
Hesaplama açısından bu, \(x=m\) ile başlayıp \(x\)'i tekrar tekrar \(p\)'ye bölerek oluşan bölümleri toplamak anlamına gelir:
$$v_p(m!)=\left\lfloor \frac{m}{p}\right\rfloor+\left\lfloor \frac{m}{p^2}\right\rfloor+\left\lfloor \frac{m}{p^3}\right\rfloor+\cdots.$$
Legendre formülünü binom özdeşliğine yerleştirince
$$v_p\!\left(\binom{n}{k}\right)=\sum_{j \ge 1}\left(\left\lfloor \frac{n}{p^j}\right\rfloor-\left\lfloor \frac{k}{p^j}\right\rfloor-\left\lfloor \frac{n-k}{p^j}\right\rfloor\right)$$
elde edilir. O halde
$$S\!\left(\binom{n}{k}\right)=\sum_{p \le n} p \sum_{j \ge 1}\left(\left\lfloor \frac{n}{p^j}\right\rfloor-\left\lfloor \frac{k}{p^j}\right\rfloor-\left\lfloor \frac{n-k}{p^j}\right\rfloor\right)$$
olur. \(n\)'den büyük asalların katkısı yoktur; çünkü böyle bir asal \(n!\) içinde hiç görünemez. Bu nedenle algoritmanın ilk işi, bir elekle bütün \(p \le n\) asallarını üretmektir.
Asal listesi hazır olduktan sonra her katkı bağımsızdır: her asal için \(n!\), \(k!\) ve \((n-k)!\) içindeki üs hesaplanır, fark alınır, \(p\) ile çarpılır ve sonuca eklenir.
Uygulamaların kullandığı küçük doğrulama örneği
$$\binom{10}{3}=120=2^3 \cdot 3 \cdot 5$$
olduğundan, ağırlıklı toplamın
$$S\!\left(\binom{10}{3}\right)=2 \cdot 3 + 3 \cdot 1 + 5 \cdot 1 = 14$$
çıkması gerekir. Legendre formülü bunu doğrudan verir. \(p=2\) için
$$v_2(10!)=5+2+1=8,\qquad v_2(3!)=1,\qquad v_2(7!)=3+1=4,$$
dolayısıyla
$$v_2\!\left(\binom{10}{3}\right)=8-1-4=3.$$
\(p=3\) için
$$v_3(10!)=3+1=4,\qquad v_3(3!)=1,\qquad v_3(7!)=2,$$
ve buradan
$$v_3\!\left(\binom{10}{3}\right)=4-1-2=1$$
çıkar. \(p=5\) için
$$v_5(10!)=2,\qquad v_5(3!)=0,\qquad v_5(7!)=1,$$
yani
$$v_5\!\left(\binom{10}{3}\right)=2-0-1=1.$$
\(p=7\) için ise tam iptal vardır:
$$v_7(10!)=1,\qquad v_7(3!)=0,\qquad v_7(7!)=1,\qquad v_7\!\left(\binom{10}{3}\right)=0.$$
Bu örnek, yöntemin neden sağlam olduğunu net biçimde gösterir: binom katsayısı hiç üretilmeden, bütün asal üsleri doğru elde edilir.
C++, Python ve Java uygulamaları aynı üç aşamalı akışı izler.
Önce \(n\)'e kadar Eratosthenes eleği çalıştırılır. Bir byte ya da boolean dizisi aday asalları işaretler, bileşik sayıların katları elenir ve kalan indisler asal listesine toplanır. Hedef örnekte \(n=20{,}000{,}000\) olduğu için bu ön hazırlık ciddi boyuttadır, ama doğrudan ve standarttır.
Her asal \(p\) için uygulama, \(m\)'i tekrar tekrar \(p\)'ye bölüp oluşan bölümleri toplayarak \(v_p(m!)\) değerini hesaplar. Aynı yordam \(n\), \(k\) ve tamamlayıcı değer \(n-k\) için uygulanır. Bu, Legendre formülünün doğrudan kod karşılığıdır ve büyük sayıları tek tek çarpanlarına ayırmaya hiç gerek bırakmaz.
Üç değerleme hesaplandıktan sonra, binom katsayısındaki asal üssü çıkarma ile bulunur:
$$v_p\!\left(\binom{n}{k}\right)=v_p(n!) - v_p(k!) - v_p((n-k)!).$$
Ardından uygulama
$$p \cdot v_p\!\left(\binom{n}{k}\right)$$
ifadesini çalışan toplamın üzerine ekler. C++ sürümü ayrıca \(\binom{10}{3}\) için küçük bir kontrol adımı içerir ve ana örneğe geçmeden önce 14 sonucunu doğrular. Python ve Java sürümleri aynı matematiği aynı varsayılan parametrelerle uygular.
\(n\)'e kadar yapılan elek \(O(n \log \log n)\) zaman ve \(O(n)\) bellek kullanır. Belleğin baskın kısmı da budur; çünkü \(n\)'e kadar her tamsayı için tek bir asal işareti tutulur.
Bundan sonra her asal \(p\), Legendre toplamı için \(O(\log_p n)\) adet bölme gerektirir. Dolayısıyla değerleme aşamasının toplam maliyeti
$$O\!\left(\sum_{p \le n}\log_p n\right)$$
olur. İki kısmı birleştirince toplam çalışma süresi
$$O\!\left(n \log \log n + \sum_{p \le n}\log_p n\right)$$
ve bellek kullanımı \(O(n)\) çıkar. Gerçek problem boyutunda yöntem verimlidir; çünkü devasa \(\binom{20{,}000{,}000}{15{,}000{,}000}\) sayısını asla açık biçimde oluşturmaya çalışmaz.
La cantidad buscada es la suma de los factores primos del coeficiente binomial \(\binom{20{,}000{,}000}{15{,}000{,}000}\), contando cada primo con su multiplicidad. Si un entero positivo \(N\) tiene descomposición
$$N=\prod_{p \text{ primo}} p^{e_p},$$
entonces la suma ponderada pedida es
$$S(N)=\sum_{p \text{ primo}} p\,e_p.$$
Por tanto, en este problema hay que calcular
$$S\!\left(\binom{20{,}000{,}000}{15{,}000{,}000}\right)=\sum_{p \le 20{,}000{,}000} p\,v_p\!\left(\binom{20{,}000{,}000}{15{,}000{,}000}\right),$$
donde \(v_p(x)\) es el exponente del primo \(p\) en \(x\). Expandir o factorizar explícitamente ese coeficiente binomial es totalmente impracticable, así que la solución trabaja solo con exponentes primos.
La idea central es simple: en vez de construir el enorme número \(\binom{n}{k}\), calculamos cuántas veces aparece cada primo en él y sumamos las contribuciones ponderadas \(p \cdot v_p\).
Partimos de
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$
Los exponentes primos se suman en un producto y se restan en un cociente, así que para cada primo \(p\),
$$v_p\!\left(\binom{n}{k}\right)=v_p(n!) - v_p(k!) - v_p((n-k)!).$$
Ese es exactamente el patrón de cancelación usado por las implementaciones. El problema se reduce a tres consultas de valoración factorial por primo. El término \(n-k\) aparece de manera natural porque el denominador contiene tanto \(k!\) como \((n-k)!\); además, la simetría \(\binom{n}{k}=\binom{n}{n-k}\) deja claro por qué ambos papeles son equivalentes.
Para calcular \(v_p(m!)\), el código usa la fórmula de Legendre:
$$v_p(m!)=\sum_{j \ge 1}\left\lfloor \frac{m}{p^j}\right\rfloor.$$
Cada término tiene una interpretación directa. \(\left\lfloor m/p \right\rfloor\) cuenta los múltiplos de \(p\) entre \(1\) y \(m\); \(\left\lfloor m/p^2 \right\rfloor\) cuenta las copias adicionales que provienen de los múltiplos de \(p^2\); y así sucesivamente. La suma termina en la práctica cuando \(p^j > m\), porque a partir de ese momento todos los cocientes enteros valen cero.
Desde el punto de vista computacional, basta empezar con \(x=m\), dividir repetidamente por \(p\) y acumular los cocientes:
$$v_p(m!)=\left\lfloor \frac{m}{p}\right\rfloor+\left\lfloor \frac{m}{p^2}\right\rfloor+\left\lfloor \frac{m}{p^3}\right\rfloor+\cdots.$$
Sustituyendo Legendre en la identidad binomial obtenemos
$$v_p\!\left(\binom{n}{k}\right)=\sum_{j \ge 1}\left(\left\lfloor \frac{n}{p^j}\right\rfloor-\left\lfloor \frac{k}{p^j}\right\rfloor-\left\lfloor \frac{n-k}{p^j}\right\rfloor\right).$$
Por lo tanto,
$$S\!\left(\binom{n}{k}\right)=\sum_{p \le n} p \sum_{j \ge 1}\left(\left\lfloor \frac{n}{p^j}\right\rfloor-\left\lfloor \frac{k}{p^j}\right\rfloor-\left\lfloor \frac{n-k}{p^j}\right\rfloor\right).$$
Solo pueden contribuir primos menores o iguales que \(n\), porque ningún primo mayor que \(n\) aparece en \(n!\). Por eso la primera fase del algoritmo consiste en generar con una criba todos los primos \(p \le n\).
Una vez conocida esa lista, cada contribución es independiente: para cada primo \(p\), se calcula su exponente en \(n!\), se restan los dos exponentes del denominador, se multiplica por \(p\) y se suma al total.
La comprobación pequeña usada por las implementaciones es
$$\binom{10}{3}=120=2^3 \cdot 3 \cdot 5,$$
de modo que la suma ponderada debe ser
$$S\!\left(\binom{10}{3}\right)=2 \cdot 3 + 3 \cdot 1 + 5 \cdot 1 = 14.$$
La fórmula de Legendre reproduce ese valor sin formar el número 120 a partir de factoriales gigantes. Para \(p=2\),
$$v_2(10!)=5+2+1=8,\qquad v_2(3!)=1,\qquad v_2(7!)=3+1=4,$$
y por tanto
$$v_2\!\left(\binom{10}{3}\right)=8-1-4=3.$$
Para \(p=3\),
$$v_3(10!)=3+1=4,\qquad v_3(3!)=1,\qquad v_3(7!)=2,$$
así que
$$v_3\!\left(\binom{10}{3}\right)=4-1-2=1.$$
Para \(p=5\),
$$v_5(10!)=2,\qquad v_5(3!)=0,\qquad v_5(7!)=1,$$
luego
$$v_5\!\left(\binom{10}{3}\right)=2-0-1=1.$$
Y para \(p=7\), la cancelación es completa:
$$v_7(10!)=1,\qquad v_7(3!)=0,\qquad v_7(7!)=1,\qquad v_7\!\left(\binom{10}{3}\right)=0.$$
Este ejemplo muestra exactamente por qué el método funciona: nunca se construye el coeficiente binomial de forma explícita, pero sí se recupera cada exponente primo correcto.
Las implementaciones en C++, Python y Java siguen el mismo proceso de tres etapas.
Primero se ejecuta una criba de Eratóstenes hasta \(n\). Un arreglo de bytes o booleanos marca los candidatos a primos, se eliminan los múltiplos compuestos y los índices que sobreviven se guardan en una lista de primos. Como la instancia objetivo usa \(n=20{,}000{,}000\), esta fase es grande, pero totalmente directa.
Para cada primo \(p\), la implementación calcula \(v_p(m!)\) dividiendo repetidamente \(m\) por \(p\) y acumulando los cocientes. La misma rutina se aplica a \(n\), a \(k\) y al valor complementario \(n-k\). Esto implementa la fórmula de Legendre de forma literal y evita factorizar enteros individuales.
Una vez conocidas las tres valoraciones, el exponente de \(p\) en el coeficiente binomial se obtiene por sustracción:
$$v_p\!\left(\binom{n}{k}\right)=v_p(n!) - v_p(k!) - v_p((n-k)!).$$
Después, la implementación añade
$$p \cdot v_p\!\left(\binom{n}{k}\right)$$
a un total entero acumulado. La versión en C++ incluye además una comprobación pequeña con \(\binom{10}{3}\), verificando que el resultado sea 14 antes de atacar la instancia principal. Las versiones en Python y Java realizan la misma matemática con los mismos parámetros por defecto.
La criba hasta \(n\) cuesta \(O(n \log \log n)\) tiempo y \(O(n)\) memoria. Ese es también el principal coste espacial, porque se mantiene una marca de primalidad por cada entero hasta \(n\).
Después de la criba, cada primo \(p\) requiere \(O(\log_p n)\) divisiones para evaluar la suma de Legendre, así que la fase de valoraciones cuesta en total
$$O\!\left(\sum_{p \le n}\log_p n\right).$$
Combinando ambas partes, el tiempo total es
$$O\!\left(n \log \log n + \sum_{p \le n}\log_p n\right),$$
con uso de memoria \(O(n)\). Para el tamaño real del problema, el algoritmo es eficaz porque nunca intenta construir el gigantesco número \(\binom{20{,}000{,}000}{15{,}000{,}000}\) como tal.
这道题要求计算二项式系数 \(\binom{20{,}000{,}000}{15{,}000{,}000}\) 的素因子加权和，并且素因子要按重数计算。若一个正整数 \(N\) 的素因子分解为
$$N=\prod_{p \text{ 为素数}} p^{e_p},$$
那么题目要的量就是
$$S(N)=\sum_{p \text{ 为素数}} p\,e_p.$$
因此，本题本质上是在求
$$S\!\left(\binom{20{,}000{,}000}{15{,}000{,}000}\right)=\sum_{p \le 20{,}000{,}000} p\,v_p\!\left(\binom{20{,}000{,}000}{15{,}000{,}000}\right),$$
其中 \(v_p(x)\) 表示素数 \(p\) 在整数 \(x\) 的分解中出现的指数。由于这个二项式系数极其巨大，不可能先把它完整算出来再去分解质因数，所以解法必须直接处理每个素数的指数。
整套方法围绕一个核心思想展开：不要生成庞大的 \(\binom{n}{k}\)，而是逐个求出每个素数在其中出现了多少次，再把贡献 \(p \cdot v_p\) 加起来。
首先写出
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$
在乘法中，素数指数相加；在除法中，素数指数相减。所以对任意素数 \(p\)，都有
$$v_p\!\left(\binom{n}{k}\right)=v_p(n!) - v_p(k!) - v_p((n-k)!).$$
这正是实现所使用的关键恒等式。它把问题转化为：对于每个素数，只要分别求出它在三个阶乘里的指数即可。这里的 \(n-k\) 不是额外技巧，而是因为分母本来就包含 \(k!\) 和 \((n-k)!\)。同时，恒等式 \(\binom{n}{k}=\binom{n}{n-k}\) 也说明这两个较小阶乘在地位上完全对称。
为了计算 \(v_p(m!)\)，代码使用 Legendre 公式：
$$v_p(m!)=\sum_{j \ge 1}\left\lfloor \frac{m}{p^j}\right\rfloor.$$
这个公式非常直观。\(\left\lfloor m/p \right\rfloor\) 统计了 \(1\) 到 \(m\) 中有多少个 \(p\) 的倍数；\(\left\lfloor m/p^2 \right\rfloor\) 统计了这些数中还能额外再提供一个 \(p\) 的那些 \(p^2\) 的倍数；后面的项依次处理 \(p^3,p^4,\dots\)。当 \(p^j > m\) 时，后续所有项都为零，所以这个和实际上是有限的。
从实现角度看，这意味着可以让 \(x=m\)，然后不断执行整除 \(x \gets \lfloor x/p \rfloor\)，并把每一步的商累加起来：
$$v_p(m!)=\left\lfloor \frac{m}{p}\right\rfloor+\left\lfloor \frac{m}{p^2}\right\rfloor+\left\lfloor \frac{m}{p^3}\right\rfloor+\cdots.$$
把 Legendre 公式代入二项式系数的指数公式，就得到
$$v_p\!\left(\binom{n}{k}\right)=\sum_{j \ge 1}\left(\left\lfloor \frac{n}{p^j}\right\rfloor-\left\lfloor \frac{k}{p^j}\right\rfloor-\left\lfloor \frac{n-k}{p^j}\right\rfloor\right).$$
于是总答案可以写成
$$S\!\left(\binom{n}{k}\right)=\sum_{p \le n} p \sum_{j \ge 1}\left(\left\lfloor \frac{n}{p^j}\right\rfloor-\left\lfloor \frac{k}{p^j}\right\rfloor-\left\lfloor \frac{n-k}{p^j}\right\rfloor\right).$$
为什么只需要枚举 \(p \le n\) 的素数？因为比 \(n\) 大的素数不可能出现在 \(n!\) 中，自然也不可能出现在 \(\binom{n}{k}\) 的分解中。所以算法的第一步就是用筛法生成所有不超过 \(n\) 的素数。
拿到素数表之后，每个素数的贡献都可以独立计算：先算它在 \(n!\) 中的指数，再减去它在 \(k!\) 和 \((n-k)!\) 中的指数，最后乘上该素数本身并加入总和。
实现里用来做小规模校验的例子是
$$\binom{10}{3}=120=2^3 \cdot 3 \cdot 5,$$
因此答案应该是
$$S\!\left(\binom{10}{3}\right)=2 \cdot 3 + 3 \cdot 1 + 5 \cdot 1 = 14.$$
下面用 Legendre 公式把这个结果完整推出来。对 \(p=2\)，有
$$v_2(10!)=5+2+1=8,\qquad v_2(3!)=1,\qquad v_2(7!)=3+1=4,$$
所以
$$v_2\!\left(\binom{10}{3}\right)=8-1-4=3.$$
对 \(p=3\)，有
$$v_3(10!)=3+1=4,\qquad v_3(3!)=1,\qquad v_3(7!)=2,$$
因此
$$v_3\!\left(\binom{10}{3}\right)=4-1-2=1.$$
对 \(p=5\)，有
$$v_5(10!)=2,\qquad v_5(3!)=0,\qquad v_5(7!)=1,$$
从而
$$v_5\!\left(\binom{10}{3}\right)=2-0-1=1.$$
而 \(p=7\) 则展示了完全抵消的情形：
$$v_7(10!)=1,\qquad v_7(3!)=0,\qquad v_7(7!)=1,\qquad v_7\!\left(\binom{10}{3}\right)=0.$$
这个例子很好地说明了解法的本质：虽然从头到尾都没有真正构造出巨大的二项式系数，但每个素数的准确指数仍然可以被严格恢复出来。
C++、Python 和 Java 实现遵循完全相同的三阶段流程。
第一步是对 \(n\) 运行埃拉托斯特尼筛法。实现用一个字节数组或布尔数组标记每个整数当前是否仍可能是素数，再把合数的倍数划去，最后把剩下的下标收集成素数列表。目标实例中 \(n=20{,}000{,}000\)，因此这一步的数据量不小，但算法本身非常标准。
对每个素数 \(p\)，实现都用“不断整除并累加商”的方式计算 \(v_p(m!)\)。同一个过程分别应用在 \(n\)、\(k\) 和互补值 \(n-k\) 上。这就是 Legendre 公式的直接程序化表达，不需要对任何单独的大整数做质因数分解。
当三个阶乘估值都算出后，素数 \(p\) 在二项式系数中的指数就是
$$v_p\!\left(\binom{n}{k}\right)=v_p(n!) - v_p(k!) - v_p((n-k)!).$$
随后实现把
$$p \cdot v_p\!\left(\binom{n}{k}\right)$$
加入到运行总和中。C++ 实现还附带了一个 \(\binom{10}{3}\) 的小检查，在处理主实例之前先确认结果确实是 14。Python 和 Java 版本执行的是同一套数学过程，默认参数也相同。
筛到 \(n\) 的时间复杂度是 \(O(n \log \log n)\)，空间复杂度是 \(O(n)\)。由于要为每个不超过 \(n\) 的整数保存一个素性标记，这也是整个算法中最主要的空间消耗。
筛法结束后，每个素数 \(p\) 需要做 \(O(\log_p n)\) 次整除来完成 Legendre 求和，因此估值阶段的总复杂度为
$$O\!\left(\sum_{p \le n}\log_p n\right).$$
合并两部分，整体时间复杂度是
$$O\!\left(n \log \log n + \sum_{p \le n}\log_p n\right),$$
空间复杂度是 \(O(n)\)。对于本题的真实规模，这个算法之所以可行，关键就在于它从来不去显式构造那个极其巨大的二项式系数，而只追踪各个素数的指数。
Нужно найти сумму простых множителей биномиального коэффициента \(\binom{20{,}000{,}000}{15{,}000{,}000}\), причём каждый простой множитель учитывается с кратностью. Если положительное целое число \(N\) раскладывается как
$$N=\prod_{p \text{ простое}} p^{e_p},$$
то требуемая взвешенная сумма равна
$$S(N)=\sum_{p \text{ простое}} p\,e_p.$$
Значит, в этой задаче требуется вычислить
$$S\!\left(\binom{20{,}000{,}000}{15{,}000{,}000}\right)=\sum_{p \le 20{,}000{,}000} p\,v_p\!\left(\binom{20{,}000{,}000}{15{,}000{,}000}\right),$$
где \(v_p(x)\) обозначает показатель простого \(p\) в разложении числа \(x\). Явно вычислять и затем факторизовать такой биномиальный коэффициент нереально, поэтому решение целиком строится на подсчёте показателей простых.
Основная идея одна: мы не строим огромное число \(\binom{n}{k}\), а сразу определяем, сколько раз каждый простой делитель входит в него, после чего суммируем вклады вида \(p \cdot v_p\).
Запишем
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$
Показатели простых складываются в произведении и вычитаются в частном. Поэтому для любого простого \(p\)
$$v_p\!\left(\binom{n}{k}\right)=v_p(n!) - v_p(k!) - v_p((n-k)!).$$
Именно это сокращение лежит в основе всех реализаций. Тем самым задача сводится к трём вычислениям факториальной оценки для каждого простого. Член \(n-k\) возникает естественно, потому что в знаменателе стоят и \(k!\), и \((n-k)!\); кроме того, симметрия \(\binom{n}{k}=\binom{n}{n-k}\) показывает, почему обе малые факториальные части равноправны.
Чтобы вычислить \(v_p(m!)\), используется формула Лежандра:
$$v_p(m!)=\sum_{j \ge 1}\left\lfloor \frac{m}{p^j}\right\rfloor.$$
Смысл каждого слагаемого прозрачен. \(\left\lfloor m/p \right\rfloor\) считает кратные \(p\) среди чисел от \(1\) до \(m\); \(\left\lfloor m/p^2 \right\rfloor\) учитывает дополнительные множители \(p\), приходящие от кратных \(p^2\); далее аналогично для \(p^3,p^4,\dots\). Сумма фактически конечна, потому что при \(p^j > m\) все последующие целые части равны нулю.
С вычислительной точки зрения это означает: берём \(x=m\), многократно делим на \(p\) и суммируем получающиеся частные:
$$v_p(m!)=\left\lfloor \frac{m}{p}\right\rfloor+\left\lfloor \frac{m}{p^2}\right\rfloor+\left\lfloor \frac{m}{p^3}\right\rfloor+\cdots.$$
Подставляя формулу Лежандра в биномиальную формулу для показателя, получаем
$$v_p\!\left(\binom{n}{k}\right)=\sum_{j \ge 1}\left(\left\lfloor \frac{n}{p^j}\right\rfloor-\left\lfloor \frac{k}{p^j}\right\rfloor-\left\lfloor \frac{n-k}{p^j}\right\rfloor\right).$$
Следовательно, общий ответ равен
$$S\!\left(\binom{n}{k}\right)=\sum_{p \le n} p \sum_{j \ge 1}\left(\left\lfloor \frac{n}{p^j}\right\rfloor-\left\lfloor \frac{k}{p^j}\right\rfloor-\left\lfloor \frac{n-k}{p^j}\right\rfloor\right).$$
Почему достаточно простых \(p \le n\)? Потому что простое число, большее \(n\), не может входить в \(n!\), а значит, не может появиться и в разложении биномиального коэффициента. Поэтому первый этап алгоритма состоит в том, чтобы с помощью решета перечислить все простые до \(n\).
После этого вклад каждого простого считается независимо: находим его показатель в \(n!\), вычитаем показатели из знаменателя, умножаем на сам простой и добавляем к общей сумме.
Небольшая проверка, используемая реализациями, такова:
$$\binom{10}{3}=120=2^3 \cdot 3 \cdot 5,$$
поэтому правильная взвешенная сумма должна быть
$$S\!\left(\binom{10}{3}\right)=2 \cdot 3 + 3 \cdot 1 + 5 \cdot 1 = 14.$$
Формула Лежандра даёт этот результат напрямую. Для \(p=2\)
$$v_2(10!)=5+2+1=8,\qquad v_2(3!)=1,\qquad v_2(7!)=3+1=4,$$
откуда
$$v_2\!\left(\binom{10}{3}\right)=8-1-4=3.$$
Для \(p=3\)
$$v_3(10!)=3+1=4,\qquad v_3(3!)=1,\qquad v_3(7!)=2,$$
поэтому
$$v_3\!\left(\binom{10}{3}\right)=4-1-2=1.$$
Для \(p=5\)
$$v_5(10!)=2,\qquad v_5(3!)=0,\qquad v_5(7!)=1,$$
следовательно,
$$v_5\!\left(\binom{10}{3}\right)=2-0-1=1.$$
А для \(p=7\) происходит полное сокращение:
$$v_7(10!)=1,\qquad v_7(3!)=0,\qquad v_7(7!)=1,\qquad v_7\!\left(\binom{10}{3}\right)=0.$$
Этот пример наглядно показывает, почему метод работает: сам биномиальный коэффициент не строится, но показатели всех простых восстанавливаются точно.
Реализации на C++, Python и Java выполняют один и тот же трёхэтапный алгоритм.
Сначала запускается решето Эратосфена до \(n\). Байтовый или логический массив помечает кандидатов на простоту, кратные составных чисел вычёркиваются, а оставшиеся индексы собираются в список простых чисел. Для целевого значения \(n=20{,}000{,}000\) это заметная по объёму подготовка, но сама идея стандартна.
Для каждого простого \(p\) реализация вычисляет \(v_p(m!)\), многократно деля \(m\) на \(p\) и суммируя частные. Одна и та же процедура применяется к \(n\), к \(k\) и к дополнительному значению \(n-k\). Это буквальная реализация формулы Лежандра, которая полностью обходится без факторизации отдельных больших чисел.
Когда три оценки готовы, показатель простого \(p\) в биномиальном коэффициенте находится вычитанием:
$$v_p\!\left(\binom{n}{k}\right)=v_p(n!) - v_p(k!) - v_p((n-k)!).$$
После этого к накапливаемой сумме добавляется величина
$$p \cdot v_p\!\left(\binom{n}{k}\right).$$
В реализации на C++ есть также маленькая проверка для \(\binom{10}{3}\), подтверждающая значение 14 перед запуском основной задачи. Версии на Python и Java используют ту же математику с теми же стандартными параметрами.
Решето до \(n\) требует \(O(n \log \log n)\) времени и \(O(n)\) памяти. Это же и основной расход памяти, потому что для каждого целого числа до \(n\) хранится метка простоты.
После этапа решета каждый простой \(p\) требует \(O(\log_p n)\) делений для вычисления суммы Лежандра, так что суммарная стоимость второго этапа равна
$$O\!\left(\sum_{p \le n}\log_p n\right).$$
Итоговая асимптотика по времени равна
$$O\!\left(n \log \log n + \sum_{p \le n}\log_p n\right),$$
а по памяти равна \(O(n)\). Для реального размера задачи алгоритм эффективен именно потому, что он никогда не пытается явно построить гигантское число \(\binom{20{,}000{,}000}{15{,}000{,}000}\).
المطلوب هو حساب مجموع العوامل الأولية لمعامل ثنائي الحدين \(\binom{20{,}000{,}000}{15{,}000{,}000}\) مع احتساب التكرار. إذا كان تحليل عدد صحيح موجب \(N\) إلى عوامله الأولية هو
$$N=\prod_p p^{e_p},$$
فإن الكمية المطلوبة في هذه المسألة هي
$$S(N)=\sum_p p\,e_p.$$
وبالتالي فنحن نريد حساب
$$S\!\left(\binom{20{,}000{,}000}{15{,}000{,}000}\right)=\sum_{p \le 20{,}000{,}000} p\,v_p\!\left(\binom{20{,}000{,}000}{15{,}000{,}000}\right),$$
حيث تمثل \(v_p(x)\) أسَّ العدد الأولي \(p\) في تحليل \(x\). من غير العملي تماماً أن نبني هذا المعامل الثنائي الهائل ثم نحاول تحليله، لذا تعتمد الحلول كلها على تتبع أسس الأعداد الأولية مباشرة.
الفكرة الأساسية واحدة: لا نحسب العدد الضخم \(\binom{n}{k}\) نفسه، بل نحسب عدد مرات ظهور كل أولي فيه، ثم نجمع المساهمات الموزونة \(p \cdot v_p\).
نبدأ من العلاقة
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$
أسس العوامل الأولية تتجمع عند الضرب وتُطرح عند القسمة، ولذلك نحصل لكل عدد أولي \(p\) على
$$v_p\!\left(\binom{n}{k}\right)=v_p(n!) - v_p(k!) - v_p((n-k)!).$$
هذه هي هوية الإلغاء الدقيقة التي تعتمد عليها التطبيقات. وبهذا تتحول المسألة إلى ثلاث عمليات تقييم لأس \(p\) داخل مضروبات. وجود \(n-k\) ليس حيلة منفصلة، بل يأتي مباشرة من كون المقام يساوي \(k!(n-k)!\)، كما أن التناظر \(\binom{n}{k}=\binom{n}{n-k}\) يوضح لماذا يلعب هذان الحدّان الدور نفسه.
لحساب \(v_p(m!)\) تستخدم الشيفرة صيغة ليجاندر:
$$v_p(m!)=\sum_{j \ge 1}\left\lfloor \frac{m}{p^j}\right\rfloor.$$
كل حد في هذا المجموع له معنى مباشر. الحد \(\left\lfloor m/p \right\rfloor\) يعد مضاعفات \(p\) بين \(1\) و\(m\)، والحد \(\left\lfloor m/p^2 \right\rfloor\) يعد النسخ الإضافية من \(p\) التي تأتي من مضاعفات \(p^2\)، ثم يستمر المنطق نفسه مع \(p^3\) و\(p^4\) وما بعدها. المجموع فعلياً منتهٍ، لأنه عندما يصبح \(p^j > m\) تختفي كل الحدود اللاحقة.
ومن الناحية العملية يمكن حساب ذلك بالبدء من \(x=m\)، ثم قسمة \(x\) على \(p\) مراراً وجمع نواتج القسمة:
$$v_p(m!)=\left\lfloor \frac{m}{p}\right\rfloor+\left\lfloor \frac{m}{p^2}\right\rfloor+\left\lfloor \frac{m}{p^3}\right\rfloor+\cdots.$$
بالتعويض بصيغة ليجاندر داخل علاقة المعامل الثنائي نحصل على
$$v_p\!\left(\binom{n}{k}\right)=\sum_{j \ge 1}\left(\left\lfloor \frac{n}{p^j}\right\rfloor-\left\lfloor \frac{k}{p^j}\right\rfloor-\left\lfloor \frac{n-k}{p^j}\right\rfloor\right).$$
ومن ثم يكون الجواب الكلي
$$S\!\left(\binom{n}{k}\right)=\sum_{p \le n} p \sum_{j \ge 1}\left(\left\lfloor \frac{n}{p^j}\right\rfloor-\left\lfloor \frac{k}{p^j}\right\rfloor-\left\lfloor \frac{n-k}{p^j}\right\rfloor\right).$$
لماذا نكتفي بالأوليات التي لا تتجاوز \(n\)؟ لأن أي أولي أكبر من \(n\) لا يمكن أن يظهر في \(n!\)، وبالتالي لا يمكن أن يسهم في تحليل \(\binom{n}{k}\). لهذا تبدأ الخوارزمية أولاً بتوليد جميع الأوليات \(p \le n\) بواسطة غربال.
بعد الحصول على قائمة الأوليات، يصبح حساب كل مساهمة مستقلاً: نحسب أس \(p\) في \(n!\)، ثم نطرح منه أسه في \(k!\) وفي \((n-k)!\)، ثم نضرب في \(p\) ونضيف إلى المجموع.
مثال التحقق الصغير المستخدم في التطبيقات هو
$$\binom{10}{3}=120=2^3 \cdot 3 \cdot 5,$$
ولذلك يجب أن تكون القيمة المطلوبة
$$S\!\left(\binom{10}{3}\right)=2 \cdot 3 + 3 \cdot 1 + 5 \cdot 1 = 14.$$
تعطينا صيغة ليجاندر هذه النتيجة مباشرة. بالنسبة إلى \(p=2\)، لدينا
$$v_2(10!)=5+2+1=8,\qquad v_2(3!)=1,\qquad v_2(7!)=3+1=4,$$
ومن ثم
$$v_2\!\left(\binom{10}{3}\right)=8-1-4=3.$$
وبالنسبة إلى \(p=3\)،
$$v_3(10!)=3+1=4,\qquad v_3(3!)=1,\qquad v_3(7!)=2,$$
فنحصل على
$$v_3\!\left(\binom{10}{3}\right)=4-1-2=1.$$
وبالنسبة إلى \(p=5\)،
$$v_5(10!)=2,\qquad v_5(3!)=0,\qquad v_5(7!)=1,$$
وبالتالي
$$v_5\!\left(\binom{10}{3}\right)=2-0-1=1.$$
أما \(p=7\) فيعطي مثالاً على الإلغاء الكامل:
$$v_7(10!)=1,\qquad v_7(3!)=0,\qquad v_7(7!)=1,\qquad v_7\!\left(\binom{10}{3}\right)=0.$$
هذا المثال يبين بدقة لماذا تنجح الطريقة: لا نكوّن المعامل الثنائي الضخم نفسه، ومع ذلك نستعيد كل أس أولي فيه استعادة صحيحة.
تتبع تطبيقات C++ وPython وJava المراحل الثلاث نفسها.
في البداية تُشغَّل خوارزمية غربال إراتوستينس حتى \(n\). تستعمل الشيفرة مصفوفة بايتات أو مصفوفة منطقية لتمييز الأعداد التي ما زالت مرشحة لأن تكون أولية، ثم تُشطب المضاعفات المركبة، وبعد ذلك تُجمع الفهارس الباقية في قائمة للأوليات. وبما أن الحالة الفعلية تستخدم \(n=20{,}000{,}000\)، فهذه المرحلة كبيرة نسبياً ولكنها قياسية جداً.
لكل أولي \(p\)، تحسب الشيفرة \(v_p(m!)\) من خلال قسمة \(m\) على \(p\) مراراً وجمع نواتج القسمة. وتُطبق العملية نفسها على \(n\) وعلى \(k\) وعلى القيمة المتممة \(n-k\). هذا تنفيذ مباشر لصيغة ليجاندر، ويغني تماماً عن تحليل الأعداد الكبيرة واحداً واحداً.
بعد معرفة القيم الثلاث، يصبح أس \(p\) في المعامل الثنائي
$$v_p\!\left(\binom{n}{k}\right)=v_p(n!) - v_p(k!) - v_p((n-k)!).$$
ثم تضيف الشيفرة الكمية
$$p \cdot v_p\!\left(\binom{n}{k}\right)$$
إلى مجموع تراكمي صحيح. تتضمن نسخة C++ أيضاً تحققاً صغيراً باستعمال \(\binom{10}{3}\) للتأكد من أن الناتج يساوي 14 قبل معالجة المسألة الأساسية. أما نسختا Python وJava فتنفذان الرياضيات نفسها وبالقيم الافتراضية نفسها.
الغربال حتى \(n\) يكلف زمناً مقداره \(O(n \log \log n)\) وذاكرة مقدارها \(O(n)\). وهذا أيضاً هو الجزء الأكبر من استهلاك الذاكرة، لأن هناك علامة أولية واحدة لكل عدد صحيح حتى \(n\).
بعد ذلك يحتاج كل أولي \(p\) إلى \(O(\log_p n)\) من عمليات القسمة لإكمال مجموع ليجاندر، ولذلك تكون كلفة مرحلة التقييم
$$O\!\left(\sum_{p \le n}\log_p n\right).$$
وبجمع المرحلتين نحصل على زمن كلي
$$O\!\left(n \log \log n + \sum_{p \le n}\log_p n\right),$$
مع استخدام ذاكرة قدره \(O(n)\). والخوارزمية عملية في حجم المسألة الحقيقي لأنها لا تحاول أبداً بناء العدد الهائل \(\binom{20{,}000{,}000}{15{,}000{,}000}\) بشكل صريح، بل تكتفي بتتبع أسس الأوليات.