所谓素数(也称为质数)是指大于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要小一点,所以循环到开方即可,不用全部循环,节省算力,提升运行效率。