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

C语言输出100以内的素数

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

基本方法

#include <stdio.h>
#include <math.h>
int main() {
    int i, j;
    int flag;
    printf("100以内的素数有：\n");
    for (i = 2; i <= 100; i++) {
        flag = 1; // 假设i是素数
        // 检查i是否能被2到sqrt(i)之间的数整除
        for (j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) {
                flag = 0; // 不是素数
                break;
            }
        }
        if (flag == 1) {
            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 flag = 1;
        for (j = 3; j <= sqrt(i); j += 2) { // 只用奇数除数
            if (i % j == 0) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            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;
    for (int i = 2; i * i <= 100; i++) {
        if (isPrime[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 

方法比较

1. 方法一：最直观，但效率较低，因为检查了所有可能的除数
2. 方法二：优化了基本方法，跳过了偶数,效率提高约50%
3. 方法三：埃拉托斯特尼筛法，是最高效的方法，尤其适合查找较大范围内的素数

对于100以内的素数，三种方法都可以快速完成，但对于更大的范围,方法三会更高效。