iT邦幫忙

2021 iThome 鐵人賽

DAY 22
0
自我挑戰組

用 C & C++ 帶你手把手解 UVa 一顆星選集系列 第 22

Day 0x16 UVa10235 Simply Emirp

題意

  • 輸入一整數,輸出是否為質數或 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 為合數就不用再計算;若為質數就用 whileN 顛倒,並再判斷一次若顛倒後是同個數,根據題目要求要撇除此情況,所以就更新 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;
    }
    

上一篇
Day 0x15 UVa10056 What is the Probability ?
下一篇
Day 0x17 UVa10252 Common Permutation
系列文
用 C & C++ 帶你手把手解 UVa 一顆星選集30

尚未有邦友留言

立即登入留言