Rust Implementation of Problem 87
View source code here on GitHub!
Includes
Problem Solution
- pub fn problems::p0087::p0087() -> utils::Answer
1/*
2Project Euler Problem 87
3
4I ended up having to do this with recursion, which I normally do not like to
5use that much. Small changes can have large effects on later results. Still,
6this seems to work for the moment.
7
8Revision 1:
9
10Shorten the code slightly to take advantage of the primes_until() stop argument.
11Probably loses performance slightly.
12
13Problem:
14
15The smallest number expressible as the sum of a prime square, prime cube, and
16prime fourth power is 28. In fact, there are exactly four numbers below fifty
17that can be expressed in such a way:
18
1928 = 2**2 + 2**3 + 2**4
2033 = 3**2 + 2**3 + 2**4
2149 = 5**2 + 2**3 + 2**4
2247 = 2**2 + 3**3 + 2**4
23
24How many numbers below fifty million can be expressed as the sum of a prime
25square, prime cube, and prime fourth power?
26*/
27use std::collections::HashSet;
28
29use crate::include::primes::primes_until;
30use crate::include::utils::Answer;
31
32
33pub fn p0087() -> Answer {
34 let mut seen: HashSet<u64> = HashSet::new();
35 let root2_50m = f64::powf(50_000_000.0, 1.0 / 2.0).floor() as u64;
36 let root3_50m = f64::powf(50_000_000.0, 1.0 / 3.0).floor() as u64;
37 let root4_50m = f64::powf(50_000_000.0, 1.0 / 4.0).floor() as u64;
38 for x in primes_until(root2_50m) {
39 let x2 = x * x;
40 for y in primes_until(root3_50m) {
41 let y3 = y * y * y;
42 for z in primes_until(root4_50m) {
43 let total = x2 + y3 + z * z * z * z;
44 if total < 50_000_000 {
45 seen.insert(total);
46 }
47 else {
48 break;
49 }
50 }
51 }
52 }
53 return Answer::Int((seen.len() as u64).into());
54}