python.p0357 Namespace Reference

Functions
def	divisors
def	main ()

Detailed Description

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.

Function Documentation

def python.p0357.divisors

(

n

)

Here is the call graph for this function:

Here is the caller graph for this function:

def python.p0357.main

(

int

)

Here is the call graph for this function: