[51nod 1181] 质数中的质数

如果一个质数，在质数列表中的编号也是质数，那么就称之为质数中的质数。例如：3 5分别是排第2和第3的质数，所以他们是质数中的质数。现在给出一个数N，求>=N的最小的质数中的质数是多少（可以考虑用质数筛法来做）。

Solution

拿个筛子来筛筛然后暴力统计就可以了

我居然被 \(0\) 卡掉了，我是智障

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2000005;

int prime[MAXN+1]; // Note: Let prime[0] donate the number of primes

// Note: the array "prime" has two different roles in the algorithm

int isp[MAXN+1];

void presolve() {

    memset(prime,0,sizeof prime);

    for(int i=2;i<=MAXN;i++) {

        if(!prime[i]) prime[++prime[0]]=i;

        for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++) {

            prime[prime[j]*i]=1;

            if(i%prime[j]==0) break;

        }

    }

}

signed main() {

    presolve();

    int n,ans=-1;

    cin>>n;

    for(int i=1;i<=prime[0];i++) {

        isp[prime[i]]=1;

        if(isp[i]) ans=prime[i];

        if(ans>=n) break;

    }

    cout<<ans;

}

巴特西

[51nod 1181] 质数中的质数 - 筛法

Solution

最新文章

热门文章