【揭秘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言語中尋覓質數的兩種演算法：試除法跟篩法。試除法簡單直不雅，但效力較低；篩法則更高效，但實現起來絕對複雜。讀者可能根據現實須要抉擇合適的演算法。