素数判断算法实现与优化技巧

1. 素数判断算法实现与优化

1.1 基础素数判断原理

素数判断是编程入门阶段的经典问题，也是理解循环和条件分支的绝佳案例。素数的定义是只能被1和它本身整除的自然数，根据这个定义我们可以直接推导出最基础的判断方法：

c复制int is_prime(int n) {
    if (n <= 1) return 0;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

这个基础版本虽然直观，但存在明显的效率问题。当n很大时（比如10^9量级），循环次数会变得非常多。

注意：在实现素数判断时，必须处理n≤1的特殊情况，因为数学上素数定义在大于1的自然数范围内。

1.2 算法优化思路

实际编程中我们可以通过数学知识进行优化：

1. 范围优化：只需检查2到√n之间的整数即可。因为如果n能被某个大于√n的数整除，那么商必定小于√n，这就意味着我们已经在之前检查过这个因数了。

2. 偶数优化：除了2以外，所有偶数都不是素数，可以单独处理。

优化后的代码如下：

c复制int is_prime_optimized(int n) {
    if (n <= 1) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return 0;
    }
    return 1;
}

1.3 多组输入处理技巧

在实际编程题目中，通常需要处理多组输入。C语言中可以使用以下模式：

c复制int main() {
    int T;  // 测试用例数量
    scanf("%d", &T);
    
    while (T--) {
        int n;
        scanf("%d", &n);
        if (is_prime_optimized(n)) {
            printf("yes\n")