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))
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: