2026-10-20
fives.rs
fn fives(mut k: u32) -> u32 {
let mut count = 0;
while k.is_multiple_of(5) {
k /= 5;
count += 1;
}
count
}
fn main() {
let total: u32 = (1..=30).map(fives).sum();
println!("{total}");
}
これは何を出力するでしょうか?
Answer
7 です。
fives(k) は、k が5で割り切れるあいだ割り続け、割った回数を返します。これは k を素因数分解(prime factorization)したときの5の指数です。1から30までのうち5の倍数は5、10、15、20、25、30の6個で、それ以外の数では0が返ります。
6個のうち25だけは 5 × 5 なので、1回割ったあとの5がもう一度割り切れ、fives(25) は2を返します。合計は 1 + 1 + 1 + 1 + 2 + 1 = 7 です。5の倍数の個数の6を答えにすると、25が持つ2つ目の5を数え落とします。
この7は、30の階乗(factorial)30! = 1 × 2 × … × 30 を素因数分解したときの5の指数でもあります。30! には2が5より多く含まれるので、5が1つあるごとに10が1つ作れ、30! の末尾には0がちょうど7個並びます。30を5で割った商の6に、30を25で割った商の1を足して同じ7を求める式は、ルジャンドルの公式(Legendre's formula)と呼ばれます1。
- 一般に、素数
pがn!に含まれる個数は、nをp、pの2乗、pの3乗、……で割った商を、商が0になるまで足した和です。pの2乗で割った商は、pを2つ以上含む数がもう1つずつ持つpを数えています。