팩토리얼 카운터 편집하기

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

즉, n!을 소인수 분해했을 때
:n! = p<sup>e<sub>p</sub></sup> × ...
에서 e<sub>p</sub>를 구하는 것이다.
==공식==
정수 n에 대해, 소수 p의 지수 e<sub>p</sub>는 다음 공식으로 계산된다.<syntaxhighlight lang="text">
e_p = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ... (p^k ≤ n인 동안 계속)
</syntaxhighlight>이 공식은 p의 거듭제곱들이 n 이하인 동안 n을 그 거듭제곱으로 나눈 몫의 합으로 계산된다.
==예시==
예를 들어, 10! = 3628800의 소인수 분해에서 2의 지수를 구하면 다음과 같다.
*⌊10/2⌋ = 5
*⌊10/4⌋ = 2
*⌊10/8⌋ = 1
*합계: 5 + 2 + 1 = 8
따라서, 10!은 2<sup>8</sup>을 포함한다.
==파이썬 구현==
<syntaxhighlight lang="python">
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
</syntaxhighlight>
==응용==
*조합식(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.
==각주==
[[분류:알고리즘]]
[[분류:수학]]