Problem 21(Amicable numbers)

Problem 21(Amicable numbers)

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

 

In python:

# PE21(Amicable numbers)
import time

def div(n):
    return sum([d for d in range(1, n) if n % d == 0])

startTime = time.time()
listAmi = []
for i in range(1, 10001):
    j = div(i)
    k = div(j)
    if i == k and i != j:
        listAmi.append(i)
print(sum(listAmi))
print(time.time() - startTime, "seconds")

Run time: 6.8222270011901855 seconds

 

In Java:

//Euler21 Amicable numbers
package project_euler21_30;

public class Euler21 {
	public static int div(int n) {
		int sum = 0;
		for (int i = 1; i < n; i++) {
			if (n % i == 0) {
				sum += i;
			}
		}
		return sum;
	}
	public static void main(String[] args) {
		long startTime = System.currentTimeMillis();
		int sum = 0;
		for (int i = 1; i < 10001; i++) {
			if (i == div(div(i)) && i != div(i)) {
				sum += i;
			}
		}
		System.out.println(sum);
		long endTime = System.currentTimeMillis();
		System.out.println((double)(endTime - startTime) / (double)1000 + "seconds");
	}
}

Run time: 0.282seconds

 

Solution: 31626