C语言如何高效输出100以内所有素数？

C语言输出100以内的素数

以下是几种用C语言输出100以内素数的方法：

简单判断法

#include <stdio.h>
#include <math.h>
int main() {
    int i, j;
    int isPrime;
    printf("100以内的素数有：\n");
    for (i = 2; i <= 100; i++) {
        isPrime = 1; // 假设当前数是素数
        // 检查i是否能被2到sqrt(i)之间的数整除
        for (j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) {
                isPrime = 0; // 不是素数
                break;
            }
        }
        if (isPrime) {
            printf("%d ", i);
        }
    }
    return 0;
}

优化判断法（跳过偶数）

#include <stdio.h>
#include <math.h>
int main() {
    int i, j;
    printf("100以内的素数有：\n");
    printf("2 "); // 2是唯一的偶素数
    // 只检查奇数
    for (i = 3; i <= 100; i += 2) {
        int isPrime = 1;
        // 检查是否能被奇数整除
        for (j = 3; j <= sqrt(i); j += 2) {
            if (i % j == 0) {
                isPrime = 0;
                break;
            }
        }
        if (isPrime) {
            printf("%d ", i);
        }
    }
    return 0;
}

埃拉托斯特尼筛法（更高效）

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
int main() {
    bool isPrime[101]; // 0-100
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false; // 0和1不是素数
    for (int i = 2; i * i <= 100; i++) {
        if (isPrime[i]) {
            // 将i的倍数标记为非素数
            for (int j = i * i; j <= 100; j += i) {
                isPrime[j] = false;
            }
        }
    }
    printf("100以内的素数有：\n");
    for (int i = 2; i <= 100; i++) {
        if (isPrime[i]) {
            printf("%d ", i);
        }
    }
    return 0;
}

输出结果

程序运行后都会输出相同的结果：

100以内的素数有：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

方法三（埃拉托斯特尼筛法）是最高效的，特别是当需要查找较大范围内的素数时，对于100以内的素数,任何方法都能快速完成。