[Project Euler] Problem 021

 

 

public class Problem021 {
    public static void main(String[] args) {
        System.out.println(run());
    }
    
    public static String run() {
        int sum = 0;
        int b = 0;
        
        for(int a = 2; a <= 10000; ++a) {
            if(!isPrime(a)) {
                b = d(a);
                
                if((b != a) && (d(b) == a)) {
                    sum += a;
                }
            }
        }
        
        return Integer.toString(sum);
    }
    
    public static int d(int num) {
        int sum = 1;    
        int root = (int)(Math.sqrt(num));
        
        for(int i = 2; i <= root; ++i) { 
            if(num%i == 0) { 
                sum += (i + num/i);
            }
        }
    
        return sum;
    }
    
    public static boolean isPrime(int num) {
        if(num <= 1) {
            return false;
        } else if(num == 2) { 
            return true;
        } else {
            if(num % 2 == 0) {
                return false;
            } else {
                for (int i = 3; i*i <= num; i += 2) {
                    if (num % i == 0) {
                        return false;
                    }
                }
                
                return true;
            }
        }
    }
    
}

 

정답: 31626

실행 시간: 0.015초

 

n이 소수일 때 d(n)의 값은 무조건 1이므로 소수의 친화쌍은 존재할 수 없다.

따라서 소수는 제외한다.

또한 d(n)의 값을 구하는 과정은 √n까지만 반복함으로써 반복 횟수를 줄였다.

 

예를 들어 268의 약수는 다음과 같다.

 

1, 2, 4, 67, 134, 268

 

그리고 일반적으로 약수를 구할 때는 양 끝 값부터 쓴다.

이 방법으로 268의 약수를 찾는 방법은 다음과 같다.

 

1

1            268

1 2          268

1 2      134 268

1 2 4    134 268

1 2 4 67 134 268

 

 d(num) 의 값을 구할 때  i 는 1, 2, 4가 되고   num/i 는 67, 134, 268이 된다.

따라서  √n 까지만 반복하면서  sum += (i + num/i) 를 하면  d(num) 의 값을 구할 수 있다.

 

 d  메소드를 제외하고 핵심적인 연산은 다음과 같다.

 

for(int a = 2; a <= 10000; ++a) {

    if(!isPrime(a)) {

        b = d(a);

 

        if((b != a) && (d(b) == a)) {

            sum += a;

        }

    }

}

 

 a 가  368 이라고 하자.

 b 에는  d(368) 의 값인  367 이 저장된다.

따라서  368 != 367 이지만  d(367) != 368 이므로 이는 친화수에 포함되지 않는다.

 

이번에는 a 가  220 이라고 하자.

 b 에는  d(220) 의 값인  284 가 저장된다.

따라서  284 != 220 이고  d(284) == 220 이므로 이는 친화수에 포함된다.