C语言实例之10求0-200内的素数

1. 素数

素数（Prime number），也叫质数，是指在大于 1 的自然数中，除了 1 和它自身外，不能被其他自然数整除的数。例如 2、3、5、7、11 等都是素数，而 4 能被 2 整除、6 能被 2 和 3 整除，所以它们不是素数。

2. 素数的特性与判断思路

素数是指在大于 1 的自然数中，除了 1 和它自身外，不能被其他自然数整除的数。要判断一个数num是否为素数，最直接的方法是从 2 开始，依次检查num能否被小于它的每个数整除，如果都不能整除，那么num就是素数。
然而，这种方法的效率比较低。实际上，只需要检查num能否被小于等于sqrt(num)的数整除就可以了（这是基于一个数学原理：如果一个数num不是素数，那么它一定有一个小于等于sqrt(num)的因子）。

3. 实例代码

#include <iostream>
#include <cmath>

// 判断一个数是否为素数
bool isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    if (num <= 3) {
        return true;
    }
    if (num % 2 == 0 || num % 3 == 0) {
        return false;
    }

    for (int i = 5; i <= std::sqrt(num); i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) {
            return false;
        }
    }

    return true;
}

int main() {
    std::cout << "0到200之间的素数有：" << std::endl;
    for (int i = 0; i <= 200; ++i) {
        if (isPrime(i)) {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;

    return 0;
}

4. 分析

• isPrime函数用于判断一个数是否为素数。首先处理了小于等于1的数肯定不是素数以及2、3这两个特殊素数的情况。然后通过排除能被2和3整除的数来初步筛选，接着使用循环从5开始，每次增加6（因为大于3的素数一定可以表示为 6k ± 1 的形式，k为整数，i的值依次为 5、11、17、23…… 这些数都是6k - 1的形式；同时，对应的i + 2的值依次为 7、13、19、25…… 这些数都是6k + 1的形式。），判断该数能否被 i 或者 i + 2 整除，如果能，则不是素数，否则就是素数。
• 在 main 函数中，通过循环遍历0到200之间的每个数，调用 isPrime 函数进行判断，如果是素数就输出。

5. 优化

可以将

    for (int i = 5; i <= std::sqrt(num); i += 6) {
    }

修改为，减少不必要的循环

int sqrtNum = static_cast<int>(std::sqrt(num));
for (int i = 5; i <= sqrtNum; i += 6) {
}

6. 输出