c语言怎么求素数

如何用 C 语言求素数

素数，又称质数，是指大于 1 且只能被 1 和自身整除的自然数。用 C 语言求素数，主要有以下方法：

1. 暴力法

这种方法最简单，通过逐一检查每个数是否满足素数条件，来判断其是否为素数。实现代码如下：

立即学习“C语言免费学习笔记（深入）”；

<code class="c">#include <stdio.h>
int isPrime(int num) {
    if (num <= 1) {
        return 0; // 1 及以下不是素数
    }
    for (int i = 2; i <= num / 2; 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;
}</code>

2. 埃拉托斯特尼筛法

这种方法通过创建一张数表，并逐一筛除合数（非素数），来找出素数。实现代码如下：

<code class="c">#include <stdio.h>
#include <stdlib.h>
int main() {
    int SIZE = 100; // 保存整数的数表大小
    int *arr = (int *)malloc(SIZE * sizeof(int));
    
    // 初始化数表，所有数都认为是素数
    for (int i = 0; i < SIZE; i++) {
        arr[i] = 1;
    }
    
    // 从 2 开始，逐一筛除非素数
    for (int i = 2; i < SIZE; i++) {
        if (arr[i]) { // 如果 i 是素数
            for (int j = i * i; j < SIZE; j += i) { // 筛除 i 的倍数
                arr[j] = 0;
            }
        }
    }
    
    // 打印素数
    printf("素数列表：");
    for (int i = 2; i < SIZE; i++) {
        if (arr[i]) {
            printf("%d ", i);
        }
    }
    
    free(arr);
    return 0;
}</code>

3. Miller-Rabin 测试

这种方法通过使用费马小定理和欧拉准则，在一定概率下判断一个数是否为素数。实现代码较复杂，这里不再给出。