Processing math: 100%

2013. 11. 14.

Project Euler - 문제 7번

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?

 문제 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가 걸렸네요. 이것도 사실 긴 시간이긴 합니다만, 저는 일단 만족합니다.


댓글 없음:

댓글 쓰기