10001st prime
Problem 7
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 10 001st prime number?
What is the 10 001st prime number?
문제 7번 : 처음 6개의 소수를 나열하면: 2, 3, 5, 7, 11, 그리고 13, 여기서 6번째 소수는 13임을 알 수 있다. 그러면 10,001번째 소수는 얼마인가?
단순하게 소수를 찾는 문제입니다. 소수를 찾아내는 방법은 여러 가지가 있겠지만 가장 무난하면서도 쉬운 방법은 임의의 숫자를 그 전의 숫자들로 모조리 나누어 보는 방법이지요. 다만 이 방법은 시간이 오래 걸리는 것이 단점입니다. 빠른 속도를 원하시면 위키피디아 같은 곳에서 소수를 찾는 더 좋은 수학적인 방법을 검색해 볼 수도 있습니다.
저는 짝수는 제외하고 오직 홀수만 테스트 해 보았습니다. 그렇게 하면 전체적인 프로세스를 1/4까지 줄일 수 있습니다. 그리고 임의의 숫자 i를 j로 나누어 가면서 j를 1씩 증가시킬 것인데, 여기서 j를 꼭 i까지 증가시킬 필요는 없습니다. 왜냐하면 소인수의 특성상 1부터 √i까지만 i%j == 0인지 체크를 해주면 그 위의 부분은 저절로 체크가 되기 때문에, 중복해서 체크를 할 필요가 없습니다. 그래서 이런 방식으로 다시 프로세스를 간편화 시킬 수 있습니다.
#include <iostream> #include "time.h" using namespace std; int main() { clock_t start = clock(); int i,j; int nprime = 1; // I will skip 1st prime number 2. for(i = 3; nprime < 10001; i += 2) { if(i%2 ==0) break; for(j = 3; j*j < i; j +=2) { if(i%j == 0) break; } if(j*j > i) nprime++; } clock_t end = clock(); cout << "Result : " << i-2 << endl; cout << "Time : " << (long double)(end-start)/CLOCKS_PER_SEC; return 0; }
여기서 sqrt 대신에 j를 제곱해서 체크를 했습니다. 만약에 j의 제곱이 i보다 작을 때 나누어 떨어지는 숫자가 하나도 없었다면 i라는 숫자는 소수라는 뜻이 됩니다. 그래서 for문이 끝나면서 j = j+2가 되고 if문에서 j의 제곱이 i보다 커지기 때문에 조건문으로 이 소수가 몇 번째 소수인지 체크를 하면서 10,001번째 소수를 찾는 것입니다.
결과 출력에 i-2라고 적었는데 이것은 for문을 탈출하면서 i가 2가 증가하기 때문에 원래 우리가 for문 안에서 찾은 소수 i를 출력하려면 다시 2만큼 빼 주어야 합니다. 이것 때문에 고생했네요;
처음에 무식하게 돌렸을 때는 1초도 넘게 걸렸는데, 조건을 잘 주고 나니까 9ms가 걸렸네요. 이것도 사실 긴 시간이긴 합니다만, 저는 일단 만족합니다.
댓글 없음:
댓글 쓰기