基於C的素數計算小程序及優化詳情 - 後端,c,知識 BlackQid 動態日志

質數（英文名：Prime number）又稱素數，是指在大於1的自然數中，除了1和它本身以外不再有其他因數的自然數。質數又稱素數。

以100~200之間的素數計算為例，通過以下C語言程序可以很容易地實現。需要包含頭的文件有stdio.h。

#include<stdio.h>

int main()
{
    int i = 0;
    for (i = 100; i <= 200; i++)
    {
        //判斷i是否為素數
        //產生2~i-1的數字，去試除i
        int flag = 1;//假設i是素數
        for (int n = 2; n <= i - 1; n++)
        {
            if (i % n == 0)
            {
                flag = 0;//i不可能是素數
                break;
            }
        }
        if (flag)//是素數
        {
            printf("%d ", i);
        }
    }
    return 0;
}

接下來，為進一步優化程序，我們可以運用如下兩條數學性質：

對於任意兩個正實數a和b,若a x b = c,則a ≤ √c或b ≤ √c(即至少有一個數不超過√c)。如果在2~√c都沒有找到能整除i的數，則i是素數。

偶數不可能是素數。

因此，修改內部for循環的判斷條件為n <= sqrt(i)；外部for循環為for (i = 101; i <= 200; i+=2)。需要包含頭的文件有stdio.h和math.h。

sqrt() 是 C 標準庫math.h中的一個函數，用於計算一個非負數的平方根。

#include<stdio.h>
#include<math.h>

int main()
{
    int i = 0;
    for (i = 101; i <= 200; i+=2)
    {
        //判斷i是否為素數
        //產生2~i-1的數字，去試除i
        int flag = 1;//假設i是素數
        for (int n = 2; n <= sqrt(i); n++)
        {
            if (i % n == 0)
            {
                flag = 0;//i不可能是素數
                break;
            }
        }
        if (flag)//是素數
        {
            printf("%d ", i);
        }
    }
    return 0;
}

如此一來，有效減少了內外層循環需要執行的次數。

<font style="color:rgb(38, 38, 38);">正文完</font>

（素數）https://baike.baidu.com/item/%E8%B4%A8%E6%95%B0/263515

（C 庫函數 - sqrt()）https://www.runoob.com/cprogramming/c-function-sqrt.html