Home » programming » Dividers of a number in Python

# Dividers of a number in Python

I looked it up a little bit and I didn’t find a solution in Python calculating fast enough all the prime dividers of a set of numbers. Moreover, I wanted to find all the dividers of a number.

Because I am not really fond to implementing the same algorithms every 1 or 2 years, I paste it here, for future reference. Probably, there is a faster way to compute all the dividers. If that’s the case, I am curious.

GREATEST = 10000

def rwh_primes(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns  a list of primes < n """
sieve = [True] * n
for i in range(3, int(n**0.5) + 1, 2):
if sieve[i]:
sieve[i * i::2 * i]=[False] * ((n-i*i-1)//(2*i)+1)
return [2] + [i for i in range(3,n,2) if sieve[i]]

PRIMES = rwh_primes(GREATEST)

def prime_dividers(num):
prime_factors = []
for prime in PRIMES:
if prime > num:
break
if num % prime == 0:
prime_factors.append(prime)
return prime_factors

def dividers(num):
factors = prime_dividers(num)
if factors[-1] == num:
factors.pop()

can_combine = factors[:]

for c in can_combine:
for f in factors:
if num % (f * c) == 0 and f * c < num:
factors.append(f * c)
else:
continue

factors.append(1)

return set(factors)

def are_amicable(num1, num2):
factors1 = dividers(num1)
factors2 = dividers(num2)

a = sum(factors1)
b = sum(factors2)

return (a == num2 and b == num1)

print(are_amicable(220, 284))