7. 10001번째 소수를 찾아

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^th prime is 13.

What is the 10001^st prime number?

첫 여섯개의 소수를 나열하면 2, 3, 5, 7, 11, 13 이다. 우리는 6번째 소수가 13이란 걸 안다.

10001번째 소수를 찾아라

#include <stdio.h> #include <math.h> #include <string.h> #include <time.h> int prime[10002]; int is_prime_0(int a) //소수목록으로 확인 { int i; for(i=1; prime[i]; i++) if(a%prime[i]==0) return 0; return 1; } int is_prime_1(int a) //포인터로 접근 { int *p; for(p=prime+1; *p; p++) if(a % (*p) == 0) return 0; return 1; } int is_prime_2(int a) //제곱근a까지만 확인 { int i, sqrn=(int)sqrt(a); for(i=3; i<=sqrn; i+=2) if(a%i==0) return 0; return 1; } int main() { int way, i, j; int (*fptr[3])(int); clock_t start, end; fptr[0]=is_prime_0; fptr[1]=is_prime_1; fptr[2]=is_prime_2; prime[1]=2; for(way=0; way<3; way++) { memset(prime+2, 0, sizeof(int)*10000); //prime[2]부터 prime[10001]까지 0으로 start=clock(); for(i=3, j=2; j<10002; i+=2) { if(fptr[way](i)) prime[j++]=i; } end=clock(); printf("10001번째 소수는 %d\n", prime[10001]); printf("%f초\n", (double)(end-start) / CLOCKS_PER_SEC); } return 0; }

소수목록으로 확인하는 방법이  많이 느리네요.

포인터 접근은 빠를 때도 있고 느릴 때도 있는데 왜이런거죠 ㅋㅋ