Rust Implementation of Problem 69
View source code here on GitHub!
Includes
Problem Solution
- pub fn problems::p0069::p0069() -> utils::Answer
1/*
2Project Euler Problem 69
3
4First I brute forced to see if I noticed a pattern. Having noticed one, I implemented it as a solution and found it to
5be the right answer.
6
7Problem:
8
9Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than
10n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to
11nine, φ(9)=6.
12
13n Relatively Prime φ(n) n/φ(n)
142 1 1 2
153 1,2 2 1.5
164 1,3 2 2
175 1,2,3,4 4 1.25
186 1,5 2 3
197 1,2,3,4,5,6 6 1.1666...
208 1,3,5,7 4 2
219 1,2,4,5,7,8 6 1.5
2210 1,3,7,9 4 2.5
23
24It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.
25
26Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.
27*/
28use crate::include::primes::primes;
29use crate::include::utils::Answer;
30
31pub fn p0069() -> Answer {
32 let mut answer: u32 = 1;
33 for p in primes::<u32>() {
34 let new = answer * p;
35 if new <= 1_000_000 {
36 answer = new;
37 }
38 else {
39 break;
40 }
41 }
42 return Answer::Int(answer.into());
43}