least_prime_factors/
lib.rs

1/// 「`k` を割る最小の素数」をエラトステネスのふるいの要領で `2` 以上 `n` 未満の全ての `k` について計算します。[参考](https://osak.jp/diary/diary_201310.html#20131017)
2///
3/// # Examples
4/// ```
5/// use least_prime_factors::least_prime_factors;
6/// let facs = least_prime_factors(10);
7/// assert_eq!(facs[2], 2);
8/// assert_eq!(facs[3], 3);
9/// assert_eq!(facs[4], 2);
10/// assert_eq!(facs[5], 5);
11/// assert_eq!(facs[6], 2);
12/// assert_eq!(facs[7], 7);
13/// assert_eq!(facs[8], 2);
14/// assert_eq!(facs[9], 3);
15/// ```
16pub fn least_prime_factors(n: usize) -> Vec<usize> {
17    let mut result = vec![0; n];
18    #[allow(clippy::needless_range_loop)]
19    for i in 2..n {
20        result[i] = i;
21    }
22    for i in 2..n {
23        if result[i] == i {
24            for j in ((i + i)..n).step_by(i) {
25                if result[j] == j {
26                    result[j] = i;
27                }
28            }
29        }
30    }
31    result
32}
33
34#[cfg(test)]
35mod tests {
36    use super::least_prime_factors;
37
38    #[test]
39    fn min_factors_test() {
40        let n = 1000;
41        let min_factors = least_prime_factors(n);
42        for i in 2..n {
43            let j = (2..=i).find(|&j| i % j == 0).unwrap();
44            assert_eq!(j, min_factors[i]);
45        }
46    }
47}
least_prime_factors/lib.rs

least_prime_factors/
lib.rs
