Project Euler Problem7

Problem7.

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?

나의 풀이)

10001번째 소수를 구하는 것.

일단 소수인지를 확인하는 bool isPrime(int num); 함수를 구현했다.

생각한 것이.

 

bool flag = true;

    for (int i = 2; i<num; i++) {
        if (num%i == 0) {
            flag = false;
            break;
        }
    }
    return flag;
}

일단 이렇게 짜면 너~~~무 느리다. 성능을 올릴 방법을 생각해보다가 소수는 모두 홀수!


if (num%i == 0 || num%2 == 0)

이프문에 짝수를 제외하니 확실히 답을 빠르게 찾았다.
소수 찾아내는 더 좋은 알고리즘이 있나 찾아봤지만 별다른건 찾지 못했다.