暴力法
也称定义法
质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数.
对于给定数字n,直接枚举j从1到n-1 ,如果j能够整除n,说明n不是质数
bool prime_simple(int num){
if(num == 1)return false;
for(int i = 2;i <= num - 1;i++)
if(num % i == 0)return false;
对于只是判断一个数字的时候,时间复杂度是O(n),但是当我们需要判断某个区间的质数的时候,时间复杂度就上升到了O(n^2).
简单优化
实际上枚举j到根号n就可以了,因为对于非质数num,存在a*b==num,若a和b均不为