【揭秘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语言中寻找质数的两种算法：试除法和筛法。试除法简单直观，但效率较低；筛法则更高效，但实现起来相对复杂。读者可以根据实际需求选择合适的算法。