UVA10235

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.

解法:埃拉托斯特尼篩法

import java.util.Scanner;

public class UVA10235 {

 public static int matrix[] = new int[1000000];

 public static void main(String[] args) {

  Scanner sc = new Scanner(System.in);

  StringBuilder sb = new StringBuilder();

  
  matrix[0] = 1;
  matrix[1] = 1;

  for (int i = 2; i < 1000000; i++) {

   if (matrix[i] == 0)
    for (int j = 2 * i; j < 1000000; j += i) {
     matrix[j] = 1;
    }

  }
  while (sc.hasNext()) {

   int num = sc.nextInt();

   String temp = Integer.toString(num);
   String t_num = "";
   int number = 0;

   for (int i = temp.length() - 1; i >= 0; i--)
    t_num += temp.charAt(i);

   number = Integer.parseInt(t_num);

   if (matrix[num] == 1)
    sb.append(num + " is not prime." + "\n");

   else if (matrix[number] == 0 && number != num)
    sb.append(num + " is emirp." + "\n");

   else
    sb.append(num + " is prime." + "\n");

  }

  System.out.print(sb);

  sc.close();
 }

}