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;
}
</math.h></stdio.h>
兩段代碼的輸出結果相同。


第一次運行結果：

輸入一個整數：1 1是素數。
第二次運行結果：

輸入一個整數：97 97是素數。
第三次運行結果：

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