n번째 소수 구하기

$K$번째 소수를 구하는 문제: 15965번 문제: K번째 소수

$n$번째 소수를 구하는 방법에는 여러 가지가 있습니다. $i=2$부터 시작해서 각 양의 정수의 약수 개수를 구한 다음, 만약 두 개이면 소수이라는 성질을 이용하거나, 에라토스테네스의 체를 이용할 수도 있습니다. 수학동아 기사에 의하면 $n-1$번째 소수를 알고 있을 때, $n$번째 소수를 찾는 점화식(아래의 점화식)이 발견되었다고 합니다. 아래의 점화식으로 $f_{n}$의 값을 계산한 다음, 그 값의 정수 부분이 $n$번째 소수인 $P_{n}$이 됩니다.

$$f_{1}=\lim_{n\rightarrow\infty} \sum_{k=1}^n \frac{P_{k}-1}{P_{1} \times P_{2} \times \cdots \times P_{k-1}} \fallingdotseq 2.920050977316 \cdots (단, P_{n}=[f_{n}])$$ $$f_{n}=[f_{n-1}] \times (f_{n-1}-[f_{n-1}]+1)$$

단, $[x]$$x$의 정수부분, 즉 $x$보다 크지 않은 최대의 정수를 의미합니다. 그리고, 위의 시그마($\sum$)에서 $k=1$일 때 $\frac{P_{k}-1}{P_{1} \times P_{2} \times \cdots \times P_{k-1}}$의 값은 1입니다.

그럼 $K$번째 소수 문제를 이 방법을 해결할 수 있을까요? 이 점화식을 사용한다면, 반복문 한 개로 풀 수 있습니다. C 언어로 소스코드를 구현해 보면, 아래와 같습니다.

#include <stdio.h>

double a[500001]={0.0, 2.920050977316};

int main(void)
{
    int k, i;

    scanf("%d" ,&k);

    for(i=2; i<=k; i++)
        a[i]=((int)a[i-1])*(a[i-1]-((int)a[i-1])+1.0);

    printf("%d" ,(int)a[k]);
    return 0;
}

(직접 실행해 보시고 싶은 분은 이 링크에서 실행해 보시기 바랍니다.)

이 프로그램을 실행하고, 2를 입력합니다. 2번째 소수인 3이 출력됩니다.

이번에는 3을 입력합니다. 3번째 소수인 5가 출력됩니다.

5를 입력합니다. 5번째 소수인 11이 출력됩니다.

12를 입력합니다. 12번째 소수인 37이 출력됩니다.

그 다음에는 13을 입력합니다. 하지만, 13번째 소수인 41이 출력되지 않고, 심지어 소수도 아닌 40이 출력됩니다. 왜 그럴까요?

소스코드를 보면, 약간 의심이 가는 부분이 있을 수 있습니다. 바로 a[1]의 값입니다. a[1]의 값을 $f_{1}$의 대략적인 값인 2.920050977316으로 정의했습니다. 이 값이 부정확하기 때문에 오류가 발생하는 것입니다. 그럼 어떻게 해야 할까요?

점화식의 초기값을 변형하면 될 것 같다고 생각해서 $f_{1}$의 값을 $n=14$일 때까지 계산을 해 보니, 1 + 2 ÷ 2 + 4 ÷ 6 + 6 ÷ 30 + 10 ÷ 210 + 12 ÷ 2310 + 16 ÷ 30030 + 18 ÷ 510510 + 22 ÷ 9699690 + 28 ÷ 223092870 + 30 ÷ 6469693230 + 36 ÷ 200560490130 + 40 ÷ 7420738134810 + 42 ÷ 304250263527210 ≒ 2.92005097731613입니다. 이 값을 a[1]에 넣고 프로그램을 다시 실행해봅니다.

이전 소스에서 문제가 되었던 13을 입력합니다. 이제는 13번째 소수인 41이 출력됩니다!

기대되는 마음으로 이번에는 14를 입력합니다. 아쉽게도 43이 출력되지 않습니다. ㅠㅠ 초기값이 더 정확해야 합니다. 다음에는 초기값을 프로그램 내에서 계산하는 방법으로 소스코드를 작성해 보겠습니다.

궁금하신 점이나 요청하시고 싶은 부분은 이 글의 댓글로 달아 주시거나, Slack DM(@eric00513)으로 보내주시기 바랍니다.

댓글 (7개) 댓글 쓰기


sait2000 5달 전

이 방법은 본질적으로 소수사이의 간격이 베르트랑의 공준에 따라 그리 멀지 않다는 점을 이용해서 그냥 무한정밀도 실수에 모든 소수를 올린 겁니다. 예를 들어 앞의 다섯개 소수 2, 3, 5, 7 ,11을 1107050302의 한 자연수로 표현한 다음 100으로 나눈 나머지를 구하고 100을 나눈 몫을 대입하는 과정을 반복하는 식으로요. 물론 이 공식에서는 100대신 계속 변하는 값을 이용하고, 좀 다른 방법의 식이 사용된다는 차이가 있겠네요.


eric00513 5달 전

네 감사합니다. 연구를 더 많이 해 보아야겠네요.


sohnryang 5달 전

음.. 부동소수점 실수 정밀도 오류가 생기면 문제되지 않을까요?


eric00513 5달 전

네 맞습니다. 부동소수점 오류도 해결해야 하는데, 그 문제보다는 시간 문제($O(n)$)이 더 중요한 것 같다고 생각되어서 부동소수점은 생각하지 않고 코드를 작성하는 중입니다.


kipa00 4달 전

n번째 소수를 구하는 시간 O(n^(2/3)) 알고리즘이 있습니다(Meissel-Lehmer). 참고하시기 바랍니다.


sait2000 4달 전

키파님 팬이에요


eric00513 4달 전

@kipa00

<충격>헉 이런 것이 있는지도 몰랐네요... 저저저정말 감사합니다~