【揭秘C语言质数寻踪】掌握算法，解锁高效寻找质数的奥秘

引言

质数，作为数学中的基本不雅点，在打算机科学中也有着广泛的利用。在C言语中，寻觅质数是一个经典且实用的编程成绩。本文将具体介绍多少种在C言语中寻觅质数的算法，并分析它们的优毛病，帮助读者控制高效寻觅质数的技能。

质数的基本不雅点

质数（Prime Number）是指在大年夜于1的天然数中，除了1跟它本身以外不再有其他因数的数。比方，2、3、5、7、11等都是质数。

寻觅质数的算法

1. 试除法

试除法是最简单也是最直不雅的寻觅质数的方法。对每个数n，从2开端实验除以n，假如n能被2整除，则n不是质数；不然，持续实验下一个数，直到实验到n的平方根。假如在这个范畴内不找到能整除n的数，则n是质数。

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

int isPrime(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 n;
    printf("请输入一个正整数：");
    scanf("%d", &n);
    if (isPrime(n)) {
        printf("%d 是质数\n", n);
    } else {
        printf("%d 不是质数\n", n);
    }
    return 0;
}

2. 筛法

筛法是一种更高效的寻觅质数的方法。它经由过程打消必定范畴内的合数来找到质数。罕见的筛法有埃拉托斯特尼筛法跟埃特金筛法等。

埃拉托斯特尼筛法

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

void sieveOfEratosthenes(int n) {
    char *prime = (char *)malloc((n + 1) * sizeof(char));
    memset(prime, 1, n + 1);
    prime[0] = prime[1] = 0;

    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = 0;
        }
    }

    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");
    free(prime);
}

int main() {
    int n;
    printf("请输入一个正整数：");
    scanf("%d", &n);
    sieveOfEratosthenes(n);
    return 0;
}

埃特金筛法

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

void sieveOfAtkin(int n) {
    char *prime = (char *)malloc((n + 1) * sizeof(char));
    memset(prime, 0, n + 1);
    prime[2] = prime[3] = 1;

    for (int x = 1; x * x <= n; x++) {
        for (int y = 1; y * y <= n; y++) {
            int n = 4 * x * x + y * y;
            if (n <= n) prime[n] = !prime[n];

            n = 3 * x * x + y * y;
            if (n <= n) prime[n] = !prime[n];

            n = 3 * x * x - y * y;
            if (x > y && n <= n) prime[n] = !prime[n];
        }
    }

    for (int p = 5; p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p * p)
                prime[i] = 0;
        }
    }

    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");
    free(prime);
}

int main() {
    int n;
    printf("请输入一个正整数：");
    scanf("%d", &n);
    sieveOfAtkin(n);
    return 0;
}

总结

本文介绍了在C言语中寻觅质数的两种算法：试除法跟筛法。试除法简单直不雅，但效力较低；筛法则更高效，但实现起来绝对复杂。读者可能根据现实须要抉择合适的算法。