C 언어 예제, n 번째 소수 찾기. Project Euler 7번

사실 소수 찾는 글은 이전에도 한번 올린 적이 있다. 이 문제를 접하게 되어 그 때랑 얼마나 다른지 좀 살펴봤는데 좀 다르더라.

그래서 그냥 올리기로 했다.

사실 문제 자체는 10001 번째 소수를 찾는거지만.... 그냥 하면 값 조정에 따라 n 번째 소수를 찾을 수 있다.

우선 간단히 설명하자면....

어차피 짝수는 2 말고는 소수 아니니까 찾을 필요 없고

작은 수로 나눠지면 소수 아니니까 바로 쳐내면 된다.

코드는 아래와 같다.

#include <stdio.h>

int main()

{

int num=5, counter=3, divider;

for(;;)

{

for(divider=3;divider<num;divider = divider+2)

{

if(num % divider == 0)

{

if(num == divider)

{

counter++;

printf("%d 번째 소수, %d \n", counter, num);

break;

}

else

{

break;

}

}

else

{

if(divider>=num/3)

{

counter++;

printf("%d 번째 소수, %d \n", counter-1, num);

break;

}

}

}

num=num+2;

if(counter==10002)

{

break;

}

}

printf("the answer is, %d \n", num-2);

return 0;

}