(Java) Project Euler 007 - 10001st Prime

// By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
// What is the 10001st prime number?

 

-- 가장 작은 수부터 6개의 소수를 나열해보자 : 2, 3, 5, 7, 11, 13.

-- 6번째 소수는 13이다.

-- 10001번째 소수는 무엇인가?

 

public class ProjectEuler_007 {
    public static void main(String[] args) {

        int primeCount = 0;                             //  1)
        int startPrime = 2;                             //  2)

        while (primeCount < 10001) {                    //  3)
            if (PrimeCheck(startPrime)) {
                primeCount += 1;                        //  4)
            }
            startPrime += 1;                            //  5)
        }

        int result = startPrime - 1;                    //  6)

        System.out.println("The 10001st Prime number is " + result);
    }


    static boolean PrimeCheck(int num) {
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

1) primeCount를 0으로 초기화함.

 

2) startPrime은 2부터 시작.

 

3) primeCount가 10001보다 작을 때 while 루프. ( 10001이면 루프 중단. )

 

4) primeCheck해서 prime(소수)이면 primeCount를 1 증가시킴.

 

5) 다음 수를 체크하기 위해 startPrime을 1 증가시킴.

 

6) 최종적으로 while 루프가 끝났을 때에는 결과를 나타낼 startPrime에 1이 더해져있는 상황이므로, 1을 빼준다.

---

소수 체크를 할 때, 짝수(2의 배수)는 2를 제외하고는 전부 소수가 아니기 때문에, 루프에서 증가 값을 1이 아닌 2로 해줘서 모든 홀수에 대해서만 소수 체크를 하면 훨씬 효율적으로 할 수 있을거같음.