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

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

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

原因：因為如果 m 能被 2 ~ m-1 之間任一整數(shù)整除，其二個因子必定有一個小于或等于 ，另一個大于或等于 。例如 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;  // 素數(shù)的個數(shù)
    int num=0;  // 輸入的整數(shù)
 
    printf("輸入一個整數(shù)：");
    scanf("%d",&num);
 
    for(int i=2;i<num;i++){
        if(num%i==0){
            a++;  // 素數(shù)個數(shù)加1
        }
    }
 
    if(a==0){
        printf("%d是素數(shù)。\n", num);
    }else{
        printf("%d不是素數(shù)。\n", num);
    }
 
    return 0;
}
思路2)的代碼：

#include <stdio.h>
#include <math.h>
void main(){
    int m;  // 輸入的整數(shù) 
    int i;  // 循環(huán)次數(shù)
    int k;  // m 的平方根 
    printf("輸入一個整數(shù)：");
    scanf("%d",&m);
    // 求平方根，注意sqrt()的參數(shù)為 double 類型，這里要強制轉(zhuǎn)換m的類型 
    k=(int)sqrt( (double)m );
    for(i=2;i<=k;i++)
        if(m%i==0)
            break;
    // 如果完成所有循環(huán)，那么m為素數(shù)
    // 注意最后一次循環(huán)，會執(zhí)行i++，此時 i=k+1，所以有i>k 
    if(i>k)
        printf("%d是素數(shù)。\n",m);
    else
        printf("%d不是素數(shù)。\n",m);
    return 0;
}
</math.h></stdio.h>
兩段代碼的輸出結(jié)果相同。


第一次運行結(jié)果：

輸入一個整數(shù)：1 1是素數(shù)。
第二次運行結(jié)果：

輸入一個整數(shù)：97 97是素數(shù)。
第三次運行結(jié)果：

輸入一個整數(shù)：10 10不是素數(shù)。