---
# System prepended metadata

title: UVA 10235 Simply Emirp

---

# UVA 10235 Simply Emirp
##  題目連結 [UVA 10235](https://vjudge.net/problem/UVA-10235)
### 題目內容
An integer greater than 1 is called a prime number if its only positive divisors (factors) are 1 and itself. Prime numbers have been studied over the years by a lot of mathematicians. Applications of prime umbers arise in Cryptography and Coding Theory among others.

Have you tried reversing a prime? For most primes, you get a composite (43 becomes 34). An Emirp (Prime spelt backwards) is a Prime that gives you a different Prime when its digits are reversed. 

For example, 17 is Emirp because 17 as well as 71 are Prime. 
In this problem, you have to decide whether a number N is 
Non-prime or Prime or Emirp. Assume that 1 < N < 1000000.

Interestingly, Emirps are not new to NTU students. We have been boarding 199 and 179 buses for quite a long time!
### 輸入限制
Input consists of several lines specifying values for N.
### 輸出限制
For each N given in the input, output should contain one of the following:
1. ‘N is not prime.’, if N is not a Prime number.
2. ‘N is prime.’, if N is Prime and N is not Emirp.
3. ‘N is emirp.’, if N is Emirp.
### 解題思路
1.先建大小為1000005的質數表
2.先把數字當字串讀取，利用==stoi==轉換為整數型別
3.先判斷是否為質數，若是就翻轉確認是否為質數，需要注意的是若翻轉後與翻轉前相同就視為prime，若翻轉後仍是質數，則是emirp
### 程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int prime[1000005];
void Prime(){
    for(int i=0;i<1000005;i++){
        prime[i]=1;
    }
    prime[0]=0;
    prime[1]=0;
    for(int i=0;i<1000005;i++){
        if(prime[i]==1){
            for(int j=i+i;j<1000005;j+=i){
                prime[j]=0;
            }
        }
    }
}
int main(){
    Prime();
    string n;
    while(cin>>n){
        long long a=stoi(n);
        if(prime[a]==0){
            cout<<n<<" is not prime."<<endl;
        }
        else{
            string s=n;
            reverse(s.begin(),s.end());
            if(s==n){
                cout<<a<<" is prime."<<endl;
                continue;
            }
            long long b=stoi(s);
            if(prime[b]==0){
                cout<<a<<" is prime."<<endl;
            }
            else{
                cout<<a<<" is emirp."<<endl;
            }
        }
    }
}
```
## 測資
### Sample input
17
18
19
179
199
### Sample output
17 is emirp.
18 is not prime.
19 is prime.
179 is emirp.
199 is emirp.
##  中文題目連結 [zerojudge d387](https://zerojudge.tw/ShowProblem?problemid=d387)