首页 > 编程笔记 > C语言笔记

C语言写一个判断素数的函数（有源码有解析）

在开始编写判断素数的函数之前，我们先来了解一下什么是素数。素数，也称为质数，是一个大于 1 的自然数，除了 1 和它本身外，不能被其他自然数整除。换句话说，素数只有两个因数：1 和它本身。例如，2、3、5、7、11、13 等都是素数。
 

相对地，那些除了 1 和它本身之外还能被其他数整除的数，我们称之为合数。
 

判断一个数是否为素数的原理其实很简单，我们只需要检查这个数是否能被小于它的数（除了 1）整除：如果能被整除，那么它就不是素数；如果不能被整除，那么它就是素数。


但是，我们不需要检查所有小于它的数，只需要检查到它的平方根即可。这是因为如果一个数 n 可以被整除，那么它的因子中必然有一个小于或等于 √n。这个优化可以大大减少我们的计算量。


现在，让我们来编写一个C语言函数来判断一个数是否为素数：

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

bool is_prime(int n) {
    if (n <= 1) {
        return false;  // 1 和小于 1 的数都不是素数
    }
    if (n == 2) {
        return true;   // 2 是最小的素数
    }
    if (n % 2 == 0) {
        return false;  // 除了 2 以外的偶数都不是素数
    }
    
    // 只需要检查到平方根
    int sqrt_n = (int)sqrt(n);
    for (int i = 3; i <= sqrt_n; i += 2) {
        if (n % i == 0) {
            return false;  // 如果能被整除，就不是素数
        }
    }
    
    return true;  // 通过了所有检查，是素数
}

int main() {
    int number = 17;
    if (is_prime(number)) {
        printf("%d 是素数\n", number);
    } else {
        printf("%d 不是素数\n", number);
    }
    return 0;
}

让我们来解析一下这个函数的工作原理：
 

首先，我们排除了一些特殊情况。小于等于 1 的数都不是素数，所以我们直接返回 false。2 是最小的素数，我们直接返回 true。对于其他偶数，由于它们都能被 2 整除，所以我们也直接返回 false。
 

接下来，我们只需要检查奇数因子。我们从 3 开始，每次增加 2，一直检查到输入数字的平方根。如果在这个过程中发现任何一个数能够整除输入的数，那么这个输入就不是素数。如果所有的检查都通过了，那么这个数就是素数。
 

这个函数的时间复杂度是 O(√n)，这比简单地检查到 n-1 的 O(n) 复杂度要好得多。对于较大的数，这种优化可以显著提高程序的效率。
 

在主函数中，我们可以使用这个 is_prime 函数来判断任何整数是否为素数。上面的例子中，我们判断了数字 17 是否为素数。


运行这段代码，我们会得到如下输出：

17 是素数

这个函数可以很容易地集成到更大的程序中，用于各种需要判断素数的场景。例如，你可以用它来找出一定范围内的所有素数，或者在密码学相关的应用中使用。
 

需要注意的是，虽然这个函数对于一般的用途来说已经足够高效，但对于非常大的数字（比如在密码学中使用的那些），可能还需要更高效的算法，如 Miller-Rabin 素性测试。不过，对于初学者来说，理解和实现这个基本的素数判断函数是一个很好的起点。

相关文章