神奇的素数 75063692618249
bcdmwSjy
·
·
个人记录
我们注意到，75063692618249 是第 2428095424619 个素数。
而 2428095424619 正好也是一个素数，容易发现，它是第 88362852307 个素数。
显而易见，88362852307 还是一个素数，它是第 3657500101 个素数。
接下来，3657500101 又是一个素数，它是第 174440041 个素数 （有完没完了）
你应该猜到下面的内容了。
$9737333$ 是第 $648391$ 个素数。
$648391$ 是第 $52711$ 个素数。
$52711$ 是第 $5381$ 个素数。
$5381$ 是第 $709$ 个素数。
$709$ 是第 $127$ 个素数。
$127$ 是第 $31$ 个素数。
$31$ 是第 $11$ 个素数。
$11$ 是第 $5$ 个素数。
$5$ 是第 $3$ 个素数。
$3$ 是第 $2$ 个素数。
$2$ 是第 $1$ 个素数。
啊，终于写完了，累死我了。
要找到它们也很简单，只需要使用下面的代码即可。
输入 $1$ 查找下一个，$0$ 退出程序。
温馨提示：算最后一个时可能有些慢，耐心等待一下即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int isqrt(ll x) {
return sqrt(x+0.9);
}
ll ML(ll n){
if (n<=1) return 0;
if (n==2) return 1;
int lim=isqrt(n);
int siz=(lim+1)>>1;
vector<int> small(siz),rough(siz);
vector<ll> large(siz);
vector<bool> np(lim+1);
for (int i=0;i<siz;i++){
small[i]=i;
rough[i]=i<<1|1;
large[i]=(n/rough[i]-1)>>1;
}
int cnt=0;
for (int i=3;i<=lim;i+=2){
if (np[i]) continue;
ll i2=i*i;
if (i2*i2>n) break;
np[i]=true;
for (int j=i2,k=i<<1;j<=lim;j+=k) np[j]=true;
int ns=0;
for (int j=0;j<siz;j++){
ll curr=rough[j];
if (np[curr]) continue;
ll d=curr*i;
large[ns]=large[j]-(d<=lim?large[small[d>>1]-cnt]:small[(n/d-1)>>1])+cnt;
rough[ns++]=curr;
}
siz=ns;
for (int j=(lim-1)>>1,k=(lim/i-1)|1;k>=i;k-=2){
int curr=small[k>>1]-cnt;
for (int l=(k*i)>>1;l<=j;j--) small[j]-=curr;
}
cnt++;
}
ll ans=large[0]+(ll(siz+((cnt-1)<<1))*(siz-1)>>1);
for (int i=1;i<siz;i++) ans-=large[i];
for (int i=1;i<siz;i++){
int q=rough[i];
ll m=n/q,e=small[(m/q-1)>>1]-cnt;
if (e<i+1) break;
ll t=0;
for (int j=i+1;j<=e;j++) t+=small[(m/rough[j]-1)>>1];
ans+=t-(e-i)*(cnt+i-1);
}
return ans+1;
}
ll nth_prime(ll n){
if (n==0) return 0;
if (n==1) return 2;
if (n==2) return 3;
if (n==3) return 5;
if (n==4) return 7;
if (n==5) return 11;
ll l=n*log(n),r=n*log(n)+n*log(log(n)),ans=0;
while (l<=r){
ll mid=(l+r)>>1;
if (ML(mid)>=n){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
return ans;
}
int main() {
ll x=1;
while (true){
x=nth_prime(x);
cout<<x<<"\n";
int op;
cin>>op;
if (op==0) break;
}
return 0;
}
```