质数
试除法判定质数
这个算法广为人知，这里就不证明了，解释一下 i<=√n 的写法
1、不推荐写成i<=sqrt(n)
首先需要引入头文件#include<cmath>麻烦，其次每次循环都要调用sqrt()函数，速度变慢了；
2、强烈不推荐写成 i*i<=n
如果 i 的值比较大， i*i 极有可能有爆int的风险，影响质数判断且很难debug；
3、强烈推荐用 i<=x / i 写法
不需要调用函数且绝对不会有数值过大的风险
#include <iostream> #include <algorithm> using namespace std; bool is_prime(int x) { if (x < 2) return false; for (int i = 2; i <= x / i; i ++ )//核心操作 if (x % i == 0) return false; return true; } int main() { int n; cin >> n; while (n -- ) { int x; cin >> x; if (is_prime(x)) puts("Yes"); else puts("No"); } return 0; }
分解质因数
本词条由“科普中国”科学百科词条编写与应用工作项目 审核 。
质因子（或质因数）在数论里是指能整除给定正整数的质数。根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。
即：n=p1^a1 * p2^a2 *p3^a3.....pn^an（p为质数，a为幂）
证明1：
循环里面的 i 一定是一个质数：假如 i 是一个合数，那么它一定可以分解成多个质因子相乘的形式，这多个质因子同时也是 x 的质因子且比 i 要小，而比 i 小的数在之前的循环过程中一定是被条件除完了的，所以 i 不可能是合数，只可能是质数
证明2：
if (x > 1) cout << x << ' ' << 1 << endl;
比sqet(n)大的质因子x最多只有1个，因为如果该质因子x数量大于一个，则x*x>n，是不可能的，所以比sqet(n)大的质因子x最多只有1个
那么我们只需要找小于sqrt（n）的所有质因子，然后如果n的值还大于1，说明仍然存在质因子，又因为大于sqrt（n）的质因子只有一个，所以直接输出该值并标记幂为1
#include <iostream> #include <algorithm> using namespace std; void divide(int x) { for (int i = 2; i <= x / i; i ++ ) if (x % i == 0)//见证明1：如果该条件成立，i一定是质数 { int s = 0; while (x % i == 0) x /= i, s ++ ; cout << i << ' ' << s << endl; } if (x > 1) cout << x << ' ' << 1 << endl;//最多只有一个大于平方根下n的质因子（两个相乘就大于n了） cout << endl; } int main() { int n; cin >> n; while (n -- ) { int x; cin >> x; divide(x); } return 0; }
筛质数
诶氏筛法 O(nloglogn)
根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。
反向思考：将2到n中，所有质数的倍数删除，那么剩下的就只有质数
#include <iostream> #include <algorithm> using namespace std; const int N= 1000010; int primes[N], cnt;//存质数与质数个数 bool st[N];//用于装合数 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[] st[j] = true; } }//最后primes[]存2到n所有质数，st[]装所有合数 } int main() { int n; cin >> n; get_primes(n); cout << cnt << endl; return 0; }
线性筛法 O(n)
if(i%primes[j]==0) break;
分两种情况：
情况1 i%primes[j]!=0
当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j]小于 i 的最小质因子,所以primes[j]*i的最小质因子就是primes[j];
情况2 i%primes[j]==0
当有i%primes[j]==0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是
prime[j]，当发现primes[j]是i最小质因子的时候,如果再继续进行的话，我们就把 prime[j+1]*i 这个数筛掉了,虽然这个数也是合数，但是我们筛掉它的时候并不是用它的最小质因数筛掉的，而是利用 prime[j+1] 和 i 把它删掉的，也就是说这个数的最小质因数其实是prime[j],如果我们不在这里退出循环的话，我们会发现有些数是被重复删除了的。
#include <iostream> #include <algorithm> using namespace std; const int N= 1000010; int primes[N], cnt; bool st[N]; 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 ++ )//primes[j]*i<=n 筛掉小于n的合数 { 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; }
约数
试除法求约数
若 i 是N的约数，则 N/i 也是N的约数。换言之，约数总是成对出现的（(除了对于完全平方数，√N会单独出现)。
#include <iostream> #include <algorithm> #include <vector> using namespace std; vector<int> get_divisors(int x) { vector<int> res; for (int i = 1; i <= x / i; i ++ ) if (x % i == 0) { res.push_back(i);//存储成对出现的约数 if (i != x / i) res.push_back(x / i);//除了对于完全平方数，√N会单独出现 } sort(res.begin(), res.end()); return res; } int main() { int n; cin >> n; while (n -- ) { int x; cin >> x; auto res = get_divisors(x); for (auto x : res) cout << x << ' '; cout << endl; } return 0; }
约数个数
约数个数定理：
根据约数个数定理，我们只需要分解质因数，然后直接套公式即可
分解质因数如上质数部分
#include <iostream> #include <algorithm> #include <unordered_map> #include <vector> using namespace std; typedef long long LL; const int N = 110, mod = 1e9 + 7; int main() { int n; cin >> n; unordered_map<int, int> primes;//存储质数p和对应的幂a 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] ++ ; } LL res = 1; for (auto p : primes) res = res * (p.second + 1) % mod;//公式(a1+1)*(a2+1)*....*(ak+1) cout << res << endl; return 0; }
约数之和
例题：正整数360的所有正约数的和是多少？
解：将360分解质因数可得
360=2^3*3^2*5^1
由约数和定理可知，360所有正约数的和为
(2^0+2^1+2^2+2^3)×(3^0+3^1+3^2)×(5^0+5^1)=(1+2+4+8)(1+3+9)(1+5)=15×13×6=1170
可知360的约数有1、2、3、4、5、6、8、9、10、12、15、18、
20、24、30、36、40、45、60、72、90、120、180、360；则它们的和为
1+2+3+4+5+6+8+9+10+12+15+18+20+24+30+36+40+45+60+72+90+120+180+360=1170
总结：
分解质因数后，约数和为
值得注意的是：
while (b -- ) t = (t * a + 1) % mod;
若b=0，t=1;b=1,t=p+1 以此类推
#include <iostream> #include <algorithm> #include <unordered_map> #include <vector> using namespace std; typedef long long LL; const int N = 110, 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] ++ ; } LL res = 1; for (auto p : primes)//套公式 { LL a = p.first, b = p.second; LL t = 1; while (b -- ) t = (t * a + 1) % mod;//求累加 res = res * t % mod;//求累乘 } cout << res << endl; return 0; }
最大公约数
辗转相除法求最大公约数，一行代码，背就完事了
#include <iostream> #include <algorithm> using namespace std; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { int n; cin >> n; while (n -- ) { int a, b; scanf("%d%d", &a, &b); printf("%d\n", gcd(a, b)); } return 0; }
值得注意的是，可以调用STL；但是速度比自己手写慢个5倍左右！！
#include<iostream> #include<algorithm> using namespace std;！ int n,a,b; int main() { cin >> n; while(n--){ cin >> a >> b; cout << __gcd(a,b) << endl;//调用STL函数 } return 0; }
