팩토리얼 카운터

팩토리얼 카운터(factorial counter)는 주어진 수 n! (n 팩토리얼)의 소인수 분해 결과를 바탕으로, 특정 소수들이 n! 안에 얼마나 곱해져 있는지를 세는 수론적 알고리즘 또는 함수이다. 일반적으로 정수 n에 대해 n!에 등장하는 소수 p의 지수를 구하는 데 사용된다.

정의

팩토리얼 카운터는 다음 문제를 해결한다: 정수 n이 주어졌을 때, n!의 소인수 분해에서 어떤 소수 p가 몇 번 곱해지는가?

즉, n!을 소인수 분해했을 때

n! = p^e_p × ...

에서 e_p를 구하는 것이다.

공식

정수 n에 대해, 소수 p의 지수 e_p는 다음 공식으로 계산된다.

e_p = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ... (p^k ≤ n인 동안 계속)

이 공식은 p의 거듭제곱들이 n 이하인 동안 n을 그 거듭제곱으로 나눈 몫의 합으로 계산된다.

예시

예를 들어, 10! = 3628800의 소인수 분해에서 2의 지수를 구하면 다음과 같다.

• ⌊10/2⌋ = 5
• ⌊10/4⌋ = 2
• ⌊10/8⌋ = 1
• 합계: 5 + 2 + 1 = 8

따라서, 10!은 2⁸을 포함한다.

파이썬 구현

def factorial_prime_exponent(n, p):
    exponent = 0
    power = p
    while power <= n:
        exponent += n // power
        power *= p
    return exponent

# 예시
n = 10
p = 2
print(f"{p}의 지수:", factorial_prime_exponent(n, p))  # 출력: 8

응용

• 조합식(nCr)의 소수성 판별
• 소수로 나누어떨어지는 계승 값 계산
• 크고 복잡한 팩토리얼 연산의 정수론적 분석
• 소수 모듈로의 나눗셈 계산 전 소인수 처리

같이 보기

• 팩토리얼
• 소인수 분해
• 이항 계수
• 조합론
• 정수론

참고 문헌

• Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics (2nd ed.). Addison-Wesley.
• Hardy, G. H., & Wright, E. M. (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press.