Problem G: Simply Emirp
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 numbers 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
Input consists of several lines specifying values for N.
Output
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.
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.
Notes:
1.判斷是否為質數，若為質數則回傳1，不是質數則回傳0
/*return value: 1=prime, 0=not prime*/
int is_prime(int *n){
int num,i,result=0;
num=*n;
// num == 2: 2 is prime.
// num > 2: num is even, num is not prime.
if(num%2==0){
//printf("**[%d]\n",__LINE__);
(num==2)?(result=1):(result=0);
return result;
}
for(i=3;i*i<=num;i+=2){
//printf("**[%d]\n",__LINE__);
if(num%i==0){
//printf("**[%d]\n",__LINE__);
result=0;
return result;
}
//printf("**[%d]\n",__LINE__);
}
result=1;
return result;
}
2.整數轉字串、字串反轉、字串轉整數
#include <string.h>
int input,rev_input;
int value;
char temp[7];
char *rev_temp;
value=is_prime(&input);
sprintf(temp,"%d",input);
rev_temp=strrev(temp);
rev_input=atoi(rev_temp);
3.debug專用，顯示行號的標籤"__LINE__"
printf("**[%d]\n",__LINE__);
4.利用兩個三元運算子(條件運算子 conditional operator)，化簡三選一的if else
三選一: if(value==1)
printf("%d %s\n",input,PRIME);
else if(value==2)
printf("%d %s\n",input,EMIRP);
else
printf("%d %s\n",input,NOT_PRIME);
利用兩個條件運算子化簡:
printf("%d %s\n",input,(value>1)?(EMIRP):((value<1)?NOT_PRIME:PRIME));
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define PRIME "is prime."
#define NOT_PRIME "is not prime."
#define EMIRP "is emirp."
/*return value: 1=prime, 0=not prime*/
int is_prime(int *n){
int num,i,result=0;
num=*n;
// num == 2: 2 is prime.
// num > 2: num is even, num is not prime.
if(num%2==0){
(num==2)?(result=1):(result=0);
return result;
}
for(i=3;i*i<=num;i+=2){
if(num%i==0){
result=0;
return result;
}
}
result=1;
return result;
}
int main(void){
int input,rev_input;
int value;
char temp[7];
char *rev_temp;
while(scanf("%d",&input)!=EOF){
value=0;
value=is_prime(&input);
sprintf(temp,"%d",input);
if(value>0){
rev_temp=strrev(temp);
rev_input=atoi(rev_temp);
value+=is_prime(&rev_input);
}
if(value!=0 && input==rev_input)
value--;
printf("%d %s\n",input,(value>1)?(EMIRP):((value<1)?NOT_PRIME:PRIME));
