判断一个大于 2 的正整数 n 是否为素数，请用至少两种方法实现。c语言

方法一：暴力枚举法

暴力枚举法即为从 2 到 n-1 遍历每个数，判断是否能整除 n，若能整除则 n 不是素数，否则 n 是素数。

代码如下：

#include <stdio.h>

int is_prime(int n)
{
    int i;
    for (i = 2; i < n; i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main()
{
    int n;
    printf("请输入一个大于2的正整数：");
    scanf("%d", &n);
    if (is_prime(n)) {
        printf("%d是素数\n", n);
    } else {
        printf("%d不是素数\n", n);
    }
    return 0;
}

方法二：埃氏筛法

埃氏筛法是一种高效的素数判断方法，其基本思想是从 2 开始，将每个素数的倍数都标记成合数，直到最后剩下的都是素数。

具体实现过程如下：

1. 创建一个布尔数组，记录每个数是否为素数，初始值都设置为 true。

2. 从 2 开始，将每个素数的倍数都标记成合数，具体实现为遍历 2 到 sqrt(n) 的所有数，如果该数为素数，则将其倍数均标记为合数。

3. 遍历整个数组，如果某个数未被标记为合数，则该数为素数。

代码如下：

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

int is_prime(int n)
{
    if (n < 2) {
        return false;
    }
    int i;
    for (i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int main()
{
    int n;
    printf("请输入一个大于2的正整数：");
    scanf("%d", &n);

    bool* primes = (bool*)malloc(sizeof(bool) * (n+1));
    int i, j;
    for (i = 0; i <= n; i++) {
        primes[i] = true;
    }
    primes[0] = primes[1] = false;
    for (i = 2; i <= sqrt(n); i++) {
        if (is_prime(i)) {
            for (j = i*i; j <= n; j += i) {
                primes[j] = false;
            }
        }
    }
    if (primes[n]) {
        printf("%d是素数\n", n);
    } else {
        printf("%d不是素数\n", n);
    }

    free(primes);

    return 0;
}