[수학경시] 팩토리얼 안에 소수가 몇번 등장하는지 알아내기

 

📘 르장드르 정리: 팩토리얼 속 소수를 찾아내는 방법

팩토리얼과 소수 지수

팩토리얼 $n!$은

$$n! = 1 \times 2 \times 3 \times \cdots \times n $$

형태로, 수가 커질수록 엄청난 크기의 곱으로 확장됩니다.

예를 들어,$$10! = 3,628,800 = 2^8 \cdot 3^4 \cdot 5^2 \cdot 7$$

여기서 우리가 궁금한 건 특정 소수(예: 2, 3, 5)가 몇 번 등장하는지입니다.
직접 소인수분해를 하면 계산량이 너무 크기 때문에, 더 효율적인 방법이 필요합니다.

르장드르 정리(Legendre’s Formula)

프랑스 수학자 아드리앵 마리 르장드르가 제시한 정리에 따르면,

소수 $p$가 $n!$의 소인수분해에서 몇 번 등장하는지는 다음 공식으로 구할 수 있습니다:

$$e_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor$$

• $e_p(n!)$: $n!$ 안에서 소수 $p$의 지수
• $\lfloor x \rfloor$: 소수점 이하 버림 (floor 함수)
• 유한 번만 계산하면 됨 (왜냐하면 $p^k > n$이 되면 그 이후 항은 0이 되기 때문)

시에르핀스키 삼각형 패턴(p=2)

(1) $10!$에서 소수 2의 지수

$$
e_2(10!) = \left\lfloor \frac{10}{2} \right\rfloor + \left\lfloor \frac{10}{4} \right\rfloor + \left\lfloor \frac{10}{8} \right\rfloor
$$

$$
= 5 + 2 + 1 = 8
$$

따라서, $10!$에는 $2^8$이 포함됩니다.

 

(2) $100!$에서 소수 5의 지수

$$
e_5(100!) = \left\lfloor \frac{100}{5} \right\rfloor + \left\lfloor \frac{100}{25} \right\rfloor + \left\lfloor \frac{100}{125} \right\rfloor
$$

$$
= 20 + 4 + 0 = 24
$$

즉, $100!$에는 $5^{24}$가 들어 있습니다.
이 결과는 “100!의 끝자리 0이 몇 개인지”와도 연결됩니다. (0은 2와 5가 짝을 이루어 생기므로, $e_5(100!)$이 곧 0의 개수가 됩니다.)

 

파이썬 구현

def legendre_formula(n: int, p: int) -> int:
    """
    르장드르 정리: n! 안에서 소수 p의 지수를 계산
    """
    exponent = 0
    power = p
    while power <= n:
        exponent += n // power
        power *= p
    return exponent

# 예시 실행
print("10!에서 2의 지수:", legendre_formula(10, 2))   # 8
print("100!에서 5의 지수:", legendre_formula(100, 5)) # 24

 

활용 분야

• 조합론: $\binom{n}{k}$가 특정 소수로 나누어 떨어지는지 판별
• 정수론: 팩토리얼 기반 약수 개수 계산
• 프로그래밍 대회/올림피아드: 큰 수의 소인수 지수 계산 시 효율적인 접근
• 끝자리 0의 개수 세기: $n!$의 0의 개수는 $e_5(n!)$

 

✍️ 정리

르장드르 정리는 팩토리얼 속 소수를 꺼내는 도구입니다.
직접 소인수분해하지 않고도, 간단한 나눗셈과 버림 연산만으로 특정 소수가 몇 번 등장하는지 알 수 있죠.

큰 수를 다루는 정수론 문제에서 알아야 하는 정리입니다. 주로 경시대회 때 많이 쓰입니다.