C语言判断素数的三种方法：试除法、筛法优化与快速幂

创作时间:

作者:

@小白创作中心

C语言判断素数的三种方法：试除法、筛法优化与快速幂

引用

来源

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

在C语言中，判断一个数是否为素数是一个常见的编程问题。本文将介绍三种主要的素数判断方法：试除法、筛法优化和快速幂与费马小定理。每种方法都有其适用场景和优缺点，通过对比分析，读者可以更好地选择适合特定需求的算法。

C语言判断素数最快的方法有：试除法、筛法优化、快速幂与费马小定理。在这些方法中，试除法最常用，筛法优化最有效。其中，筛法优化可以大大减少计算次数，提升效率。下面我们将详细介绍这些方法及其具体实现。

一、试除法

基本原理

试除法的基本思想是：一个数n如果能被2到sqrt(n)之间的任何数整除，那么n就不是素数；否则，n就是素数。这种方法适用于判断单个数的素数性质。

实现步骤

检查n是否小于2，如果是，则n不是素数。
检查n是否等于2或3，如果是，则n是素数。
检查n是否为偶数或能被3整除，如果是，则n不是素数。
从5开始，检查所有小于等于sqrt(n)的数，如果n能被其中任何一个数整除，则n不是素数；否则，n是素数。

代码实现

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

int isPrime(int n) {  
    if (n <= 1) return 0;  
    if (n <= 3) return 1;  
    if (n % 2 == 0 || n % 3 == 0) return 0;  
    for (int i = 5; i * i <= n; i += 6) {  
        if (n % i == 0 || n % (i + 2) == 0) return 0;  
    }  
    return 1;  
}  

int main() {  
    int number = 29;  
    if (isPrime(number)) {  
        printf("%d is a prime number.\n", number);  
    } else {  
        printf("%d is not a prime number.\n", number);  
    }  
    return 0;  
}

二、筛法优化

基本原理

筛法（埃拉托色尼筛法）是一种高效的求素数的方法。其基本思想是：从2开始，将2的倍数全部标记为非素数，然后找到下一个未标记的数，将其倍数全部标记为非素数，依次类推，直到sqrt(n)。

优化策略

空间优化：使用布尔数组来标记非素数。
时间优化：只筛选奇数，减少一半的计算量。

实现步骤

创建一个布尔数组，初始值为真。
从2开始，将2的倍数全部标记为非素数。
找到下一个未标记的数，将其倍数全部标记为非素数。
重复步骤2和3，直到sqrt(n)。
数组中未被标记的数即为素数。

代码实现

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

void sieveOfEratosthenes(int n) {  
    int* isPrime = (int*)malloc((n + 1) * sizeof(int));  
    memset(isPrime, 1, (n + 1) * sizeof(int));  
    isPrime[0] = isPrime[1] = 0;  
    for (int i = 2; i * i <= n; i++) {  
        if (isPrime[i]) {  
            for (int j = i * i; j <= n; j += i) {  
                isPrime[j] = 0;  
            }  
        }  
    }  
    for (int i = 2; i <= n; i++) {  
        if (isPrime[i]) {  
            printf("%d ", i);  
        }  
    }  
    printf("\n");  
    free(isPrime);  
}  

int main() {  
    int n = 30;  
    printf("Prime numbers up to %d are:\n", n);  
    sieveOfEratosthenes(n);  
    return 0;  
}

三、快速幂与费马小定理

基本原理

费马小定理：如果p是一个素数，且a是一个整数，满足1 <= a < p，那么a^(p-1) ≡ 1 (mod p)。利用这个定理可以进行素数判定。

快速幂算法

快速幂算法用于高效计算大整数的幂模运算。其基本思想是通过二分法将指数分解，从而减少计算次数。

实现步骤

使用快速幂算法计算a^(p-1) % p。
如果结果不等于1，则p不是素数；否则，p可能是素数。

代码实现

#include <stdio.h>

long long power(long long a, long long n, long long p) {  
    long long res = 1;  
    a = a % p;  
    while (n > 0) {  
        if (n % 2 == 1) {  
            res = (res * a) % p;  
        }  
        n = n >> 1;  
        a = (a * a) % p;  
    }  
    return res;  
}  

int isPrimeFermat(int p, int iterations) {  
    if (p <= 1 || p == 4) return 0;  
    if (p <= 3) return 1;  
    for (int i = 0; i < iterations; i++) {  
        int a = 2 + rand() % (p - 4);  
        if (power(a, p - 1, p) != 1) return 0;  
    }  
    return 1;  
}  

int main() {  
    int number = 29;  
    int iterations = 5; // Number of iterations for accuracy  
    if (isPrimeFermat(number, iterations)) {  
        printf("%d is a prime number.\n", number);  
    } else {  
        printf("%d is not a prime number.\n", number);  
    }  
    return 0;  
}