1、简单迭代

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

bool isPrime1(int n) {
    if (n <= 1) return false;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int num;
    printf("请输入一个整数: ");
    scanf("%d", &num);

    if (isPrime1(num))
        printf("%d 是素数。\n", num);
    else
        printf("%d 不是素数。\n", num);

    return 0;
}

2、迭代到平方根

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

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

int main() {
    int num;
    printf("请输入一个整数: ");
    scanf("%d", &num);

    if (isPrime2(num))
        printf("%d 是素数。\n", num);
    else
        printf("%d 不是素数。\n", num);

    return 0;
}

3、优化的平方根迭代

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

bool isPrime3(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int main() {
    int num;
    printf("请输入一个整数: ");
    scanf("%d", &num);

    if (isPrime3(num))
        printf("%d 是素数。\n", num);
    else
        printf("%d 不是素数。\n", num);

    return 0;
}

4、埃拉托斯特尼筛法（适用于寻找多个素数）

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

void sieveOfEratosthenes(int n) {
    bool *prime = malloc((n + 1) * sizeof(bool));
    for (int i = 0; i <= n; i++) prime[i] = true;

    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p) prime[i] = false;
        }
    }

    for (int p = 2; p <= n; p++) {
        if (prime[p]) printf("%d ", p);
    }
    free(prime);
}

int main() {
    int num;
    printf("请输入一个整数: ");
    scanf("%d", &num);
    printf("小于等于 %d 的素数有: ", num);
    sieveOfEratosthenes(num);
    printf("\n");

    return 0;
}

5、判断多个数字是否为素数（批量检测）

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

bool isPrime5(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int main() {
    int nums[] = {2, 3, 4, 5, 16, 17, 18, 19, 20, 23};
    int size = sizeof(nums) / sizeof(nums[0]);

    for (int i = 0; i < size; i++) {
        if (isPrime5(nums[i]))
            printf("%d 是素数。\n", nums[i]);
        else
            printf("%d 不是素数。\n", nums[i]);
    }

    return 0;
}