866.试除法判定质数

时/空限制：1s / 64MB

题目描述

给定n个正整数\(a_i\)，判定每个数是否是质数。

输入格式

第一行包含整数\(n\)。

接下来\(n\)行，每行包含一个正整数\(a_i\)。

输出格式

共\(n\)行，其中第 \(i\) 行输出第 \(i\) 个正整数\(a_i\)是否为质数，是则输出「Yes」，否则输出「No」。

数据范围

\(1 \le n \le 100\), \(1 \le a_i \le 2\times10^9\)

输入样例

2
2
6

输出样例

Yes
No

代码

// 暴力O(n)
bool is_prime(int n) {
	if(n < 2) return false;
	for(int i = 2; i < n; ++i) { // 这里是< 不是<=
		if(n % i == 0) return false;
	}
	return true;
}

以上暴力做法「时间复杂度太高」，可根据「质数性质」对其优化。

质数性质：假设 \(|\) 为整除符号，若 \(d | n\) 成立，则 \(\frac{n}{d} | n\) 成立。 举例：假设 \(n = 12\)，若 \(2\) 为 \(12\) 的约数，那 \(6\) 也是 \(12\) 的约数；若 \(3\) 为 \(12\) 的约数，那 \(4\) 也是 \(12\) 的约数。可发现「约数都是成对出现」。所以在枚举时，只需枚举出「成对约数」中较小的那一个即可。假设 \(d\) 为较小的数，即满足 \(d \le \frac{n}{d}\)，此时要枚举区间 \([2, d]\) 的所有正整数，整理得：\(d \le \sqrt{n}\)，因此只需枚举区间 \([2, \sqrt{n}]\) 范围的数即可。

// 优化O(sqrt(n))
bool is_prime(int n) {
	if(n < 2) return false;
	for(int i = 2; i <= n/i; ++i) { // 不推荐i*i <= n的写法 和 i <= sqrt(n)的写法
		if(n % i == 0) return false;
	}
	return true;
}

• 循环终止条件用 i <= n/i 最好，原因如下：
  • 若使用 i <= sqrt(n)，每次循环都会使用 sqrt 函数计算，产生时间开销。
  • 若使用 i*i <= n，i*i 可能会造成数值溢出。
• x < 2时直接返回false。