What is the most efficient way to find amicable numbers in python?

Question

I've composed code in Python to figure the amount of amicable numbers under 10000: 

def amicable(a, b):

   total = 0

   result = 0

   for i in range(1, a):

      if a % i == 0:

        total += i

   for j in range(1, b):

      if b % j == 0:

        result += j

   if total == b and result == a:

        return True

   return False

sum_of_amicables = 0

for m in range (1, 10001):

    for n in range (1, 10001):

        if amicable(m, n) == True and m != n:

            sum_of_amicables = sum_of_amicables + m + n

Code is running for over 20 minutes in Python 2.7.11. Is it alright? How might I improve it?

Answer 1

To efficiently find amicable numbers in Python, you can use the following approach:

1. Define a function that calculates the sum of proper divisors for a given number.
2. Iterate through a range of numbers and check if they form an amicable pair.
3. Store the amicable pairs in a list.
4. Return the list of amicable numbers.

Here's the Python code that implements these steps:

def sum_of_divisors(n):

    # Calculates the sum of proper divisors for a given number 'n'

    divisors_sum = 1

    for i in range(2, int(n**0.5) + 1):

        if n % i == 0:

            divisors_sum += i

            if i != n // i:

                divisors_sum += n // i

    return divisors_sum

def find_amicable_numbers(limit):

    amicable_numbers = []

    for num in range(2, limit + 1):

        sum_a = sum_of_divisors(num)

        sum_b = sum_of_divisors(sum_a)

        if num == sum_b and num != sum_a:

            amicable_numbers.append((num, sum_a))

    return amicable_numbers

limit = 10000  # Set the upper limit for the range of numbers to check

amicable_nums = find_amicable_numbers(limit)

print("Amicable numbers:")

for pair in amicable_nums:

    print(pair)

limit = 10000 # Set the upper limit for the range of numbers to check amicable_nums = find_amicable_numbers(limit) print("Amicable numbers:") for pair in amicable_nums: print(pair)

In this code, the sum_of_divisors function calculates the sum of proper divisors for a given number n. The find_amicable_numbers function iterates over a range of numbers from 2 to the specified limit, checking if a number forms an amicable pair. If a pair is found, it is added to the amicable_numbers list. Finally, the list of amicable numbers is printed.

Feel free to adjust the limit variable to define the range of numbers you want to check for amicable pairs.

Answer 2

Check the below code:

def sum_factors(n):  

     result = []

     for i in xrange(1, int(n**0.5) + 1):

         if n % i == 0:

             result.extend([i, n//i])

     return sum(set(result)-set([n]))

def amicable_pair(number):

    result = []

    for x in xrange(1,number+1):

        y = sum_factors(x)

        if sum_factors(y) == x and x != y:

            result.append(tuple(sorted((x,y))))

    return set(result)

Execute it:

start = time.time()

print (amicable_pair(10000))

print time.time()-start

Output:

set([(2620, 2924), (220, 284), (6232, 6368), (1184, 1210), (5020, 5564)])

0.180204153061

Join the python online course fast, to learn python concepts in detail and get certified.

For more details, do check out the below video tutorial...

Answer 3

Here's the Python code implementing the above steps:

def sum_of_divisors(n):

    divisors_sum = 1

    for i in range(2, int(n**0.5) + 1):

        if n % i == 0:

            divisors_sum += i

            if i != n // i:

                divisors_sum += n // i

    return divisors_sum

def find_amicable_numbers(limit):

    amicable_numbers = []

    for num in range(2, limit + 1):

        sum_a = sum_of_divisors(num)

        sum_b = sum_of_divisors(sum_a)

        if num == sum_b and num != sum_a:

            amicable_numbers.append((num, sum_a))

    return amicable_numbers

limit = 10000  # Set the upper limit for the range of numbers to check

amicable_nums = find_amicable_numbers(limit)

print("Amicable numbers:")

for pair in amicable_nums:

    print(pair)

In this code, we define the sum_of_divisors function that calculates the sum of proper divisors for a given number n. Then, the find_amicable_numbers function iterates over a range of numbers from 2 to the specified limit. It checks if a number forms an amicable pair by calculating the sums of divisors for both the number and its sum, and comparing them. If a pair is found, it is added to the amicable_numbers list. Finally, the list of amicable numbers is printed.

You can adjust the limit variable to change the range of numbers to check for amicable pairs.

Answer 4

To efficiently find amicable numbers in Python, follow these steps:

1. Define a function to calculate the sum of proper divisors for a given number.
2. Iterate over a range of numbers and check if they form an amicable pair.
3. Store the amicable pairs in a list.
4. Return the list of amicable numbers.

Here's the Python code:

def sum_of_divisors(n):

    # Calculates the sum of proper divisors for a given number 'n'

    divisors_sum = sum(i for i in range(1, n) if n % i == 0)

    return divisors_sum

def find_amicable_numbers(limit):

    amicable_numbers = [(num, sum_of_divisors(num)) for num in range(2, limit + 1)

                        if num == sum_of_divisors(sum_of_divisors(num)) and num != sum_of_divisors(num)]

    return amicable_numbers

limit = 10000  # Set the upper limit for the range of numbers to check

amicable_nums = find_amicable_numbers(limit)

print("Amicable numbers:")

for pair in amicable_nums:

    print(pair)

Adjust the limit variable to specify the range of numbers you want to check for amicable pairs.