給定一個素數，能否確定它是第幾個素數？

如358723134241

Meissel - Lehmer 公式^[1]

其中

解遞歸可以求出

時間複雜度是

空間複雜度是

THE MEISSEL, LEHMER, LAGARIAS, MILLER, ODLYZKO METHOD

這篇文章宣稱他們的時空複雜度是和

參考

^https://mathoverflow.net/questions/297785/prime-counting-meissel-lehmer-is-there-a-general-formula

這裡解釋一個比較樸素的思路，可以認為是 @醬紫君老師給出公式的低配版，是二潘《初等數論》上計算（它表示不超過的素數個數）的方法，由勒讓德第一個發現。

利用集合的文氏圖可以直觀的看出，對於任意兩個有限集，有

以及對任意三個有限集，有

可以用數學歸納法證明其一般形式，對於任意個有限集成立

這就是所謂容斥原理。

我們利用這個原理導出的計算方法（僅考慮的情形）。如果我們知道了的值，並知道不超過的個素數為，我們如何計算不超過的素數個數呢？記集合

，

它表示的就是以內的正整數中，素數的倍數構成的集合。於是集合就是以內的正整數中能同時被整除的那些數構成的集合（），自然有

這是因為

設，則不超過的正整數中，能被整除的恰好有個，即。
同時被若干個數整除等價於被這些數的最小公倍數整除。
若干素數的最小公倍數即它們的乘積。

到此，就可以利用容斥原理計算了，也就是以內的正整數中至少能被其中之一整除的數的個數。之後，在正整數中，除了這個非素非合的異類，集合之外的數一定是（大於的）素數，這是因為不超過的合數一定有不超過的素因數。而包含了，因為它們都是自身的倍數。這樣，不超過的素數個數就是

於是，我們只要知道以內有多少素數，以及這些素數都是什麼，就可以求以內有多少素數。

能，時間問題。

如果考慮時間問題，不能。

當然，你給的這個很簡單，是第14032817002個素數。

當然可以啊，從2開始按次序把素數一個一個找出來不就行了。

用循環查找

要麼查表要麼篩，沒什麼好辦法吧

可以。

但是我懶得寫程序。

答案： wolframalpha: 14032817002

C++代碼：

#include& using namespace std; typedef long long LL; const int N = 1e6+2; LL L[N],R[N]; LL pi(LL n){ LL rn = (LL)sqrt(n+0.2); for(LL i=1;i&<=rn;++i) R[i]=n/i-1; LL ln = n/(rn+1)+1; for(LL i=1;i&<=ln;++i) L[i]=i-1; for(LL p=2;p&<=rn;++p){ if(L[p]==L[p-1]) continue; for(LL i=1,tn=min(n/(p*p),rn);i&<=tn;++i){ R[i] -= (i*p&<=rn?R[i*p]:L[n/(i*p)])-L[p-1]; } for(LL i=ln;i&>=p*p;--i){ L[i] -= L[i/p]-L[p-1]; } } return R[1]; } int main(){ LL n; while(cin&>&>n){ cout&