6.C++经典实例-计算给定范围内的素数（质数）

所谓素数（也称为质数）是指大于1的自然数，且只能被1和它本身整除的数。例如，2、3、5、7、11等都是素数。

下面是计算3000内所有的素数的实例

#include <iostream>
#include <vector>
#include <cmath>// 判断一个数是否为素数
bool isPrime(int num) {if (num <= 1) return false;  // 1及以下的数不是素数if (num == 2) return true;   // 2是最小的素数if (num % 2 == 0) return false;  // 偶数（除了2）都不是素数// 检查从3到sqrt(num)的所有奇数for (int i = 3; i <= std::sqrt(num); i += 2) {if (num % i == 0) return false;}return true;
}int main() {std::vector<int> primes;// 计算3000以内的所有素数for (int i = 2; i < 3000; ++i) {if (isPrime(i)) {primes.push_back(i);}}// 输出所有素数std::cout << "3000以内的所有素数：" << std::endl;for (int prime : primes) {std::cout << prime << " ";}std::cout << std::endl;return 0;
}

以下是执行结果：

大家想一下为什么循环到指定数的开方即可，不用再循环了，比如判断101是否为素数，那么对101进行开方计算，得到10.0499，那么只要循环10次即可，不用循环100次，可以大大节省计算量，想一想，如果10.0499*10.0499等于101，那么，只要这两个数相乘等于101的话，就不会只有1和他自己，如果小于这个开方数的，存在，也会出现重复，不为素数，当有一个数大于10.0499的时候，另外一个数，会小于10.0499，即只要是除法，总有一个数在比10.0499要小一点，所以循环到开方即可，不用全部循环，节省算力，提升运行效率。