# Simply Emirp(UVA10235)
## [程式繳交區](https://hackmd.io/@Renektonn/ByxsVyadye/edit)
## 題目
[點我](https://onlinejudge.org/external/102/10235.pdf)

## 解題網站
[UVA](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1176)
[ZJ](https://zerojudge.tw/ShowProblem?problemid=d387)

## 演算法1

1. 輸入n，若無法，則停止
2. 將n倒轉過來變成u，，判斷以下三種可能，輸出對應的結果

"N is not prime."，如果 N 不是一個質數
"n is prime."，如果 n 是一個質數，但是不是一個 Emirp
"n is emirp."，如果 n 是一個 emirp(u跟n不同，且u是質數)

## 程式碼1(TLE)

#include <bits/stdc++.h>
#define int long long int
using namespace std;

int isPrime (int n) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) cnt++;
    }
    return cnt == 2;
}

signed main() {
    int n;
    while (cin >> n) {
        string str = to_string(n);
        reverse(begin(str), end(str));
        int u = stoi(str);
        if (!isPrime(n)) {
            cout << n << " is not prime." << endl;
        } else if (u == n or !isPrime(u)) {
            cout << n << " is prime." << endl;
        } else {
            cout << n << " is emirp." << endl;
        }
    }
    return 0;
}

:::info
演算法太慢，要用篩法建質數表
:::

## 演算法2

1. 用篩法建質數表
2. 輸入n，若無法，則停止
3. 將n倒轉過來變成u，利用質數表判斷以下三種可能，輸出對應的結果

"N is not prime."，如果 N 不是一個質數
"n is prime."，如果 n 是一個質數，但是不是一個 Emirp
"n is emirp."，如果 n 是一個 emirp(u跟n不同，且u是質數)

## 程式碼2

#include <bits/stdc++.h>
#define int long long int
using namespace std;

signed main() {
    bitset <1000001> isPrime;
    isPrime.set();
    for (int i = 2; i <= 1001; i++) {
        if (isPrime[i]) {
            for (int j = 2 * i; j <= 1000000; j += i) {
                isPrime[j] = 0;
            }
        }
    }
    int n;
    while (cin >> n) {
        string str = to_string(n);
        reverse(begin(str), end(str));
        int u = stoi(str);
        if (!isPrime[n]) {
            cout << n << " is not prime." << endl;
        } else if (u == n or !isPrime[u]) {
            cout << n << " is prime." << endl;
        } else {
            cout << n << " is emirp." << endl;
        }
    }
    return 0;
}