C语言判断素数的三种方法：试除法、埃氏筛法和费马小定理

创作时间:

作者:

@小白创作中心

C语言判断素数的三种方法：试除法、埃氏筛法和费马小定理

引用

来源

https://docs.pingcode.com/baike/1289171

判断一个数是否为素数是编程中常见的问题，特别是在密码学、数据加密等领域。本文将详细介绍三种常用的素数判断方法：试除法、埃氏筛法和费马小定理，并提供C语言实现代码。

判断一个数是否为素数的常用方法有：试除法、埃氏筛法、费马小定理。在这篇文章中，我们将详细探讨如何使用C语言来判断一个数是否为素数，并重点介绍试除法的实现细节。试除法是一种简单且高效的素数判断方法，适合于大多数编程初学者和中等规模的数据集。

一、试除法的基本概念与实现

1. 什么是试除法

试除法是判断一个数是否为素数的最直观的方法。它的基本思想是：如果一个数n能被小于等于sqrt(n)的任何一个数整除，那么n就不是素数；否则，n就是素数。因为如果一个数n能被大于sqrt(n)的数整除，那么它必定也能被小于等于sqrt(n)的数整除。

2. 试除法的C语言实现

为了在C语言中实现试除法，我们需要编写一个函数来判断一个数是否为素数。代码如下：

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

// 判断是否为素数的函数  
int isPrime(int n) {  
    if (n <= 1) return 0; // 小于等于1的数不是素数  
    if (n == 2) return 1; // 2是素数  
    if (n % 2 == 0) return 0; // 偶数不是素数  
    for (int i = 3; i <= sqrt(n); i += 2) {  
        if (n % 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;  
}

在这段代码中，我们首先定义了一个名为isPrime的函数，该函数接收一个整数作为参数并返回一个布尔值（0表示不是素数，1表示是素数）。在main函数中，我们通过读取用户输入的数并调用isPrime函数来判断其是否为素数。

3. 试除法的时间复杂度

试除法的时间复杂度为O(sqrt(n))，因为我们只需要检查到sqrt(n)即可。这使得试除法在处理较小的数时非常高效，但对于非常大的数可能会变得缓慢。在这种情况下，我们可以使用更高级的算法，如埃氏筛法或费马小定理。

二、埃氏筛法的基本概念与实现

1. 什么是埃氏筛法

埃氏筛法是一种生成素数表的高效算法。它的基本思想是：从2开始，将每个素数的倍数标记为非素数，直到达到所需的范围。这一过程类似于筛选，因而得名“筛法”。

2. 埃氏筛法的C语言实现

为了在C语言中实现埃氏筛法，我们需要编写一个函数来生成一个范围内的所有素数。代码如下：

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

// 埃氏筛法生成素数表  
void sieveOfEratosthenes(int n) {  
    int *prime = 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; // 将p的倍数标记为非素数  
            }  
        }  
    }  
    // 打印所有素数  
    for (int p = 2; p <= n; p++) {  
        if (prime[p] == 1) {  
            printf("%d ", p);  
        }  
    }  
    printf("\n");  
    free(prime); // 释放动态分配的内存  
}  

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

在这段代码中，我们首先定义了一个名为sieveOfEratosthenes的函数，该函数接收一个整数n作为参数并打印出小于等于n的所有素数。在main函数中，我们通过读取用户输入的数并调用sieveOfEratosthenes函数来生成素数表。

3. 埃氏筛法的时间复杂度

埃氏筛法的时间复杂度为O(n log log n)，相对于试除法更高效，特别是在处理较大范围的数时。因此，埃氏筛法常用于生成素数表或处理大范围的素数判断。

三、费马小定理的基本概念与实现

1. 什么是费马小定理

费马小定理是数论中的一个重要定理，它指出：如果p是一个素数，并且a是一个小于p的整数，那么a^(p-1) ≡ 1 (mod p)。基于这个定理，可以通过随机选择a来快速判断一个数是否为素数。

2. 费马小定理的C语言实现

为了在C语言中实现费马小定理，我们需要编写一个函数来判断一个数是否为素数。代码如下：

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

// 快速幂算法计算 (a^b) % mod  
int power(int a, int b, int mod) {  
    int result = 1;  
    a = a % mod;  
    while (b > 0) {  
        if (b % 2 == 1) {  
            result = (result * a) % mod;  
        }  
        b = b >> 1;  
        a = (a * a) % mod;  
    }  
    return result;  
}  

// 使用费马小定理判断素数  
int isPrimeFermat(int n, int k) {  
    if (n <= 1 || n == 4) return 0;  
    if (n <= 3) return 1;  
    srand(time(0));  
    for (int i = 0; i < k; i++) {  
        int a = 2 + rand() % (n - 4);  
        if (power(a, n - 1, n) != 1) return 0;  
    }  
    return 1;  
}  

int main() {  
    int num, k;  
    printf("请输入一个整数：");  
    scanf("%d", &num);  
    printf("请输入测试次数：");  
    scanf("%d", &k);  
    if (isPrimeFermat(num, k)) {  
        printf("%d 是一个素数。\n", num);  
    } else {  
        printf("%d 不是一个素数。\n", num);  
    }  
    return 0;  
}

在这段代码中，我们首先定义了一个名为power的辅助函数，用于计算快速幂。然后定义了一个名为isPrimeFermat的函数，该函数接收一个整数n和测试次数k作为参数并返回一个布尔值（0表示不是素数，1表示是素数）。在main函数中，我们通过读取用户输入的数和测试次数并调用isPrimeFermat函数来判断其是否为素数。