CODEWITHSUNDEEP
pythonif-statementwhile-loop
Ricardo Ferreira
Ricardo Ferreira

Reputation: 1

Hot to get all possible divisors in python

I would like to know, how I can add up all possible divisors of a number in python without the given number itself. For example, all possible divisors of the number 36 are 1, 2, 3, 4, 6, 9, 12 and 18. When you add them up, you should get a total of 55. I would like to know how to get these divisors with a while loop.

I have tried the following code:

def sum_divisors(n):
    sum = 0
    divisor = 2
    while n % divisor == 0:
        if n == 0:
            return 0
        print(n / divisor)
        divisor += 1
print(sum_divisors(36))

When I excecute this code I only get the number 18, 12, and 9. After these numbers I get "None". I think my problem is, when I execute this code the divisor will add 1 as long as the condition ist "True". But when the programm have to divide 36 / 5 the remainder is 1 and the code will no longer be excecuted because the condition is "False". So I tried to fix this problem with the following code:

def sum_divisors(n):
    sum = 0
    divisor = 2
    while n % divisor == 0:
        if n == 0:
            return 0
        if n % divisor == 1:
            divisor += 2
        print(n / divisor)
        divisor += 1
print(sum_divisors(36))

But this code din't work either. Do you have some tips how I can fix this problem. I only want to have tips and not suggested solutions. I am aware that I still need to find a code on how to add everything up. But I will surely be able to solve this problem. ;)

Upvotes: 0

Views: 1178

Answers (6)

Alain T.
Alain T.

Reputation: 42139

You could adapt a prime factorisation algorithm to build a set of divisors (exclude the number itself from the result if needed):

def getDivs(N):
    factors = {1}
    maxP  = int(N**0.5)        # largest possible prime factor
    p,inc = 2,1                # candidate divisors (primes)
    while p <= maxP:           # up to √(remaining N)
        while N%p==0:
            factors.update([f*p for f in factors]) # expand divisors
            N //= p                                # reduce N
            maxP = int(N**0.5)                     # new max prime
        p,inc = p+inc,2                            # next divisor
    if N>1:
        factors.update([f*N for f in factors])     # ultimate prime
    return factors - {max(factors)}                # exclude number itself

output:

getDivs(36)
{1, 2, 3, 4, 6, 9, 12, 18}

sum(getDivs(36))
55

getDivs(1001001001)
{1, 7, 762377, 11, 13, 77000077, 143, 91000091, 1313, 1415843, 
 9901, 69307, 1000001, 707, 7000007, 128713, 11000011, 77, 
 13000013, 143000143, 1111, 91, 7777, 101, 9191, 1001, 14443, 
 101101, 108911, 9910901, 900991}

sum(getDivs(1001001001))
356444375

If you don't need to list the divisors themselves and are only looking for their sum, you can get it in O(√N) time in a comprehension:

def divSum(N):
   return sum(sum({d,N//d}) for d in range(2,int(N**0.5)+1) if N%d == 0) + 1

divSum(36)          # 55
divSum(1001001001)  # 356444375

Upvotes: 0

Bharel
Bharel

Reputation: 26961

I highly suggest using the generator approach. We generate all possible divisors and then sum them. It will allow you to get the individual divisors as well:

import math
from typing import Iterator

def iter_divisors(n: int, /) -> Iterator[int]:
    """Iterate over the divisors of a given integer."""
    if n == 0:
        yield 0
        return

    sqrt = math.sqrt(n)

    # math.ceil explanation:
    # If sqrt is a whole number, we check everything until sqrt.
    # Else, we check everything until the closest integer from below.
    for i in range(1, math.ceil(sqrt)):
        if n % i == 0:
            yield i
            yield n // i
    
    # If the sqrt is whole, yield it only once (6 instead of 6,6 in 36)
    if sqrt.is_integer():
        yield int(sqrt)

Then you can sum it:

>>> print(sum(iter_divisors(36)))
91

Keep in mind it includes both 1 and n. You can subtract them if needed:

>>> print(sum(iter_divisors(36)) - 36)
55

Upvotes: 1

BanAnn
BanAnn

Reputation: 169

One possibility is to first get a list separately (in that case I called this method ' divisor_nums'). It contains all possible numbers that can be divided by, for example, '36'.

# // Get all possible numbers that can be devided
def divisor_nums(num: int) -> list:
    return [x for x in range(num) for y in range(num) if x * y == num]
    # ... 2, 3, 4, 6, 9, 12, 18 (with 36)

In the second section I iterate all numbers from the above list with a counter. In the comparison, list[i] == list[i] = 0. Well, maybe not the best option, but possibly one of many.

def sum_divisors(num):
    sum = 0
    i = -1
    lst = divisor_nums(num)

    while lst[i] % lst[i] == 0:
        sum += lst[i]
        i += 1
        if i >= len(lst)-1:
            break

    return sum


print(divisor_nums(36))
print(sum_divisors(36))

PS: The divisor_nums() function is only optional. You can also include this list directly in the sum_divisors function

Upvotes: 0

Gowdham V
Gowdham V

Reputation: 634

This will work for your case.

def sum_divisors(n):
    sum = 0
    divisor = 1
    while divisor<n:
        if n%divisor == 0:
            sum+= divisor
        divisor += 1
    return sum
    
print(sum_divisors(36))

Upvotes: 0

Bibhav
Bibhav

Reputation: 1757

Code:

def sum_divisors(num):
    Sum=0
    n=1
    while n<=(num//2):
        if num%n==0:
            Sum += n
        n += 1
    return Sum

print(sum_divisors(36))

Output:

55

Upvotes: 0

Adon Bilivit
Adon Bilivit

Reputation: 27315

How about a for loop:

def sum_divisors(n):
    ds = 1
    for i in range(2, (n//2)+1):
        if n % i == 0:
            ds += i
    return ds


print(sum_divisors(36))

Output:

55

Upvotes: 0

Related Questions