判断是否为素数用c语言

在C语言中，判断一个整数是否为素数可以通过以下几种常见方法：

1. **试除法**（埃拉托斯特尼筛选法）：
这是最基本的方法，从2开始遍历到该数开方的最大整数，如果该数能被任何一个数整除，则不是素数。

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

int isPrime(int n) {
    if (n <= 1) {
        return 0; // 1不是素数，小于等于1的都不是
    }
    if (n == 2) {
        return 1; // 2是素数
    }
    if (n % 2 == 0) {
        return 0; // 偶数除了2以外都不是素数
    }
    int sqrtN = sqrt(n);
    for (int i = 3; i <= sqrtN; i += 2) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1; // 如果没有找到因子，那么它是素数
}

int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    if (isPrime(num)) {
        printf("%d is prime.\n", num);
    } else {
        printf("%d is not prime.\n", num);
    }
    return 0;
}

2. **质数判定优化**：
使用Sieve of Eratosthenes（埃拉托斯特尼筛法）预处理一定范围内的素数，然后只检查这些已知素数能否整除给定的数，提高效率。

// 预先计算并存储2到n范围内的所有素数
void sieveOfEratosthenes(int primes[], int n) {
    bool isPrime[n + 1];
    memset(isPrime, true, sizeof(isPrime));
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }

    for (int p = 2; p <= n; p++)
        if (isPrime[p])
            primes[p - 2] = p; // 把索引对应到数组
}

int isPrimeOptimized(int num) {
    int* primes = malloc(sizeof(int) * ((num / 2) + 1)); // 用于存放预处理后的素数
    sieveOfEratosthenes(primes, num);

    if (primes[num / 2] > 0) { // 查找num是否为已知素数列表中的元素
        free(primes);
        return 1;
    } else {
        free(primes);
        return 0;
    }
}

int main() {
    int num;
    scanf("%d", &num);
    if (isPrimeOptimized(num)) {
        printf("%d is prime.\n", num);
    } else {
        printf("%d is not prime.\n", num);
    }
    return 0;
}