階乗の末尾に 0 はいくつ付く?
#お題
整数 N が与えられます。
N の階乗 N!
の末尾に 0 がいくつ付くか求め、出力してください。
#入力
N
・ 1 行で整数 N が与えられます。
#出力
N の階乗 N!
の末尾に 0 がいくつ付くか求め、出力してください。
#コード
import math
n = int(input())
m = math.factorial(n)
a = []
while m > 0:
a.append(m % 10)
m //= 10
cnt = 0
while a[cnt] == 0:
cnt += 1
print(cnt)
#参考
- 整数 N を受け取ります。また、末尾の 0 の個数を保持する変数を宣言します。
- N! の末尾に 0 がいくつ付くのかという問題は、N! が 10 で何回割れるのか、つまり N! を素因数分解すると 2 * 5 がいくつ出てくるのかという問題と同じであると考えられます。
- また、N! を素因数分解したとき、2 より 5 の方が出てくる頻度は少ないので、5 が何個含まれるのかを数えればよいことになります。
- 例えば、
10!
を考えるとき、因数分解すると2^8 * 3^4 * 5^2 * 7
となり、5 は 2 個含まれていることが分かります。実際に10!
は3628800
なので、5 の個数と末尾の 0 の個数は一致していることがわかります。 - では、N! を求めずに末尾の 0 の個数を求める方法を考えると、N 以下の整数に 5 で割り切れる数がいくつあるか数えればいいと思うかもしれません。ですが、50 や 600 といった、5 を 2 つ以上持っている数もあるため、5 で割り切れる数の個数だけでなく、25(5^2)で割り切れる数の個数や、125(5^3)で割り切れる数の個数なども考える必要があります。
- N 以下の整数で 5 で割り切れる数の個数は
N / 5
で求めることができ、5^2 や 5^3 で割り切れる数の個数も同様にN / (5^2)
、N / (5^3)
で求めることができます。 - ループ処理を用いて、末尾の 0 の個数を保持する変数に
N / 5
を加算し、N を 5 で割ることを繰り返すことで、同じ動作が実現できます。 - 計算した値を出力します。
N = int(input())
count_zero = 0
while N > 0:
count_zero += N // 5
N //= 5
print(count_zero)