haar_lib/math/
factorial_prime_factor.rs

1//! a!の素因数pの個数を求める。
2//!
3//! # References
4//! - <https://ja.wikipedia.org/wiki/%E3%83%AB%E3%82%B8%E3%83%A3%E3%83%B3%E3%83%89%E3%83%AB%E3%81%AE%E5%85%AC%E5%BC%8F>
5//!
6//! # Problems
7//! - <https://yukicoder.me/problems/no/2380>
8
9/// a!の素因数pの個数を求める。
10///
11/// **Time complexity** $O(\log a)$
12pub fn factorial_prime_factor(a: u64, p: u64) -> u64 {
13    let mut ret = 0;
14    let mut q = p;
15
16    while q <= a {
17        ret += a / q;
18        if let Some(q_) = q.checked_mul(p) {
19            q = q_;
20        } else {
21            break;
22        }
23    }
24
25    ret
26}
27
28#[cfg(test)]
29mod tests {
30    use super::*;
31
32    #[test]
33    fn test() {
34        for p in [2, 3, 5, 7, 11, 13] {
35            let a = 1000;
36
37            let mut ans = 0;
38
39            for mut x in 1..=a {
40                while x % p == 0 {
41                    ans += 1;
42                    x /= p;
43                }
44            }
45
46            assert_eq!(factorial_prime_factor(a, p), ans);
47        }
48    }
49}
haar_lib/math/factorial_prime_factor.rs

haar_lib/math/
factorial_prime_factor.rs
