I have solved problem 12 on Project Euler website, which reads:
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
And I've solved this in two ways:
1.functools.reduce()
import math
from functools import reduce
import time
def primeFactors(n):
i = 2
factors = {}
num = 0
while i ** 2 <= n:
if n % i:
i += 1
else:
n //= i
num = factors.get(i, None)
if num is None:
factors[i] = 1
else:
factors[i] = num+1
if n > 1:
num = factors.get(n, None)
if num is None:
factors[n] = 1
else:
factors[n] = num+1
return factors
start_time = time.time()
numOfDivisors = 500
n = 2
while True:
t = int(n*(n+1)/2)
factors = primeFactors(t).values()
if reduce(lambda x, y: x*y, [t+1 for t in factors]) >= numOfDivisors:
print(t)
break
else:
n += 1
print("----%s seconds ----" % (time.time() - start_time))
2.for-loop
import math
import time
def primeFactors(n):
i = 2
factors = {}
num = 0
while i ** 2 <= n:
if n % i:
i += 1
else:
n //= i
num = factors.get(i, None)
if num is None:
factors[i] = 1
else:
factors[i] = num+1
if n > 1:
num = factors.get(n, None)
if num is None:
factors[n] = 1
else:
factors[n] = num+1
return factors
start_time = time.time()
numOfDivisors = 500
n = 2
while True:
t = int(n*(n+1)/2)
factors = primeFactors(t).values()
k = 1
for i in factors:
k *= (i+1)
if k >= numOfDivisors:
print(t)
break
else:
n += 1
print("----%s seconds ----" % (time.time() - start_time))
I tested out which one was faster, found that there was a fine line only:
1.670 secs
and 1.678 secs
I attempted to calculate the average computing time by making the given number bigger from 500 to 1000, repeating this process 10 times.
But both solutions were done almost simultaneously:
functools.reduce
[13.616845607757568, 13.67394757270813, 13.623621225357056, 13.596383094787598, 13.657264471054077, 13.694176197052002, 13.669324398040771, 13.65349006652832, 13.66620421409607, 13.57088851928711, 13.686619901657104]
for-loop
[13.56181812286377, 13.686477422714233, 13.548126935958862, 13.565587759017944, 13.562162637710571, 13.556873798370361, 13.562631845474243, 13.572312593460083, 13.57419729232788, 13.567578315734863, 13.611796617507935]
Question: Are there any insignificant or significant differences between the two from a practical view and in a normal case, Or is this just a matter of behavior of two functions to use?
253
as the answer. A number that is smaller than 500 cannot possibly have over 500 divisors. \$\endgroup\$primeFactors
function. I fixed this. And.. thanks for your revision. \$\endgroup\$