在C語言中,判斷一個數是否為素數(質數)的常用方法有兩種,分別是:
基礎版:從2到n-1挨個判斷是否能整除
基本思想是找到一個數n的因子時,判斷這個因子是不是 1 和 n 本身。如果一個數除了 1 和它本身之外沒有其他的因子,那么這個數就是素數。
我們可以用一個循環來判斷一個數是否為素數,即讓這個數從 2 開始循環到自己減去 1,判斷能否整除。
下面是基礎版判斷素數的函數實現:
int is_prime(int n) {
if (n <= 1) return 0; // 1不是素數
for (int i = 2; i < n; i++) {
if (n % i == 0) return 0; // 能整除,不是素數
}
return 1;
}
優化版:從2到sqrt(n)挨個判斷是否能整除
判斷一個數是否為素數的另一種優化方法是,只需要判斷該數能否被2到sqrt(n)之間的數整除,即可得出結論。這是因為如果存在大于sqrt(n)的因子p,那么一定存在一個小于sqrt(n)的因子q,使得p = n / q,反之依然成立。因此,只需要判斷2到sqrt(n)之間的數是否能整除n即可。
下面是優化版判斷素數的函數實現:
int is_prime(int n) {
if (n <= 1) return 0; // 1不是素數
int sqrt_n = (int)sqrt(n);
for (int i = 2; i <= sqrt_n; i++) {
if (n % i == 0) return 0; // 能整除,不是素數
}
return 1;
}
這里使用了 <math.h>頭文件中的 sqrt 函數來求出 n 的平方根,并將其轉型為整型。
需要注意的是,如果判斷的數很大,循環次數可能非常多,影響程序的性能。因此在實際應用中,需要對算法進行進一步優化。