Nの階乗の末尾に０が何個付くか？という問題の考え方

Question

前提　

入力値は整数Nとする。

発生している問題

１つ目のコードで問題は解いたのですが2つ目のコードが解答として載っており、このコードの考え方が理解できません。
分かりやすく教えていただけないでしょうか？

該当のソースコード

N = int(input())
num = 1

for i in range(1,N+1):
    num *= i      
zero = 0

while True:
    if num % 10 == 0:
        num //= 10
        zero += 1
    else:
        break
print(zero)

N = int(input())

count_zero = 0
while N > 0:
    count_zero += N // 5
    N //= 5

print(count_zero)

Comments

[xebme]

10 = 2 X 5です。2の個数は不要。5の個数だけ。なぜか。

[quickquip]

数学の問題として出たとしたら、解けますか?
「数学の問題としてならわかるけれどコードとして理解できない」か「数学の問題として理解できない」かで、答えることが変わります。

Answer 1

ある数の末尾に0が何個つくか、というのは
10で何回割れるかです。
10で何回割れるかというのは、「ある数」を素因数分解して、2と5のペアが何個あるかで、
さらに言い換えると、2と5のうち少ない方の個数です。

「ある数」がNの階乗のときは、1,2,3,...,Nをそれぞれ素因数分解したときに、2と5のそれぞれの合計のうち少ない方の個数です

少ない方はどっちかを考えると、
1からNまで5の倍数は5個おきに出現しますが、2の倍数は2個おきです。なので5のほうが少ないです。

なので5の数を数えればいいことになります。

で、1からNまでの素因数に5が何個あるかの数え方ですが、
解答例では5の倍数の個数、25の倍数、125の倍数、…の合計を数えています。

とりあえず5の倍数の個数を考えると
5個おきに出現するので N//5 個になります。
次に25の倍数ですが、これは先程のN//5個の中から5個おきに出現します。(分かりにくかったら適当にN=50とかを思い浮かべてください)

125以降も結局同じ手順になりますので、
解答例のコードで5の個数を数えられます。

Comments

[Zuishin]

明快な解説で、全くその通りなのですが、なぜ質問のコードで 5 の数が数えられるのかわからないという問題もありそうです。

[ozwk]

全くその通りなので足しました