Project Euler Problem7

2015. 2. 5. 20:48프로그래밍/알고리즘

728x90
728x90

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)

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








728x90
반응형

'프로그래밍 > 알고리즘' 카테고리의 다른 글

Project Euler Problem16  (0) 2015.02.24
Project Euler Problem15  (0) 2015.02.17
Project Euler Problem10  (0) 2015.02.15
Project Euler Problem9  (0) 2015.02.15
Project Euler Problem5  (0) 2015.02.12
Project Euler Problem6  (0) 2015.02.05
Project Euler Problem4  (0) 2015.01.25