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();
 }

}