a121. 質數又來囉

題目連結

https://zerojudge.tw/ShowProblem?problemid=a121

解題思路

本題給的測資較大，因此我們必須盡可能減少不必要的運算，避免出現TLE的情形。

首先，質數的定義是除了1與自己以外，沒有其他因數的數字。因此在檢查該數是否有因數的時候不用檢查1，可以直接從2開始。

再來，除了完全平方數的因數是1、自己和自己的根號共三個以外，所有數字的因數都是兩兩成對，其中一個小於自己的根號，一個大於自己的根號。因此，我們在檢查該數是否有因數的時候，不必真的逐一檢查到底，只需檢查到該數的根號就好。

最後，我們的目標在於判斷該數是否有因數，進而判斷其是否為質數，而不是找出該數所有的因數。因此，只要找到一個因數，就可以直接跳出迴圈，換下一個數字了。

注意事項

質數的定義是除了1與自己以外，沒有其他因數的數字。1不是質數也不是合數!

程式碼：C語言

#include <stdio.h>
#include <math.h>
int main() {
    //宣告變數a、b，代表檢查的上下界
    int a,b;
    //使用EOF寫法判斷程式執行的條件
    while(scanf("%d%d", &a, &b) != EOF) {
        //宣告變數ans，代表a到b之間質數的數量
        int ans = 0;
        for(int num = a ; num <= b ; num++) {
            //宣告變數test，設初始值為0，代表該數為質數
            int test = 0;
            /*因為除了完全平方數另有一個因數是自己的根號以外，
              基本上所有數字的因數都是兩兩成對，
              因此可以只檢查到該數的根號就好*/
            for(int i = 2 ; i <= ceil((int)sqrt(num)) ; i++)
                //只要該數有找到一個因數，就將test令為1，然後直接結束此輪檢查
                if(num%i == 0) {
                    test++;
                    break;
                }
            //若test經檢查後仍為0，代表該數為質數
            if(test == 0)
                ans++;
        }
        if(a == 1 || b == 1) //1不是質數也不是合數，因此若a、b為1需將之扣除
            ans--;
        printf("%d\n", ans);
    }
    return 0;
}