Rust Implementation of Problem 77
View source code here on GitHub!
Includes
Problem Solution
- pub fn problems::p0077::p0077() -> utils::Answer
1/*
2Project Euler Problem 77
3
4I was able to recycle a lot of the work on #76 for this, though I did have to undo some optimizations to get there
5
6Problem:
7
8It is possible to write ten as the sum of primes in exactly five different ways:
9
107 + 3
115 + 5
125 + 3 + 2
133 + 3 + 2 + 2
142 + 2 + 2 + 2 + 2
15
16What is the first value which can be written as the sum of primes in over five thousand different ways?
17*/
18use core::iter::zip;
19
20use crate::include::primes::primes_until;
21use crate::include::utils::Answer;
22
23
24fn prime_summations(n: u64) -> u64 {
25 let mut answer = 0;
26 let cached_primes: Vec<u64> = primes_until(n).collect();
27 let num_primes = cached_primes.len();
28 let max_idx = num_primes - 1;
29 let mut counts: Vec<u64> = vec![0; num_primes];
30 // counts is a list containing how many times you add each prime
31 // so for 5 + 5 + 3 + 2 it would be [1, 1, 2]
32 counts[0] = n / 2; // primes[0] = 2
33 loop {
34 let mut total: u64 = zip(counts.clone(), cached_primes.clone()).map(|(x, y)| x * y).sum();
35 counts[0] += 1;
36 if total > n {
37 let mut idx: usize = 0;
38 while total > n && idx < max_idx {
39 counts[idx] = 0;
40 idx += 1;
41 counts[idx] += 1;
42 total = zip(counts.clone(), cached_primes.clone()).map(|(x, y)| x * y).sum();
43 }
44 if idx >= max_idx {
45 break;
46 }
47 counts[0] = (n - total) / 2; // primes[0] = 2
48 }
49 else if total == n {
50 answer += 1;
51 }
52 }
53 return answer;
54}
55
56
57
58pub fn p0077() -> Answer {
59 for x in 11.. {
60 if prime_summations(x) > 5_000 {
61 return Answer::Int(x.into());
62 }
63 }
64 unreachable!();
65}