C语言如何实现getprime获取素数？

C语言实现获取素数（GetPrime）

在C语言中,获取素数（质数）通常有两种常见方法：一种是判断单个数是否为素数，另一种是生成一定范围内的所有素数（如埃拉托斯特尼筛法）。

方法1：判断单个数是否为素数

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
// 判断一个数是否为素数
bool isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    if (num == 2) {
        return true;
    }
    if (num % 2 == 0) {
        return false;
    }
    // 只需检查到平方根即可
    for (int i = 3; i <= sqrt(num); i += 2) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    int num;
    printf("请输入一个整数: ");
    scanf("%d", &num);
    if (isPrime(num)) {
        printf("%d 是素数\n", num);
    } else {
        printf("%d 不是素数\n", num);
    }
    return 0;
}

方法2：使用埃拉托斯特尼筛法生成素数

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
// 使用埃拉托斯特尼筛法生成n以内的所有素数
void getPrimes(int n) {
    if (n < 2) {
        printf("没有素数\n");
        return;
    }
    // 创建并初始化标记数组
    bool *isPrime = (bool *)malloc((n + 1) * sizeof(bool));
    for (int i = 0; i <= n; i++) {
        isPrime[i] = true;
    }
    isPrime[0] = isPrime[1] = false;
    // 筛法过程
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    // 输出所有素数
    printf("%d以内的素数有:\n", n);
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");
    free(isPrime);
}
int main() {
    int n;
    printf("请输入一个整数n: ");
    scanf("%d", &n);
    getPrimes(n);
    return 0;
}

方法3：优化后的筛法（空间优化）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
// 优化的筛法，只处理奇数
void getPrimesOptimized(int n) {
    if (n < 2) {
        printf("没有素数\n");
        return;
    }
    int size = (n - 1) / 2;
    bool *isPrime = (bool *)malloc(size * sizeof(bool));
    for (int i = 0; i < size; i++) {
        isPrime[i] = true;
    }
    // 筛法过程
    for (int p = 3; p * p <= n; p += 2) {
        if (isPrime[(p - 1) / 2]) {
            for (int i = p * p; i <= n; i += 2 * p) {
                isPrime[(i - 1) / 2] = false;
            }
        }
    }
    // 输出素数
    printf("%d以内的素数有:\n", n);
    printf("2 "); // 2是唯一的偶素数
    for (int p = 3; p <= n; p += 2) {
        if (isPrime[(p - 1) / 2]) {
            printf("%d ", p);
        }
    }
    printf("\n");
    free(isPrime);
}
int main() {
    int n;
    printf("请输入一个整数n: ");
    scanf("%d", &n);
    getPrimesOptimized(n);
    return 0;
}

1. 判断单个数是否为素数：适用于需要检查特定数字的情况，时间复杂度为O(√n)
2. 埃拉托斯特尼筛法：适用于生成一定范围内的所有素数，时间复杂度为O(n log log n)
3. 优化筛法：通过只处理奇数来节省空间，适用于大范围素数生成

选择哪种方法取决于你的具体需求,如果只需要检查几个数，第一种方法更简单；如果需要生成大量素数，后两种方法更高效。