c 判断一个数是不是质数

判断一个数是否为质数是一个常见的编程任务，特别是对于学习算法基础的学生来说。质数是指只有1和它本身两个正因数的自然数。以下是判断一个数n是否为质数的一种简单方法：

1. **基本条件**：0和1不算质数，因为它们没有除1以外的因子。

2. **循环检查**：从2开始，一直检查到该数的平方根（√n）。如果n能被其中任何一个数整除，那么n就不是质数。这是因为如果有大于√n的因子，那么必然有一个小于等于√n的因子与其对应。

以下是一个简单的C语言函数示例，用于判断一个数是否为质数：

#include <stdbool.h>
#include <math.h>

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    if (n == 2 || n == 3) {
        return true;
    }
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

这个函数首先排除了2和3这两个特例，然后跳过了所有能被2或3整除的数，接着从5开始，每次加6（即检查6k±1的形式），因为除了2和3之外，所有的质数都可以表示成6k±1的形式，这样可以大大减少计算量。