n번째 소수 공식
게시글 주소: https://orbi.kr/00064764677
소수를 찾아내는 알고리즘에 가깝고, 단순히 1을 (n번째 소수 - 1)번 더하도록 만든거라 비효율적이긴 합니다.
윗부분이 잘린 대괄호처럼 생긴 녀석은 바닥 함수(Floor Function)인데, 가우스함수와 똑같이 크지 않은 최대의 정수를 반환하는 함수입니다. 저 표기가 표준이라 해외에서는 다 그렇게 쓰는데 이상하게 한국에서만 대괄호를 가져다가 씁니다.
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
윌런스 공식
공식이 능사는 아니다라는걸 보여주기 위한 일종의 수학적 유머죠
실제로 윌런스도 이 공식을 수학을 교육의 재밌는 이야기를 다루는 저널에 투고 했죠
가우스 저게 국룰이제
이..이게뭐노
컴퓨터로 계산하려니 저 공식으로 열거하면 O(4^n)일뿐만아니라 부동소수점 연산까지 들어가서 매우 큰 정밀도가 필요해서 여러모로 비효율적이죠.. 더불어서 정수론적으로 아무런 의미도 없죠 컴퓨터로 계산한다면 차라리 \pi(n) ~ n/lgn 이용해서 n번째 소수는 에라토스테네스 체나 선형 체나 아킨 체같은 sieve를 이용하여 약 O(nlgn)에 찾거나 Meissel-Lehmer 알고리즘을 통해 pi를 정확히 계산하는걸로 이진 탐색을 이용하여 O(x^{2/3+eps}lg^2 n)에 찾는 방법이 있죠