C語言判斷素數（求素數）（兩種方法）

素數又稱質數。所謂素數是指除了 1 和它本身以外，不能被任何整數整除的數，例如17就是素數，因為它不能被 2~16 的任一整數整除。

思路1)：因此判斷一個整數m是否是素數，只需把 m 被 2 ~ m-1 之間的每一個整數去除，如果都不能被整除，那麼 m 就是一個素數。

思路2)：另外判斷方法還可以簡化。m 不必被 2 ~ m-1 之間的每一個整數去除，只需被 2 ~ 之間的每一個整數去除就可以了。如果 m 不能被 2 ~  間任一整數整除，m 必定是素數。例如判別 17 是是否為素數，只需使 17 被 2~4 之間的每一個整數去除，由於都不能整除，可以判定 17 是素數。

原因：因為如果 m 能被 2 ~ m-1 之間任一整數整除，其二個因子必定有一個小於或等於 ，另一個大於或等於 。例如 16 能被 2、4、8 整除，16=2*8，2 小於 4，8 大於 4，16=4*4，4=√16，因此只需判定在 2~4 之間有無因子即可。

兩種思路的程式碼請看解析。

思路1) 的程式碼：

#include <stdio.h>

int main(){
    int a=0;  // 素數的個數
    int num=0;  // 輸入的整數

    printf("輸入一個整數：");
    scanf("%d",&num);

    for(int i=2;i<num;i++){
        if(num%i==0){
            a++;  // 素數個數加1
        }
    }

    if(a==0){
        printf("%d是素數。n", num);
    }else{
        printf("%d不是素數。n", num);
    }

    return 0;
}

思路2)的程式碼：

#include <stdio.h>
#include <math.h>
void main(){
    int m;  // 輸入的整數 
    int i;  // 迴圈次數
    int k;  // m 的平方根 

    printf("輸入一個整數：");
    scanf("%d",&m);

    // 求平方根，注意sqrt()的引數為 double 型別，這裡要強制轉換m的型別 
    k=(int)sqrt( (double)m );
    for(i=2;i<=k;i++)
        if(m%i==0)
            break;

    // 如果完成所有迴圈，那麼m為素數
    // 注意最後一次迴圈，會執行i++，此時 i=k+1，所以有i>k 
    if(i>k)
        printf("%d是素數。n",m);
    else
        printf("%d不是素數。n",m);

    return 0;
}

兩段程式碼的輸出結果相同。

第一次執行結果：

輸入一個整數：1
1是素數。

第二次執行結果：

輸入一個整數：97
97是素數。

第三次執行結果：

輸入一個整數：10
10不是素數。