1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/// number of a prime factor in factorial.
pub fn legendre(
mut n: u64,
p: u64,
) -> u64 {
let mut v = 0;
while n > 0 {
v += n / p;
n /= p;
}
v
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
use crate::sieve_of_eratosthenes_prime_factorize_factorial::*;
let n = 100_000;
let factors = factorize_factorial(n);
for (p, e) in factors {
assert_eq!(legendre(n as u64, p as u64), e as u64);
}
}
}