数论的基础知识
质数（又称素数）的定义：质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
还有其他因数的是合数
1既不是质数也不是合数
一：如何判断一个数是不是质数：试除法。时间复杂度O(sqrt(n))
性质：如果d能整除n的话，d | n，那么n / d也能整除n，(n / d) | n
n的所有约数都是成对出现的，d和n / d
所以我们在枚举的时候，可以只枚举每一对中较小的那一个
所以我们只枚举d <= (n / d)这样的d，即d * d <= n，d <= sqrt(n)。时间复杂度一定为O(sqrt(n))
二：分解质因数：试除法。
小学知识，如何将一个数分解质因数，短除法
分解质因数用短除法，把一个数进行短除可以分解成若干个质数相乘
分解质因数要从最小的质数2开始除，直到没有因数2再除以下一个质数3…直至除得的商也是质数为止。
如何用编程实现短除法
暴力做法
1 #include
2 using namespace std;
3 void divide(int n) {
4 for (int i = 2; i <= n; i++) {
5 if (n % i == 0) { //求i的次数。只要这行成立，i一定是质数
6 int s = 0;
7 while (n % i == 0) {
8 n /= i;
9 s++;
10 }
11 //结束后，s就是i的次数
12 cout << i << " " << s << endl;
13 }
14 }
15 }
16 int main() {
17 int n;
18 cin >> n;
19 while (n--) {
20 int x;
21 cin >> x;
22 divide(x);
23 cout << endl;
24 }
25 return 0;
26 }
这里有些细节，对一个数分解质因数，从思路上想，应该枚举这个数所有的质因数，但是在第4行，是枚举了n这个数所有的因数
枚举所有的因数，而不是枚举所有的质因数，会不会错了
其实是没错的，然后就是数论较难理解的数学知识部分了，为什么这样不错
当枚举到i的时候，就意味着已经把从2 ~ i - 1所有的n的质因子都除干净了
然后如果又有n % i == 0成立的话，n是i的倍数，所以i当中也不包含任何2 ~ i - 1的质因子，所以i一定是个质数
这样的做法时间复杂度O(n)，然后想办法进行优化
首先有个性质：任意一个正整数n最多只有一个质因数大于根号n
很容易用反证法证明，如果n这个数有两个质因数大于根号n，那两个大于根号n的数相乘就大于n了
所以我们可以先把所有小于等于根号n的质因子枚举出来，这样时间复杂度就是O(sqrt(n))，最后再找那一个可能存在的大于根号n的质因子
时间复杂度最好的是O(log n)，最坏是O(sqrt(n))
题目一：试除法判定质数
1 #include
2 using namespace std;
3 bool is_prime(int n) { //试除法
4 if (n < 2) {
5 return false;
6 }
7 for (int i = 2; i <= n / i; i++) {
8 if (n % i == 0) {
9 return false;
10 }
11 }
12 return true;
13 }
14 int main() {
15 int n;
16 cin >> n;
17 while (n--) {
18 int x;
19 cin >> x;
20 if (is_prime(x)) {
21 cout << "Yes" << endl;
22 } else {
23 cout << "No" << endl;
24 }
25 }
26 return 0;
27 }
题目二：分解质因数
1 #include
2 using namespace std;
3 void divide(int n) {
4 for (int i = 2; i <= n / i; i++) {
5 if (n % i == 0) { //求i的次数。只要这行成立，i一定是质数
6 int s = 0;
7 while (n % i == 0) {
8 n /= i;
9 s++;
10 }
11 //结束后，s就是i的次数
12 cout << i << " " << s << endl;
13 }
14 }
15 if (n > 1) { //如果最后n还大于1,那么此时的n就是那个大于根号n的质因子
16 cout << n << " " << 1 << endl;
17 }
18 }
19 int main() {
20 int n;
21 cin >> n;
22 while (n--) {
23 int x;
24 cin >> x;
25 divide(x);
26 cout << endl;
27 }
28 return 0;
29 }