CPE 一顆星選集 49 道必考題
題目連結:https://zerojudge.tw/ShowProblem?problemid=d387
內容
定義 ‘emirp’ 為｢本身是和反過來都是質數的數。
給定一個整數 N (1 < N < 1000000)，判斷此數，是否為質數、是否為 ‘emirp’。
範例輸入
17
18
19
179
199
131
範例輸出
17 is emirp.
18 is not prime.
19 is prime.
179 is emirp.
199 is emirp.
131 is prime.
想法
先把1000000內是否為質數的結果存入陣列(建質數表)。
若 N 為質數，判斷是否為 ‘emirp’。
程式碼
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
| #include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define mxn 1000000
using namespace std;
bool sieve[mxn];
void prime_judge();
int main(){
fastio;
prime_judge();
int N, temp;
string s;
stringstream ss;
while(cin >> N){
if(sieve[N]){
cout << N << " is not prime.\n";
continue;
}
ss << N;
ss >> s;
reverse(s.begin(), s.end());
ss.str(""), ss.clear();
ss << s;
ss >> temp;
ss.str(""); ss.clear();
if(!sieve[temp] && N != temp) cout << N << " is emirp.\n";
else cout << N << " is prime.\n";
}
}
void prime_judge(){
sieve[0] = sieve[1] = true;
for(long long int i = 2; i < mxn; ++i){
if(!sieve[i]){
for(long long int j = i*i; j < mxn; j += i){
sieve[j] = true;
}
}
}
}
|