C语言如何高效找出100到200的素数？

C语言求100到200的素数

以下是使用C语言求100到200之间所有素数的代码：

#include <stdio.h>
#include <math.h>
int isPrime(int num) {
    if (num <= 1) {
        return 0; // 1及以下的数不是素数
    }
    if (num == 2) {
        return 1; // 2是素数
    }
    if (num % 2 == 0) {
        return 0; // 偶数不是素数
    }
    // 检查从3到sqrt(num)的所有奇数
    for (int i = 3; i <= sqrt(num); i += 2) {
        if (num % i == 0) {
            return 0; // 能被整除，不是素数
        }
    }
    return 1; // 是素数
}
int main() {
    printf("100到200之间的素数有：\n");
    for (int i = 100; i <= 200; i++) {
        if (isPrime(i)) {
            printf("%d ", i);
        }
    }
    printf("\n");
    return 0;
}

代码说明：

1. isPrime函数：判断一个数是否为素数

   • 首先处理特殊情况（小于等于1的数、2、偶数）
   • 然后检查从3到该数平方根的所有奇数是否能整除该数
   • 如果能被任何数整除，则不是素数；否则是素数

2. main函数：

   • 遍历100到200之间的所有整数
   • 调用isPrime函数判断每个数是否为素数
   • 如果是素数，则打印输出

优化说明：

1. 排除了所有偶数（除了2），减少了不必要的计算
2. 只检查到该数的平方根，因为如果有一个大于平方根的因数，必然对应一个小于平方根的因数
3. 每次递增2，只检查奇数

输出结果：

运行此程序将输出：

100到200之间的素数有：
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199