C語言判斷素數：試除法優化至 sqrt(n) 完整實作

素數定義

大於 1 的自然數，除 1 與自身外無其他因數。

優化試除法

1. 小於 2 非素數。
2. 2 是唯一偶數素數。
3. 排除偶數（`n%2==0`）。
4. 只檢查奇數除數：`3, 5, 7...` 至 `sqrt(n)`。

完整函式

#include 
#include 

bool is_prime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    int limit = (int)sqrt(n);
    for (int i = 3; i <= limit; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

主程式測試

int main() {
    int n;
    printf("Enter number: ");
    scanf("%d", &n);
    if (is_prime(n)) printf("%d is prime\n", n);
    else printf("%d is not prime\n", n);
    return 0;
}

進階優化：6k±1 法

大於 3 的素數皆為 `6k±1` 形式。迴圈步進 6，檢查 `i` 和 `i+2`。

for (int i = 3; i <= limit; i += 6) {
    if (n % i == 0 || n % (i+2) == 0) return false;
}

篩法（批量查詢）

若需判斷大量數字是否為素數，使用**埃拉托斯特尼篩法**預計算至上限，O(1) 查詢。

總結

判斷素數標準解：**試除至 `sqrt(n)` + 奇數優化**。`sqrt` 計算一次存變數，迴圈 `i+=2`。面試手寫此版本即可，補充 6k±1 或篩法作為進階加分項。