Factorial Iterative

Factorials grow fast; competitive problems use Legendre’s formula (prime exponents in n!) or Wilson/Lucas theorems mod prime.

Why this shows up in the real world

Cryptography, competitive programming, and combinatorics lean on primes, residues mod n, and fast arithmetic on huge integers.

Core idea (explained for students)

Count factors of prime p in n! via n/p + n/p² + .... Iterative factorial mod m needs m composite handled via prime powers or precomputed inverses.

Try this in Python

def legendre_p(n: int, p: int) -> int:
    e = 0
    pk = p
    while pk <= n:
        e += n // pk
        pk *= p
    return e


print(legendre_p(10, 2))

Common mistakes

• Raw factorial loop mod composite without theory.
• Off-by-one in Legendre sum.
• 0! edge case.

Key takeaways

• Prime factorization of n! via sieve of primes up to n.
• Use DP with mod and division using inverse when denominator invertible mod m.