How can I make this code faster?

Question

I have written this code for solving Euler Project No 12, but my code runs slow.

How can I make it running faster? I have read some suggests about finding divisors, but I do not understand the logic of using sqrt for n.

Can you explain the logic of it?

Here's my code:

def sumdiv(n):
  l=[d for d in range(1,int(n/2)+1) if n%d==0] # used n/2 to short loop
  return len(l)+1 # added n itself
trnums=[1,3]

while sumdiv(trnums[-1])<=501:
  k=trnums[-1]-trnums[-2]+1
  trnums.append(trnums[-1]+k)
print(trnums[-2:])

use `[d for d in range(1,int(math.sqrt(n))+1) if n%d==0]`, you're not finding any divisors after this point. That _will_ make your code faster. — Jean-François Fabre, Oct 09 '17 at 13:03
I've already know this method but I need logic of using sqrt — Perviz Mamedov, Oct 09 '17 at 13:04
Is your question "why should I stop at `int(math.sqrt(n))+1`? — Adirio, Oct 09 '17 at 13:06
If `xy = n`, then `x <= sqrt(n) <= y`, and if you identify a pair `(x, y)`, you don't need to find `(y, x)` separately. — chepner, Oct 09 '17 at 13:08
@Jean-FrançoisFabre you mean divisors instead of primer numbers, don't you? — Adirio, Oct 09 '17 at 13:09
yeah, right. But in that case multiply by 2 unless you get a perfect square. — Jean-François Fabre, Oct 09 '17 at 13:09
https://stackoverflow.com/questions/110344/algorithm-to-calculate-the-number-of-divisors-of-a-given-number someone dupehammer already used my close vote. — Jean-François Fabre, Oct 09 '17 at 13:11

score 0 · Accepted Answer · answered Oct 09 '17 at 13:09

0

a and b are divisors of n if a * b = n. You can, without loss of generality, set b >= a. Therefore a * a is the upper limit; i.e. you only need to consider up to and including the square root of n. Once you have an a, you can trivially infer b.

You can set the upper limit to be d * d <= n rather than d <= sqrt(n) so obviating any computation of a square root. That will be marginally faster still.

answered Oct 09 '17 at 13:09

Bathsheba

231,907
34
361
483

lest take for example 28. – Perviz Mamedov Oct 09 '17 at 13:15
the divisors of 28 are 1,2,4,7,14,28. I have changed my code. but asnwer is wrong – Perviz Mamedov Oct 09 '17 at 13:16
n=28 for i in range(1,int(n**0.5)+1): if n%i==0: print(i) – Perviz Mamedov Oct 09 '17 at 13:18
answers are 1,2,4 – Perviz Mamedov Oct 09 '17 at 13:18
Yes, they are the `a` in the set. You need to compute `n / a` to add in the other pair. Then you're done! – Bathsheba Oct 09 '17 at 13:19
Just make sure you don't add the final element twice for the case where `n` is a prime number squared. E.g. 49. – Bathsheba Oct 09 '17 at 13:22

score 0 · Answer 2 · answered Oct 09 '17 at 13:47

You just want to know the number of divisors:

For any number N there are always an even number of divisors as every dividor x requires to be multiplied by another y that is itself a divisor of N except if x=sqrt(N) yileds an integer result as that would mean that x*x=N and that would be an only number. So every divisor is grouped in pairs except for sqrt(N) if it results to be a divisor.

Then you first check if the root is a divisor and then just calculate until it and add two to the count each time as the rest will always be pairs:

def number_of_divisors(n):
    root = math.sqrt(n)
    if root == int(root):
        number = 1
        limit = int(root)
    else:
        number = 0
        limit = int(root) + 1
    for i in range(1, limit):
        if (n % i) == 0:
            number += 2
    return number

i = 1
s = 1
while number_of_divisors(s) < 501:
    i += 1
    s += i

print(i) # 12375
print(s) # 76576500
print(number_of_divisors(s)) # 576

How can I make this code faster?

2 Answers2