(Java) Project Euler 023 - Non-Abundant Numbers

// A perfect number is a number for which the sum of its proper divisors is exactly equal to the number.
// For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

// A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

// As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24.
// By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers.
// However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

// Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

 

import java.util.ArrayList;
import java.util.HashSet;

public class ProjectEuler_023 {
    public static void main(String[] args) {
        // 과잉수(Abundant), 완전수(Perfect), 결핍수(Deficient)를 저장할 리스트 생성
        ArrayList<Integer> Abundants = new ArrayList<>();
        ArrayList<Integer> Perfects = new ArrayList<>();
        ArrayList<Integer> Deficients = new ArrayList<>();

        // 2부터 28123까지의 수에 대해 과잉수, 완전수, 결핍수를 구분
        for (int i = 2; i <= 28123; i++) {
            if (i < GetSum(i)) {
                Abundants.add(i);
            } else if (i > GetSum(i)) {
                Deficients.add(i);
            } else if (i == GetSum(i)) {
                Perfects.add(i);
            }
        }

        // HashSet을 사용하여 중복된 과잉수 합을 방지
        HashSet<Integer> abundantSumHash = new HashSet<>();

        // 1부터 28123까지의 모든 수를 포함하는 리스트 생성
        ArrayList<Integer> numArr = new ArrayList<>();
        for (int i = 1; i < 28123; i++) {
            numArr.add(i);
        }

        // 모든 가능한 두 개의 과잉수 합을 구하여 HashSet에 저장
        for (int i = 0; i < Abundants.size(); i++) {
            int num_1 = Abundants.get(i);
            for (int j = 0; j < Abundants.size(); j++) {
                int num_2 = Abundants.get(j);
                int sum = num_1 + num_2;
                if (sum <= 28123) {
                    abundantSumHash.add(sum);
                }
            }
        }

        // 결과 리스트에 저장된 수들의 합을 계산하여 출력
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < numArr.size(); i++) {
            if (!abundantSumHash.contains(numArr.get(i))) {
                result.add(numArr.get(i));
            }
        }

        // 결과 리스트 출력
        System.out.println(result);

        // 결과 리스트에 저장된 수들의 합을 계산하여 출력
        int sumResult = 0;
        for (int i = 0; i < result.size(); i++) {
            sumResult += result.get(i);
        }
        System.out.println(sumResult);
    }

    // 주어진 수의 약수를 찾아내는 함수
    static ArrayList<Integer> GetDivisors(int num) {
        ArrayList<Integer> divisors = new ArrayList<>();
        for (int i = 1; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                divisors.add(i);
                if (i != 1 && i != num / i) {
                    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;
    }
}

 

번역을 어떻게 해야할 지 몰라서 맘대로 했다.

 

일단 문제에 제시된 정수 28123보다 작은 완전수 (Abundant number)를 전부 구한 다음,

중복을 허용하지 않는 리스트인 HashSet을 사용하여 모든 합을 리스트화 했다.