C语言中判断质数的几种方法

C语言中判断质数的几种方法

质数的判断在编程中是一个常见的问题，通过有效的算法可以显著提高程序的运行效率。直接检查、优化检查、使用平方根法是最常用的三种方法，下面将详细介绍其中一种方法，并在后文中详细阐述其他两种方法。

一、直接检查

直接检查是最简单的一种方法，就是从2开始依次检查每个数是否是输入数的因子，如果存在一个因子，那么这个数就不是质数。以下是一个简单的C语言实现：

#include <stdio.h>

int isPrime(int num) {
    if (num <= 1) return 0; // 0和1都不是质数
    for (int i = 2; i < num; i++) {
        if (num % i == 0) return 0; // 找到一个因子，说明不是质数
    }
    return 1;
}

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

这个方法简单直接，但它的效率较低，尤其是对于较大的数，需要检查的次数非常多。

二、优化检查

为了提高效率，可以对直接检查法进行优化。一个重要的优化方法是：如果一个数能够被一个小于其平方根的数整除，那么它就不是质数。这大大减少了需要检查的次数。

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

int isPrime(int num) {
    if (num <= 1) return 0; // 0和1都不是质数
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) return 0; // 找到一个因子，说明不是质数
    }
    return 1;
}

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

使用平方根法可以显著减少判断质数时的计算量，因为只需要检查从2到数的平方根范围内的数即可。

三、进一步优化

在进一步的优化中，可以考虑跳过偶数，因为除了2以外，所有的质数都是奇数。这使得检查的次数再次减少。

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

int isPrime(int num) {
    if (num <= 1) return 0; // 0和1都不是质数
    if (num == 2) return 1; // 2是质数
    if (num % 2 == 0) return 0; // 其他偶数不是质数
    for (int i = 3; i <= sqrt(num); i += 2) {
        if (num % i == 0) return 0; // 找到一个因子，说明不是质数
    }
    return 1;
}

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

通过跳过偶数，进一步减少了检查的次数，提高了效率。

四、使用标记法（埃拉托斯特尼筛法）

埃拉托斯特尼筛法是一种高效的找出一定范围内所有质数的方法。其基本思想是：先将2到目标数范围内的所有数标记为未处理状态，然后从最小的质数2开始，将其所有倍数标记为非质数。然后找到下一个未标记的数，将其所有倍数标记为非质数，如此循环，直到处理到目标数的平方根为止。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void sieveOfEratosthenes(int n) {
    int* prime = (int*)malloc((n+1) * sizeof(int));
    memset(prime, 1, (n+1) * sizeof(int)); // 将所有数标记为“未处理状态”
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == 1) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = 0; // 标记所有倍数
        }
    }
    for (int p = 2; p <= n; p++)
        if (prime[p])
            printf("%d ", p);
    free(prime);
}

int main() {
    int n;
    printf("请输入一个正整数: ");
    scanf("%d", &n);
    printf("小于等于 %d 的所有质数: ", n);
    sieveOfEratosthenes(n);
    return 0;
}

埃拉托斯特尼筛法非常高效，特别适用于找出一个范围内的所有质数，而不仅仅是判断单个数是否为质数。

五、总结

判断一个数是否为质数在C语言中可以通过多种方法实现，从最简单的直接检查到优化检查，再到埃拉托斯特尼筛法，每种方法都有其适用的场景。直接检查适合小范围的数、优化检查适合中等范围的数、而埃拉托斯特尼筛法适合大范围的数。根据具体需求选择合适的方法，可以大大提高程序的运行效率。