Python Implementation of Problem 357
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 357
A 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
Problem:
Consider the divisors of 30: 1,2,3,5,6,10,15,30. It can be seen that for every divisor d of 30, d+30/d is prime.
Find the sum of all positive integers n not exceeding 100 000 000 such that for every divisor d of n, d+n/d is prime.
Revision 1:
Prime filter cuts by a little more than half, but I think this is mostly from the cache benefits on is_prime(). Prime square filter shaves off an additional ~8%. without negating its benefit, or figure out a more general solution to the filter. Filtering to evens also shaves off some more, and n=4k+2 goes even further, about 45%. This cuts it overall from ~20 minutes to ~5 minutes.
Revision 2:
Using the proper_divisors function from
p0021 speeds this up by ~11%, going from 2:26 to 2:10
1"""
2Project Euler Problem 357
3
4A key note is that n // d is always also a factor, so it ends up being pairs.
5This means you can halve your search space
6
7Problem:
8
9Consider the divisors of 30: 1,2,3,5,6,10,15,30.
10It can be seen that for every divisor d of 30, d+30/d is prime.
11
12Find the sum of all positive integers n not exceeding 100 000 000
13such that for every divisor d of n, d+n/d is prime.
14
15Revision 1:
16
17Prime filter cuts by a little more than half, but I think this is mostly from the
18cache benefits on is_prime(). Prime square filter shaves off an additional ~8%.
19without negating its benefit, or figure out a more general solution to the filter.
20Filtering to evens also shaves off some more, and n=4k+2 goes even further, about 45%.
21This cuts it overall from ~20 minutes to ~5 minutes.
22
23Revision 2:
24
25Using the :py:func:`proper_divisors <python.p0021.proper_divisors>` function from
26p0021 speeds this up by ~11%, going from 2:26 to 2:10
27"""
28from typing import Iterable
29
30from .lib.factors import proper_divisors
31from .lib.primes import is_prime, primes
32
33is_slow = True
34
35
36def divisors(n: int) -> Iterable[int]:
37 yield from proper_divisors(n)
38 yield n
39
40
41def main() -> int:
42 answer = 1 + 2 # don't bother trying 1, 2, they're correct
43 for _ in primes(100010000):
44 pass # initialize the prime cache up to max + sqrt(max). It seems silly, but it goes much faster
45 prime_squares = {p * p for p in primes(10001)}
46 for n in range(6, 100000000, 4):
47 # 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
48 for d in divisors(n):
49 if d in prime_squares:
50 break
51 # this works because if n=kp^2, then whenever d=p, (p + kp^2/p) = (k+1)p, which isn't prime
52 # but since detecting if n % d^2 == 0 is expensive, I just wait for p^2 to show up
53 if not is_prime(d + n // d):
54 break
55 else: # read as: if you didn't break
56 answer += n
57 return answer