Python Efficiency / Optimization Project Euler #5 example

user_1120229 0
Viewed 830

I wrote this solution to Project Euler #5. 

import time
start_time = time.time()

def ProjectEulerFive (m = 20):

    a = m
    start = 2
    while (m % start) == 0:
        start += 1

    b = start
    while b < m:
        if ( a % b) != 0:
           a += m
           b = start
           continue
        else:
            b += 1
    return a

import sys

if (len(sys.argv)) > 2:
    print "error: this function takes a max of 1 argument"
elif (len(sys.argv)) == 2:
    print ProjectEulerFive(int(sys.argv[1]))
else:                          
    print ProjectEulerFive();

print "took " + str(time.time() - start_time ) + " seconds"

Takes my system about 8.5 seconds.

Then I decided to compare with other peoples solutions. I found this Project Euler 5 in Python - How can I optimize my solution?.

I hadn't thought of unique prime factorization.

But anyways, one supposedly optimized non-prime factorization based solution posted there: 

import time
start_time = time.time()

check_list = [11, 13, 14, 16, 17, 18, 19, 20]

def find_solution(step):
    for num in xrange(step, 999999999, step):
        if all(num % n == 0 for n in check_list):
            return num
    return None

if __name__ == '__main__':
    solution = find_solution(20)
    if solution is None:
        print "No answer found"
    else:
        print "found an answer:", solution

    print "took " + str(time.time() - start_time ) + " seconds"

Takes my system about 37 seconds

My code is about 4 times faster even though I unnecessarily check for divisibility of 3,4,5,6,7,8,9,10, and 12.

I'm new to python, and having trouble seeing where the inefficiency is coming from.

EDIT:

I did another test. 

import time
start_time = time.time()

def ProjectEulerFive (m = 20):
    ls = [11, 13, 14, 15, 16, 17, 18, 19]
    a = m
    i = 0
    while i < len(ls):
        if ( a % ls[i]) != 0:
            a += m
            i = 0
            continue
        else:
            i += 1
    return a

print ProjectEulerFive();                           
print "took " + str(time.time() - start_time ) + " seconds"

Takes my system 6 seconds, but this: 

import time
start_time = time.time()

def ProjectEulerFive (m = 20):

    a = m
    start = 11

    b = start
    while b < m:
        if ( a % b) != 0:
           a += m
           b = start
           continue
        else:
            b += 1
    return a

print ProjectEulerFive()
print "took " + str(time.time() - start_time ) + " seconds"

Takes about 3.7 seconds

python performance
5 Answers

you can solve this problem using prime factors. Solves for n=20 in 0.0004s and for n=50 in 0.0011.

from math import sqrt
import time
num = int(input("Number: "))
start_time = time.clock()

def is_prime(n):
    if(n == 2 or n == 3):
        return True
    elif(n < 2 or n % 2 == 0):
        return False
    for i in range(3, int(sqrt(n))+1, 2):
        if(n % i == 0):
            return False
    return True

def decompose(n):
    if(n == 1 or n == 0):
        return [n]
    l = []
    residue = n
    while(residue != 1):
        for i in range(1, residue+1):
            if(residue%i==0 and is_prime(i)):
                l.append(i)
                residue //= i
                break
    return l

l = []
for i in range(1, num):
    d = decompose(i)
    for n in d:
        if(l.count(n) < d.count(n)):
            l += [n]*(d.count(n)-l.count(n))
result = 1
for i in l:
    result*=i
print(result)

print("time: ", time.clock()-start_time)
user_70718790

This is my implementation

I understand the why but would appreciate enlightenment on the math behind it

If I write down all prime numbers that are not greater than the highest divisible number then substitute subset of factors that include the primes divisors that are smaller than my limit..

from functools import reduce

def divisible_by_all_up_to(limit):
    def is_prime(num):
        if num == 2 or num == 3:
            return True
        if num % 2 == 0 or num < 2:
            return False
        for i in range(3, num):
            if num % i == 0:
                return False
        return True
    primes = [i for i in range(limit) if is_prime(i) == True]
    mult = []
    for index, value in enumerate(primes):
        while value * value < limit:
            value = value * value
        mult += [value]
    return mult

ans = divisible_by_all_up_to(20)

resp = reduce(lambda x, y: x*y, ans)
user_115813980
Related