c语言怎么识别素数-C++-PHP中文网

c语言怎么识别素数

下次还敢

发布： 2024-05-26 03:42:22

原创

419人浏览过

用 C 语言识别素数有两种方法：蛮力法：遍历所有小于或等于该数的一半的数，检查能否整除。埃拉托斯特尼筛法：标记所有素数及其倍数非素数，从 2 开始依次进行标记。

c语言怎么识别素数

如何用 C 语言识别素数

素数是指只能被 1 和自身整除的自然数。识别素数是计算机科学中一个经典问题，以下是用 C 语言识别素数的方法：

方法 1：蛮力法

最简单的识别素数的方法是蛮力法：

Devv

Devv是一个专为程序员打造的新一代AI搜索引擎

140

查看详情

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

<code class="c">#include <stdio.h>
#include <stdbool.h>

bool is_prime(int n) {
    if (n <= 1) {
        return false;
    }

    for (int i = 2; i <= n / 2; ++i) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

int main() {
    int n;
    printf("请输入一个数：");
    scanf("%d", &n);

    if (is_prime(n)) {
        printf("%d 是一个素数。\n", n);
    } else {
        printf("%d 不是一个素数。\n", n);
    }

    return 0;
}</code>

登录后复制

方法 2：埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种更有效率的识别素数的方法：

<code class="c">#include <stdio.h>
#include <stdbool.h>

void sieve_of_eratosthenes(int n) {
    bool is_prime[n + 1];

    // 标记所有数字为素数
    for (int i = 0; i <= n; ++i) {
        is_prime[i] = true;
    }

    // 从 2 开始，标记所有非素数
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

int main() {
    int n;
    printf("请输入一个数：");
    scanf("%d", &n);

    sieve_of_eratosthenes(n);

    if (is_prime[n]) {
        printf("%d 是一个素数。\n", n);
    } else {
        printf("%d 不是一个素数。\n", n);
    }

    return 0;
}</code>

登录后复制

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