3
\$\begingroup\$

Project Euler Problem 357 asks:

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.

import time
start = time.time()

import math

def divisor_generator(n):
    '''Generates the divisiors of input num'''
    large_divisors = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            if i*i != n:
                large_divisors.append(n / i)
    for divisor in reversed(large_divisors):
        yield divisor

def is_prime(n):
    '''simple prime tester'''
    if n == 2 or n == 3 :
        return True
    for i in range(2,int(n**(1/2))+1):
        if n % i == 0:
            return False
    return True

def test_condition (divisor_array, num):

    ''' Testing the condition of d+n/d by taking the input as array of divisor and num'''

    if len(divisor_array) %2 != 0: # the divisors of num = d3 is [1,d2,d3], and d2*d2=d3 hence d2+d3/d2 = 2d2 which is not prime
        return False
    if sum(divisor_array) %2 != 0: # the divisors of num = d4, [1,d2,d3,d4] (1+d4)=Prime and (d2+d3)==Prime hence sum([1,d2,d3,d4]) must be even
        return False
    if len(divisor_array)%2 == 0:
        for i in range(len(divisor_array)//2):
            if is_prime(divisor_array[i] + divisor_array[-i-1]) == False:
                return False
        return True

Count = 0
for num in range(2,31,2): #since for odd num we do not have prime numbers 

    divisor_list_num = list(divisor_generator(num))

    if test_condition(divisor_list_num,num) == True:

        Count += num

print(Count)
end = time.time()
print(end-start,"sec")

It's good up to \$\text{num} = 10^6\$ but then it gets slow after that. I find that at it takes 16 min to find the \$\text{num} < 10^7\$.

How can I inrease the speed of my code ?

\$\endgroup\$
1
\$\begingroup\$
def divisor_generator(n):
    '''Generates the divisiors of input num'''
    large_divisors = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            if i*i != n:
                large_divisors.append(n / i)
    for divisor in reversed(large_divisors):
        yield divisor

I would rename this just divisors, but other than that it seems like a reasonable general-purpose divisor enumerator for very small numbers with a couple of caveats: the doc comment has a typo and uses the wrong name for the input, and if this is supposed to work in Python 3 (which I'm guessing it is from the use of range rather than xrange) then it should use integer division: n // i.

However:

  1. This task doesn't call for a general-purpose divisor enumerator. IMO it would make more sense to return pairs (i, n // i).
  2. To scale to larger numbers it's worth finding the prime factorisation and constructing the divisors from them. The best way I know to do that is to build an array like Eratosthenes' sieve, but instead of storing a Boolean to indicate prime/composite store a prime divisor. (I generally store the lowest prime divisor, but it depends on what you want to do with it). Then you can find the prime factorisation by chaining down the array.

def is_prime(n):
    '''simple prime tester'''
    if n == 2 or n == 3 :
        return True
    for i in range(2,int(n**(1/2))+1):
        if n % i == 0:
            return False
    return True

If you're going to be testing a lot of numbers from just over 0 to N for primality then you definitely want to use a sieve, effectively testing them in parallel and caching the results.

There are a couple of PEP8 violations in this function: space before colon, no space after comma.


def test_condition (divisor_array, num):

    ''' Testing the condition of d+n/d by taking the input as array of divisor and num'''

    if len(divisor_array) %2 != 0: # the divisors of num = d3 is [1,d2,d3], and d2*d2=d3 hence d2+d3/d2 = 2d2 which is not prime
        return False

Nice special case, but it can be generalised a long way. How can you restate the test "num can be split as i and num/i which are not coprime"?

Argue this through all the way and it gives you a completely different high-level algorithm which should be much more efficient. But since this is Project Euler, I'm not going to say more than that hint.

    if sum(divisor_array) %2 != 0: # the divisors of num = d4, [1,d2,d3,d4] (1+d4)=Prime and (d2+d3)==Prime hence sum([1,d2,d3,d4]) must be even
        return False

I don't think I follow this argument. Why does the sum of more than two factors matter?

    if len(divisor_array)%2 == 0:

This condition is unnecessary, because if it failed then we've already returned False.

        for i in range(len(divisor_array)//2):
            if is_prime(divisor_array[i] + divisor_array[-i-1]) == False:
                return False
        return True

It would be more Pythonic to use all(comprehension). Also, this highlights my point about returning pairs of divisors rather than using a general-purpose divisor enumerator.

\$\endgroup\$
  • \$\begingroup\$ Sorry for my late reply. I was busy with my finals. I added sum because I thought it would be faster to check it rather then just passing for loop. \$\endgroup\$ – Reign Jun 4 at 8:40
  • \$\begingroup\$ I actually did not create the divisor generator thing myself. I still dont know sieve. I ll leanr it right now and then change my prime tester. In the test part thing. $i$ must be prime I think \$\endgroup\$ – Reign Jun 4 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.