c语言怎么求素数-C#.Net教程-PHP中文网

c语言怎么求素数

下次还敢

发布： 2024-05-13 20:12:23

原创

1391人浏览过

C 语言求素数方法：暴力法：逐一检查每个数是否满足素数条件。埃拉托斯特尼筛法：创建一个数表，逐一筛除合数。Miller-Rabin 测试：使用费马小定理和欧拉准则判断素数。

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 测试

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

以上就是c语言怎么求素数的详细内容，更多请关注php中文网其它相关文章！