C语言实现素数判断与优化算法详解-嵌云网-嵌入式AI开发资源站

C语言实现素数判断与优化算法详解

蝨孨槑黽

1. 素数判断的基本概念与数学原理

素数（Prime Number）是数学中最基础也最重要的概念之一。在计算机编程中，素数判断常被用作入门练习，因为它既包含了基础语法，又涉及算法优化。我们先从数学定义开始：

素数是指大于1的自然数，除了1和它本身外，不能被其他自然数整除。换句话说，素数只有两个正因数：1和它自己。例如2、3、5、7都是素数，而4（可被2整除）、6（可被2和3整除）则不是。

判断一个数是否为素数，最直观的方法就是试除法：对于待判断的数n，用2到n-1之间的所有整数去试除n，如果都不能整除，则n是素数。但这种方法效率很低，特别是当n很大时。我们可以通过以下优化显著提高效率：

只需检查2到√n之间的整数：如果n能被某个大于√n的数整除，那么商必定小于√n，这意味着在检查较小的数时就已经能发现这个因数了。
跳过偶数（除了2）：所有大于2的偶数都不是素数，所以一旦确定n不是2，就可以跳过所有偶数。
预先排除小于2的数：根据定义，1和0都不是素数。

这些数学原理将直接指导我们后续的代码实现。理解这些优化背后的数学逻辑，比单纯记住代码更重要。

2. 基础素数判断的实现

让我们从最基本的素数判断程序开始。这个版本虽然效率不高，但清晰地展示了素数判断的核心逻辑：

c复制#include <stdio.h>
#include <stdbool.h> // 使用bool类型需要包含此头文件

bool isPrimeBasic(int n) {
    if (n <= 1) return false; // 1和0不是素数
    if (n == 2) return true;  // 2是唯一的偶素数
    
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false; // 发现能整除的因数，不是素数
        }
    }
    return true; // 没有发现因数，是素数
}

int main() {
    int num;
    printf("请输入一个正整数: ");
    scanf("%d", &num);
    
    if (isPrimeBasic(num)) {
        printf("%d 是素数\n", num);
    } else {
        printf("%d 不是素数\n", num);
    }
    
    return 0;
}