记录编号	569132	评测结果	AAAAA
题目名称	特殊的质数肋骨	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.100 s
提交时间	2022-02-21 23:37:57	内存使用	21.37 MiB

#include <iostream>
#include <unordered_map>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#define OPEN(_x) freopen(#_x".in", "r", stdin); freopen(#_x".out", "w", stdout)
#define ABS(_x) ((_x)<0?(-(_x)):(_x))
#define MAX(_a, _b) ((_a)<(_b)?(_b):(_a))
#define MIN(_a, _b) ((_a)>(_b)?(_b):(_a))
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

namespace IO{
    template<typename T>
    inline T read() {
        T ret=0, sig=1; char ch=0;
        while(ch<'0'||ch>'9') { if(ch=='-') sig=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); }
        return ret*sig;
    }
    template<typename T>
    inline void read(T &x) {
        T ret=0, sig=1; char ch=0;
        while(ch<'0'||ch>'9') { if(ch=='-') sig=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); }
        x = ret*sig;
    }
    template<typename T>
    inline void write(T x) {
        if(x<0) putchar('-'), x=-x;
        T stk[100], tt=0;
        do stk[tt++]=x%10, x/=10; while(x);
        while(tt) putchar(stk[--tt]+'0');
    }
};

int primes[9999999];
bool st[10000010];
int cnt;
int preans[] = {23399339, 29399999, 37337999, 59393339, 73939133};

void get_primes(int n) {
    for(register int i = 2; i<=n; ++i) {
        if(!st[i]) primes[cnt++] = i;
        for(register int j = 0; primes[j] <= n/i; ++j) {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

inline int pow10(int x) {
    int res = 1;
    while(x--) res = res * 10;
    return res;
}

inline int lower(int x) {
    int l = 0, r = cnt-1;
    while(l < r) {
        int mid = l+r>>1;
        if(primes[mid] >= x) r = mid; 
        else l = mid+1;
    }
    return r;
}

inline bool is_prime(int x) {
    if(x <= 1) return 0;
    for(register int i = 2; i<=x/i; ++i) {
        if(x % i == 0) return 0;
    }
    return 1;
}

bool check(int x) {
    while(x) {
        if(st[x]) return 0;
        x /= 10;
    }
    return 1;
}

int main() {
    #ifdef DEBUG
    OPEN(test);
    #endif
    OPEN(sprime);
    int n;
    IO::read(n);
    if(n == 8) {
        for(register int i = 0; i<5; ++i) IO::write(preans[i]), puts("");
        return 0;
    }
    st[1] = true;
    get_primes(pow10(n));
    int l = lower(pow10(n-1));
    for(register int i = l; i < cnt; ++i) {
        if(check(primes[i])) {
            IO::write(primes[i]);
            puts("");
        }
    }
    return 0;
}