质数
在大于1的整数中，如果只包含1和她本身这两个约数，那么这个整数被称为质数。
866. 试除法判定质数
给定n个正整数ai，判定每个数是否是质数。
输入格式
第一行包含整数n。
接下来n行，每行包含一个正整数ai。
输出格式
共n行，其中第 i 行输出第 i 个正整数ai是否为质数，是则输出“Yes”，否则输出“No”。
数据范围
1≤n≤100,
1≤ai≤2?109
输入样例：
2
2
6
输出样例：
Yes
No
试除法的优化：
由于某个数的约数是成对出现的，当枚举时，可以枚举一对约数中较小的，这样可以降低时间复杂度，为了使运行的时间更短，可以将 i <= sqrt(n) 或 i * i <= n 改为 i <= n / i.
Code：
#include <iostream>
#include <algorithm>
using namespace std;bool is_prime(int n)
{
if(n < 2) return false;for(int i = 2; i <= n / i; i ++){
if(n % i == 0) return false;}return true;
}int main()
{
int n;cin >> n;while(n --){
int x;cin >> x;if(is_prime(x)) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}
867. 分解质因数
给定n个正整数ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数n。
接下来n行，每行包含一个正整数ai。
输出格式
对于每个正整数ai,按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
数据范围
1≤n≤100,
1≤ai≤2?109
输入样例：
2
6
8
输出样例：
2 1
3 1
2 3
分解质因数优化难点：
如何保证枚举的 i 是质数？当枚举到 i，意味着2~(i - 1)的所有质因子已经处理完毕，即 i中不包含2~(i - 1)的质因子，则 i 一定是质数。n 中最多只包含一个大于sqrt(n)的质因子，在循环结束判断n的值是否大于1，若满足就输出。
Code:
#include <iostream>
#include <algorithm>
using namespace std;void divide(int n)
{
for(int i = 2; i <= n / i; i ++){
if(n % i == 0){
int s = 0;while(n % i == 0){
n /= i;s ++;}cout << i << ' ' << s << endl;}}if(n > 1) cout << n << ' ' << 1 << endl;puts("");
}int main()
{
int n;cin >> n;while(n --){
int x;cin >> x;divide(x);}return 0;
}868. 筛质数
给定一个正整数n，请你求出1~n中质数的个数。
输入格式
共一行，包含整数n。
输出格式
共一行，包含一个整数，表示1~n中质数的个数。
数据范围
1≤n≤106
输入样例：
8
输出样例：
4
Code:
#include <iostream>
#include <algorithm>
using namespace std;const int N = 1000010;
int n, cnt, primes[N];
bool st[N];//埃式筛法
void get_primes1(int n)
{
for(int i = 2; i <= n; i ++){
if(!st[i]) {
primes[cnt ++] = i;for(int j = i + i; j <= n; j += i)st[j] = true;//质数的倍数是合数，且所有的合数都可以由质数的倍数求得 }}
}//线性筛法（所有合数x只会被它最小质因子pj删除,且在i=x/pj处筛掉）
void get_primes2(int n)
{
for(int i = 2; i <= n; i ++){
if(!st[i]) primes[cnt ++] = i;for(int j = 0; primes[j] <= n/ i; j ++){
st[primes[j] * i] = true;if(i % primes[j] == 0) break;//primes[j]一定是i*primes[j]的最小质因子，则pj ≤ i的最小质因子}}
}int main()
{
cin >> n;get_primes1(n);cout << cnt << endl;return 0;
}