相信大家都對質數這種特殊的正整數不陌生: 一個大於1的自然數中，除了1和此整數自身外，沒辦法被其他自然數整除的數；
即只有兩個正因數（1和自己）的自然數，就是質數。
如果一個質數在將其所有位數顛倒(reverse)後仍是一個質數，那麼我們就稱這個數是「Emirp」(中文譯作「反質數」)，
而這個名字的由來也很容易能理解。(Emirp 正是質數的英文 Prime 反過來書寫的結果)
※舉例來說:
17 是質數，而將其每位數反轉後我們得到 71 ，而 71 恰好也是質數。因此，17 是一個 Emirp。
同理，71 也必然是 Emirp 。
--
現在，請你寫一個程式，找出由小到大數來第 n 個 Emirp 是哪個數。
(注意 : 在這個問題中，3, 5, 7, 11, 191 這類「迴文質數」由於反轉前後的結果一樣，因此我們不將其視為 Emirp。)
$$1\leq N\leq 100,000$$
本機爆搜後發現第10000個Emirp是11293973，直接蓋表，為了rever方便所以就蓋到1e8
原本想說這複雜度蠻可怕的，且本機的確跑了好幾秒，不過丟到OJ上是好的
…難道我該換電腦了嗎
用$O(n)$篩不知道為什麼會出事，還沒找到原因
$O(nlogn)$卻好好的@@
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define mem(i,j) memset(i,j,sizeof (i));
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define lowbit(x) ((x)&(-(x)))
#define siz(v) (long long)(v).size()
typedef int64_t ll;
typedef uint64_t ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
const int MAXN = 2e5+9;
#define int ll
int rever(int a) {
int b = 0;
while(a) {
b*=10;
b+=a%10;
a/=10;
}
return b;
}
const int N = 100000000;
bitset<N> isP;
signed main() {
EmiliaMyWife
vector<int> p;
isP[0]=isP[1]=1;
for(int i = 2; i < N; i++) {
if(isP[i]) continue;
for(int j = i*i; j < N; j+=i) isP[j]=1;
}
vector<int> ans;
for(int i = 1; i<N; i++) {
int k = rever(i);
if(k!=i && !isP[i] && !isP[k]) ans.pb(i);
}
int t, n;
cin >> t;
while(t--) {
cin >> n;
cout << ans[n-1] << '\n';
}
return 0;
}
|