Day 0x16 UVa10235 Simply Emirp

• 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;
  }