• Virtual Judge
• ZeroJudge

題意

• 輸入一整數，輸出是否為質數或 Emirp
• 需要注意的有：
  1. 重複輸入一整數 N 直到 EOF
  2. 什麼是 Emirp
     • 顛倒後不能為同一個數字
     • 質數的顛倒後也是質數
     • e.g. 17 & 71
  3. 輸出格式
     • 不是質數：N is not prime.
     • 只是質數：N is prime.
     • 都是質數：N is emirp.

解法

• 透過 while 迴圈重複輸入整數 N

  int N, rev_N;
  
  while(scanf("%d", &N) != EOF){
      printf("%d ", N);
      ...
  }
  

• 用 for 迴圈檢查是否有可整除的因數，若有則代表質數，並更改 flag1 的狀態；為何迴圈跑到 sqrt(N)

  flag1 = true;
  
  for(i = 2; i <= sqrt((double)N); i++){
      if(N % i == 0){
          flag1 = false;
          break;
      }
  }
  

• 因為問題是連續的，所以如果已經判斷 N 為合數就不用再計算；若為質數就用 while 把 N 顛倒，並再判斷一次若顛倒後是同個數，根據題目要求要撇除此情況，所以就更新 flag2 的狀態

  if(flag1){
  
      int temp = N;
  
      while(temp > 0){
          rev_N = rev_N * 10 + temp % 10;
          temp = temp / 10;
      }
  
      if(rev_N == N){
          flag2 = false;
      }
      else{
          ...
      }
  }
  

• 同樣用 for 迴圈再檢查一次顛倒後的 rev_N 是否為質數

  for(i = 2; i <= sqrt((double)rev_N); i++){
      if(rev_N % i == 0){
          flag2 = false;
          break;
      }
  }
  

• 若用建表法先儲存好質數表，有可能比較快 (？)，這部分就讓大家試試囉
• C code

  #include<stdbool.h>
  #include<stdio.h>
  #include<math.h>
  
  int main(){
  
      int N, rev_N;
      bool flag1, flag2;
      int i;
  
      while(scanf("%d", &N) != EOF){
  
          printf("%d ", N);
  
          flag1 = true;
          flag2 = true;
          rev_N = 0;
  
          for(i = 2; i <= sqrt((double)N); i++){
              if(N % i == 0){
                  flag1 = false;
                  break;
              }
          }
  
          if(flag1){
  
              int temp = N;
  
              while(temp > 0){
                  rev_N = rev_N * 10 + temp % 10;
                  temp = temp / 10;
              }
  
              if(rev_N == N){
                  flag2 = false;
              }
              else{
                  for(i = 2; i <= sqrt((double)rev_N); i++){
                      if(rev_N % i == 0){
                          flag2 = false;
                          break;
                      }
                  }
              }
          }
  
          if(flag1 && flag2){
              printf("is emirp.\n");
          }
          else if(flag1){
              printf("is prime.\n");
          }
          else{
              printf("is not prime.\n");
          }
      }
  
      return 0;
  }