(Java) Project Euler 003 - Largest Prime Factor

 

// The prime factors of 13195 are 5, 7, 13 and 29.
// What is the largest prime factor of the number 600851475143?

 

Question)

-- 13195의 소인수는 5, 7, 13, 29 이다.

-- 600851475143의 가장 큰 소인수는 무엇인가?

 

public class ProjectEuler_003 {
    public static void main(String[] args) {
        long num = 600851475143L;                           //  2)

        ArrayList<Long> divisors = new ArrayList<>();

        for (long i = 2; i < Math.sqrt(num); i++) {         //  3)
            if (num % i == 0) {                             //  4)
                divisors.add(i);
                divisors.add(num / i);                      //  5)
            }
        }

        ArrayList<Long> primeFactors = new ArrayList<>();   //  6)

        for (int i = 0; i < divisors.size(); i++) {
            long l = divisors.get(i);

            if (primeCheck(l)) {                            //  7)
                primeFactors.add(l);
            }
        }

        long result = getMax(primeFactors);                 //  8)

        System.out.println("The Largest Prime Factor of " + num + " is " + result);

    }

    public static boolean primeCheck(long num) {
        for (long i = 2; i <= Math.sqrt(num); i++) {        //  7-1)
            if (num % i == 0) {                             //  7-2)
                return false;
            }
        }
        return true;
    }

    public static long getMax(ArrayList<Long> longs){
        long max = Long.MIN_VALUE;                          //  8-1)

        for (Long l : longs){                               //  8-2)
            if (max < l) {
                max = l;
            }
        }

        return max;
    }
}

 

1) 인수와 소인수를 저장할 Data structure로 ArrayList를 선택함.

배열은 초기화할 때 크기를 정해야 하는데 인수와 소인수의 개수를 알 수 없는 상태에서 배열 초기화가 불가능하기 때문.

 

2) 수의 자료형으로 long을 선택함. 

Integer는 +2,147,483,647까지 표현이 가능하고, Long은 9,223,372,036,854,775,807까지 가능함.

Long을 초과하는 범위의 수는 BigInteger로 계산이 가능하긴 함.

 

3) 인수를 구하는 과정. 어떤 수의 인수는 제곱근에 대하여 대칭성을 가지고 있기 때문에, 모든 인수에 대해서 체크할 필요가 없다.

예를들어 64의 인수를 구한다 하면 : 2, 4, 8, 16, 32가 될 것인데, 8(64의 제곱근)을 가운데에 두고 각각 4 * 16, 2 * 32가 64의 인수가 되기 때문에, 2부터 제곱근까지만 루프를 돌리면 될 일이다.

 

4) i가 num의 인수인지 체크하기.

 

5) i로 나누어진다면, i로 나눈 몫도 num의 인수가 됨.

 

6) 인수 중에 소수를 담을 ArrayList를 새로 초기화함.

 

7) 어떤 인수가 소수인지를 확인하는 메서드 호출.

 

7-1) 어떤 수가 소수인지를 확인하려면, 그 수의 인수가 있는지 확인하면 됨. 마찬가지로 2부터 모든 수에 대해 루프를 돌릴 필요가 없이, 제곱근까지만 루프를 돌려도 인수가 있는지 없는지 체크할 수 있음.

 

7-2) 어떤 수에 대해서 i의 인수를 가지고 있다면 false반환, 그렇지 않다면 true 반환.

 

8) 소인수를 담은 ArrayList에서 최대값을 구하는 메서드 호출.

 

8-1) 최대값을 우선 최소값으로 초기화함. (여기서 구하는 소인수는 2이상의 양의 정수이기 때문에 1로 초기화 해도 문제 없다.)

 

8-2) C#의 foreach와 같은 용법으로 for (Long l : longs)를 사용함.

 

---

7-1의 루프를 돌릴 때, 처음에 for (long i = 1; i < Math.sqrt(num); i++)로 기준을 잡았었다.

소수체크를 1로 시작하면 전부 다 false (모든 수는 1로 나누기가 가능함!) 가 되어서 primeFactors에 아무 값도 들어가지 않는다.