[题] 试除法判定质数 #质数（素数） #试除法

质数 #质数（素数） #试除法"/>

[题] 试除法判定质数 #质数（素数） #试除法

题目

AcWing 866. 试除法判定质数

思路

首先是暴力枚举
时间：O( (n) )）

bool is_prime(int n){//朴素判定（暴力）if(n < 2) return 0;//小于2的数不在范围内，直接排除for(int i = 2; i < n; i ++)//枚举从2到n-1if(n % i == 0)//如果可以整除某一个数return 0;//就说明不是质数return 1;
}
时间复杂度是O(n)，效率低。

优化：限定范围。
原理：约数是一对一对的，所以每次枚举较小的一个约数就好。
时间：O( sqrt(n) )

  bool is_prime(int n){//优化写法if(n < 2) return 0;//小于2的数不在范围内，直接排除for(int i = 2; i <= n / i; i ++)//当i <= n/i 时，说明还没有遍历到重复的约数组/*注意不要写成for(int i = 2; i * i <= n; i ++)，会溢出注意不要写成for(int i = 2; i <= sqrt(n); i ++),每次执行sqrt(n)都耗费时间*/if(n % i == 0)//如果可以整除某一个数return 0;//就说明不是质数return 1;
}

代码

#include<bits/stdc++.h>
using namespace std;bool i(int n){//优化写法if(n < 2) return 0;//小于2的数不在范围内，直接排除for(int i = 2; i <= n / i; i ++)//枚举从到n/iif(n % i == 0)//如果可以整除某一个数return 0;//就说明不是质数return 1;
}
int main(){int n;cin >> n;while(n --){int a;cin >> a;if(i(a)) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}