1181质数中的质数

//垃圾版本
#include<iostream>
#include<cstring>
#include<cmath> 
using namespace std;
const int MAXN = 1000034;//1000034是1000000之后的第二个素数 
struct shu{
	int a1[MAXN];//存放1-1000034之间的素数 
	int a2[MAXN];//上述素数的下表从0开始 
	bool a3[MAXN];//数组下标中的素数 
}; 
bool isprime[MAXN];
int prime[MAXN];
int cnt = 0;//保存素数个数
int count=0;
int z;
shu a;
void getprime()//第一次筛
{
	for(int i=0;i<MAXN;i++)
	{
		a.a3[i]=true;
	}
	for(int i=2;i<MAXN;i++)
	{
		if(!a.a3[i])
		{
			continue;
		}
		z=cnt;
		a.a1[cnt++]=i;
//		a.a2[count++]=z;
		for(int j=2*i;j<MAXN;j+=i)
		{
			a.a3[j]=false;
		}
	}
}
void getprime(int b)//第二次筛下标
{
	for(int i=1;i<b;i++)
	{
		a.a3[i]=true;
		a.a2[i]=i;
	}
	for(int i=2;i<b;i++)
	{
		if(!a.a3[i])
		{
			continue;
		}
		//z=cnt;
//		a.a2[count++]=i;
//		a.a2[count++]=z;
		for(int j=2*i;j<b;j+=i)
		{
			a.a3[j]=false;
		}
	}

}
int main()
{
	int n,j;
	cin>>n;
	getprime();
	getprime(cnt);
	bool s[cnt];
	for(int i=1;i<cnt;i++)
	{
		j=i-1;//因为是从1开始计数的，不是从0开始。 
		s[j]=a.a3[i];
	}
	for(int i=0;i<cnt+100;i++)
	{
//		if(a.a3)
//		{
//			cout<<a.a1[i]<<"  "<<a.a2[i]<<" "<<s[i]<<endl;
//		}
	
		if(a.a1[i]>=n&&s[i])
		{
			cout<<a.a1[i]<<endl;
			return 0;
		}
	}
	 return 0;
}
//超级版本
#include <cstdio>
#include <algorithm>
char  f[1001001];
int  prime[80000];
int  cnt = 0;

void  sieve( int x ) {
        for( int i = 2; i <= x; ++i ) {
                if( !f[i] ) {
                        prime[cnt++] = i;
                        if( i < 1002 ) for( int j = i * i; j <= x; j += i ) f[j] = 1;
                }
        }

}

int main() {
        int  n, pos;
        scanf( "%d", &n );
        sieve( n + 1000 );
        pos = std::upper_bound( prime, prime + cnt, n - 1 ) - prime;
        pos = std::upper_bound( prime, prime + cnt, pos ) - prime;
        printf( "%d\n", prime[prime[pos]-1] );

        return 0;
}


//喜欢版
//思路与垃圾版一样但代码很简练
#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <set>
#include <stack>
#include <stdlib.h>
#include <time.h>

using namespace std;

bool f[1000509];

int main()
{
    int N, num = 1;
    cin>>N;
    int n = N+500;
    for(int i=2;i<n;++i)
        f[i] = 1;
    f[1] = 0;
    for(int i=1;i<n;++i)
    {
        if(f[i])
        {
            if(i>=N && f[num])
            {
                cout<<i<<endl;
                break;
            }
            int t = i<<1;
            while(t < n)
            {
                f[t] = 0;
                t += i;
            }
            f[i] = num++;
        }
    }
    return 0;
}