质数

模板：

// 试除法判断质数
bool is_prime(int x)
{if (x < 2) return false;//只需枚举一部分 使得 i<= x / i, 时间复杂度为√nfor (int i = 2; i <= x / i; i ++ )if (x % i == 0)return false;return true;
}// 试除法分解质因数
void divide(int n)
{for (int i = 2; i <= n / i; i++){if (n % i == 0){int cnt = 0;while (n % i == 0){n /= i;cnt++;}printf("%d %d\n", i, cnt);}}//本身就是质数if (n > 1) printf("%d %d\n", n, 1);printf("\n");
}// 

试除法判定质数

代码：

#include<iostream>
using namespace std;
int n;bool is_prime(int x)
{if (x == 1) return false;for (int i = 2; i <= x / i; i++){if (x % i == 0) return false;}return true;
}int main()
{scanf("%d", &n);while (n--){int a;scanf("%d", &a);printf(is_prime(a) ? "Yes\n" : "No\n");}return 0;
}

分解质因数

代码：

#include<iostream>
using namespace std;void divide(int n)
{for (int i = 2; i <= n / i; i++){if (n % i == 0){int cnt = 0;while (n % i == 0){n /= i;cnt++;}printf("%d %d\n", i, cnt);}}//本身就是质数if (n > 1) printf("%d %d\n", n, 1);printf("\n");
}int main()
{int n;scanf("%d", &n);while (n--){int a;scanf("%d", &a);divide(a);}return 0;
}

筛质数

思路：
筛法求质数，有两种方式：

• 埃氏筛法
• 线性筛法

埃氏筛法
埃氏筛法每次筛掉质数的倍数（大于等于2倍），这样最后剩下的就全是质数。$st[i]$为$false$时，表示为质数。

埃氏筛法代码：

#include<iostream>
using namespace std;const int N = 1000010;
bool st[N];
int primes[N];
int cnt;void get_primes(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;}
}int main()
{int n;cin >> n;get_primes(n);cout << cnt << endl;return 0;
}

线性筛法
线性筛法保证$n$只会被最小质因子筛掉。

• i % primes[j] == 0，primes[j]是i的最小质因子，primes[j]是primes[j] * i的最小质因子。
• i % primes[j] != 0，primes[j]小于i的最小质因子，primes[j]是primes[j] * i的最小质因子。

bool st[N];
int primes[N];
int cnt;void get_primes(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;}}
}

线性筛法代码：

#include<iostream>
using namespace std;const int N = 1000010;
bool st[N];
int primes[N];
int cnt;void get_primes(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;}}
}int main()
{int n;cin >> n;get_primes(n);cout << cnt << endl;return 0;
}

约数

试除法求约数

代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;void get_divisors(int a)
{vector<int> res;for (int i = 1; i <= a / i; i++){if (a % i == 0){res.push_back(i);// 防止平方根多次出现if (i != a / i) res.push_back(a / i);}}//从大到小排序sort(res.begin(), res.end());for (int t : res) printf("%d ", t);printf("\n");}int main()
{scanf("%d", &n);while (n--){int a;scanf("%d", &a);get_divisors(a);}return 0;
}

约数个数

思路：
给定一个数$N$，$p_i$为$N$的质约数，则可以表示为:
$$N=p_1^{{\alpha }_1}\times p_2^{{\alpha }_2}\times p_3^{{\alpha }_3}\times ...\times p_k^{{\alpha }_k}$$
$N$的每一个约数$d_i$，可以表示为:
$$d_i=p_1^{{\beta }_1}\times p_2^{{\beta }_2}\times p_3^{{\beta }_3}\times ...\times p_k^{{\beta }_k}$$
其中，$0\le {\beta }_i\le {\alpha }_i$， ${\beta }_i$的选法有$0\sim {\alpha }_i$，共有$({\alpha }_i+1)$种选法 ，根据排列组合原理，约数个数为：
$$({\alpha }_1+1)\times ({\alpha }_2+1)\times ({\alpha }_3+1)\times ...\times ({\alpha }_k+1)$$

依次遍历$a_i$，求$a_i$的质因数以及每个质因数的个数，可以用哈希表保存结果

代码：

#include<iostream>
#include<unordered_map>
using namespace std;const int mod = 1e9 + 7;int main()
{int n;cin >> n;unordered_map<int, int> primes;while (n--){int x;cin >> x;for (int i = 2; i <= x / i; i++){while (x % i == 0){x /= i;primes[i]++;}}if (x > 1) primes[x]++;}long long res = 1;for (auto prime : primes) res = res * (prime.second + 1) % mod;cout << res << endl;return 0;
}

约数之和

思路：
根据约数个数的思路，约数之和为$$d_1+d_2+d_3+...+d_k①$$
其中， $$d_i=p_1^{{\beta }_1}\times p_2^{{\beta }_2}\times p_3^{{\beta }_3}\times ...\times p_k^{{\beta }_k}②$$
约数之和为$$(p_1^0+p_1^1+p_1^2...+p_1^{{\alpha }_1})...(p_k^0+p_k^1+p_k^2...+p_k^{{\alpha }_k})$$
展开可得式①，展开的每一项均为$d_i$

$(p_i^0+p_i^1+p_i^2...+p_i^{{\alpha }_1})$可以按照下面的方式进行推导：
$t_0=1$
$t_1=t_0\times p+1=p+1$
$t_2=t_1\times p+1=p^2+p+1$
…
$t_{{\alpha }_i}=t_{{\alpha }_i-1}\times p+1=p^{{\alpha }_i}+p^{{\alpha }_i-1}+...+p+1$，
最后计算$\prod _{i=1}^n{t}_{{\alpha }_i}$，即为约数之和。

代码：

#include<iostream>
#include<unordered_map>
using namespace std;const int mod = 1e9 + 7;int main()
{int n;cin >> n;unordered_map<int, int> primes;while (n--){int x;cin >> x;for (int i = 2; i <= x / i; i++){while (x % i == 0){x /= i;primes[i]++;}}if (x > 1) primes[x]++;}long long res = 1;for (auto prime : primes) {long long t = 1;int p = prime.first, a = prime.second;while (a--) t = (t * p + 1) % mod;res = res * t % mod;}cout << res << endl;return 0;
}

最大公因数

思路：
欧几里得算法，辗转相除法。
代码：

#include<iostream>
using namespace std;int gcd(int m, int n)
{return m % n == 0 ? n : gcd(n, m % n);
}int main()
{int n;cin >> n;while (n--){int a, b;cin >> a >> b;cout << gcd(a, b) << endl;}return 0;
}