c语言质数判断的方法有哪些

K-seo • 2024-02-23 22:36 • 网站运维 • 109 views

C语言质数判断的方法有哪些

在计算机编程中，质数判断是一个常见的问题，质数是指大于1的自然数中，除了1和它本身以外不再有其他因数的数，在C语言中，我们可以使用多种方法来判断一个数是否为质数，本文将介绍几种常用的质数判断方法。

1、试除法

试除法是最简单也是最直接的质数判断方法，基本思想是从2开始，依次尝试将待判断的数除以小于等于它的平方根的所有整数，如果没有找到能整除的数，则该数为质数。

include <stdio.h>
include <math.h>
int is_prime(int n) {
    if (n <= 1) {
        return 0;
    }
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}
int main() {
    int num;
    printf("请输入一个整数：");
    scanf("%d", &num);
    if (is_prime(num)) {
        printf("%d是质数
", num);
    } else {
        printf("%d不是质数
", num);
    }
    return 0;
}

2、埃拉托斯特尼筛法（Sieve of Eratosthenes）

埃拉托斯特尼筛法是一种高效的质数判断方法，其基本思想是从小到大遍历整数，将合数标记为非质数，最后剩下的即为质数，这种方法的时间复杂度为O(n log log n)。

include <stdio.h>
include <stdbool.h>
include <string.h>
include <math.h>
include <stdlib.h>
include <time.h>
define MAXN 1000000
bool prime[MAXN];
int primes[MAXN];
int count = 0;
void sieve() {
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;
    for (int i = 2; i <= sqrt(MAXN); i++) {
        if (prime[i]) {
            for (int j = i * i; j <= MAXN; j += i) {
                prime[j] = false;
            }
        }
    }
    for (int i = 2; i <= MAXN; i++) {
        if (prime[i]) {
            primes[count++] = i;
        }
    }
}
int main() {
    sieve();
    int num;
    printf("请输入一个整数：");
    scanf("%d", &num);
    if (num >= 2 && num <= count 1) {
        int index = lower_bound(primes, primes + count, num) primes;
        if (index == num 2 || primes[index + 1] primes[index] == 2) {
            printf("%d是质数
", num);
        } else {
            printf("%d不是质数，%d和%d之间没有其他质数。
", primes[index], primes[index + 1]);
        }
    } else {
        printf("%d不在已知质数范围内。
", num);
    }
    return 0;
}

3、Miller-Rabin素性测试（Miller-Rabin Primality Test）

Miller-Rabin素性测试是一种概率性的质数判断方法，其基本思想是基于费马小定理和大数定律，通过多次随机抽样测试，可以在一定程度上降低误判的概率，这种方法的时间复杂度为O(k log n)，其中k为测试次数，当k足够大时，误判概率可以降到很低，需要注意的是，Miller-Rabin素性测试不能保证结果一定正确，但可以给出一个较高的置信度。