判斷素數(shù)的C語言函數(shù)（詳解素數(shù)判定算法）

素數(shù)是指只能被1和本身整除的自然數(shù)，如2、3、5、7等。判斷一個數(shù)是否為素數(shù)是數(shù)學(xué)中的一個經(jīng)典問題，也是計算機編程中常見的問題之一。在C語言中，我們可以通過編寫函數(shù)來實現(xiàn)判斷素數(shù)的功能。

為素數(shù)，則返回true，否則返回false。

-1的所有數(shù)進(jìn)行除法運算，若有一個數(shù)可以整除，則該數(shù)不是素數(shù)。但是這種方法效率較低，特別是對于大數(shù)來說，時間復(fù)雜度過高，不適合實際應(yīng)用。

更為高效的算法是利用數(shù)學(xué)定理和特性來判斷素數(shù)。以下是兩種常見的素數(shù)判定算法

od p)。根據(jù)這個定理，我們可以用a^(p-1)模p來判斷p是否為素數(shù)。

基于試除法的實現(xiàn)

et) { false; // 小于等于1的數(shù)不是素數(shù)t遍歷 false; // 若有數(shù)能整除，則不是素數(shù)

} true; // 否則是素數(shù)

基于費馬小定理的實現(xiàn)

et) { false; // 小于等于1的數(shù)不是素數(shù)de(NULL)); // 初始化隨機數(shù)種子t i = 0; i< 5; i++) { // 隨機取5個數(shù)進(jìn)行測試td-1之間的隨機整數(shù) false; // 判斷是否滿足費馬小定理

} true; // 否則是素數(shù)

其中，powerMod函數(shù)用于計算a的b次方對c取模的結(jié)果，可以使用快速冪算法來實現(xiàn)。