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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
pub fn prime_factorize(mut n: u64) -> Vec<(u64, u8)> {
assert!(n > 0);
let mut factors = vec![];
for i in 2..n {
if i * i > n {
break;
}
if n % i != 0 {
continue;
}
let mut e = 0;
while n % i == 0 {
e += 1;
n /= i;
}
factors.push((i, e));
}
if n != 1 {
factors.push((n, 1));
}
factors
}
// TODO
#[cfg(test)]
mod tests {
#[test]
fn test() {
use super::*;
assert_eq!(
prime_factorize(9999999999999),
[(3, 2), (53, 1), (79, 1), (265371653, 1)],
);
assert_eq!(
prime_factorize(9316358251200),
[
(2, 6),
(3, 3),
(5, 2),
(7, 1),
(11, 1),
(13, 1),
(17, 1),
(19, 1),
(23, 1),
(29, 1)
],
);
}
}