(Java) Project Euler 021 - 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.

import java.util.ArrayList;

public class ProjectEuler_021 {
    public static void main(String[] args) {
        ArrayList<Integer> sums = new ArrayList<>();

        // 2부터 10000까지 모든 수에 대해 처리
        for (int i = 2; i <= 10000; i++) {
            int sum = GetSum(i); // 현재 수의 진약수의 합을 계산
            int theOther = GetSum(sum); // 진약수의 합의 진약수의 합을 계산

            // 친화적인 수인지 확인
            if (i == theOther && sum != theOther) {
                sums.add(sum); // 친화적인 수라면 리스트에 추가
            }
        }

        System.out.println(sums.toString());

        int result = 0;

        // 모든 친화적인 수의 합 계산
        for (int i = 0; i < sums.size(); i++) {
            result += sums.get(i);
        }

        System.out.println("The result is : " + result);
    }

    // 주어진 수의 진약수를 반환하는 메서드
    static ArrayList<Integer> GetDivisors(int num) {
        ArrayList<Integer> divisors = new ArrayList<>();

        // 1부터 제곱근까지의 수 중에서 나누어 떨어지는 수를 찾아 진약수로 추가
        for (int i = 1; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                divisors.add(i);
                if (i != 1) {
                    divisors.add(num / i);
                }
            }
        }

        return divisors;
    }

    // 주어진 수의 진약수의 합을 반환하는 메서드
    static int GetSum(int num) {
        ArrayList<Integer> arr = GetDivisors(num);

        int sum = 0;

        // 진약수의 합을 계산
        for (int i = 0; i < arr.size(); i++) {
            sum += arr.get(i);
        }

        return sum;
    }
}

 

 

Amicable Number가 뭔지 몰라도,

어떤 정수의 약수(진약수)를 구할 수 있고, 그 합을 구할 수 있다면 풀 수 있는 문제.