-
Notifications
You must be signed in to change notification settings - Fork 0
/
counting_fractions.rs
26 lines (24 loc) · 1 KB
/
counting_fractions.rs
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
pub fn solve() -> i64 {
// Calculate Euler's totient of every number up to the limit.
let mut totients = (0..=1000000).collect::<Vec<i64>>();
for num in 2..totients.len() {
if totients[num] == num as i64 {
// This number is prime. The totient of each of its multiples will
// contain the term
// 1/(1 - num)
// in its product expression. Instead of multiply-assigning that
// term, we use an equivalent subtract-assign.
for multiple in (num..totients.len()).step_by(num) {
totients[multiple] -= totients[multiple] / num as i64;
}
}
}
// The number of reduced fractions with a particular denominator is the
// totient of the denominator. Hence, the total number of fractions is the
// sum.
let result = totients[2..].iter().sum();
// TODO Optimise further: implement the other algorithm described in the
// overview.
assert_eq!(result, 303963552391);
result
}