Rust Implementation of Problem 357
Note
While this is a complete solution, and will eventually complete, until proper_divisors<I>() returns an iterator
(as opposed to the current implementation that returns a vector) it will be quite slow. That conversion is underway.
View source code here on GitHub!
Includes
Problem Solution
- pub fn problems::p0357::p0357() -> utils::Answer
1/*
2Project Euler Problem 357
3
4A key note is that n // d is always also a factor, so it ends up being pairs. This means you can halve your search space
5
6Problem:
7
8Consider the divisors of 30: 1,2,3,5,6,10,15,30.
9It can be seen that for every divisor d of 30, d+30/d is prime.
10
11Find the sum of all positive integers n not exceeding 100 000 000
12such that for every divisor d of n, d+n/d is prime.
13*/
14use std::collections::HashSet;
15
16use crate::include::primes::{is_prime,primes_until};
17use crate::include::factors::proper_divisors;
18use crate::include::utils::Answer;
19
20pub fn p0357() -> Answer {
21 let mut answer: u64 = 1 + 2; // don't bother trying 1, 2, they're correct
22 let prime_squares = HashSet::<u64>::from_iter(
23 primes_until::<u64>(10001).map(|x| x * x)
24 );
25 for n in (6..100000000).step_by(4) {
26 // n can't be odd (unless 1) because then n + n/d is even, and can't be a multiple of 4 as shown below
27 let mut broken = false;
28 for d in proper_divisors(n) {
29 if prime_squares.contains(&d) || !is_prime(d + n / d) {
30 // this works because if n=kp^2, then whenever d=p, (p + kp^2/p) = (k+1)p, which isn't prime
31 // but since detecting if n % d^2 == 0 is expensive, I just wait for p^2 to show up
32 broken = true;
33 break;
34 }
35 }
36 if prime_squares.contains(&n) || !is_prime(n + 1) {
37 broken = true;
38 }
39 if !broken {
40 answer += n;
41 }
42 }
43 return Answer::Int(answer.into());
44}