팩토리얼 소인수 지수(르장드르 공식) 계산기

n!이 소수 p로 몇 번 나누어떨어지는지를 ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …로 구하는 식입니다. 1부터 n까지 가운데 p의 배수가 ⌊n/p⌋개이고 그중 p²의 배수는 한 번 더 세야 한다는 생각 그대로이며, p^i가 n을 넘으면 항이 0이 되어 저절로 끝납니다.

24개입니다. 10진법에서 0 하나는 10 = 2×5 하나를 뜻하는데 n!에는 2가 5보다 훨씬 많으므로 5의 개수가 곧 답입니다. ⌊100/5⌋ + ⌊100/25⌋ = 20 + 4 = 24가 됩니다. 100!을 직접 만들 필요가 없습니다.

밑을 소인수분해해 p^e 꼴로 쓴 뒤 각 소수마다 ⌊v_p(n!) / e⌋를 구해 가장 작은 것을 고릅니다. 12 = 2²×3처럼 지수가 1이 아닌 소인수가 있으면 그만큼 나눠 줘야 하는데, 이 나눗셈을 빼먹는 것이 가장 흔한 실수입니다. 20!을 12진법으로 적으면 0이 8개입니다.

있습니다. v_p(n!) = (n − s_p(n)) / (p − 1)이며 s_p(n)은 n을 p진법으로 적었을 때 자릿수의 합입니다. 반복이 필요 없고, 위의 합과 언제나 같아야 하므로 좋은 검산이 됩니다. 자릿수 합이 n에 견주어 작으므로 v_p(n!)이 대략 n/(p−1)이라는 것도 이 식에서 보입니다.

C(n, k)가 소수 p로 몇 번 나누어떨어지는지는 k와 n−k를 p진법으로 더할 때 일어나는 받아올림의 횟수와 같다는 정리입니다. v_p(n!) − v_p(k!) − v_p((n−k)!)를 계산하는 것과 결과가 같지만, 받아올림을 세는 쪽이 훨씬 빠르고 뜻도 분명합니다.

뤼카는 나머지를, 쿠머는 지수를 말합니다. 뤼카 정리는 C(n, k) mod p가 얼마인지 자릿수마다의 작은 이항계수 곱으로 구하고, 쿠머 정리는 C(n, k)가 p로 몇 번 나누어떨어지는지 받아올림 횟수로 셉니다. 「받아올림이 없으면 나누어떨어지지 않는다」와 「어느 자리에서든 k의 숫자가 n보다 크면 0이 아니다」는 같은 말이라 두 정리가 맞물립니다.

m을 2진법으로 적었을 때의 1비트 개수와 같습니다. m과 m을 2진법으로 더하면 1이 있는 자리마다 정확히 한 번씩 받아올림이 일어나기 때문입니다. m = 8이면 1비트가 하나뿐이라 C(16, 8)은 2로 한 번만 나누어떨어집니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.