简单数学
略
最大公约数与最小公倍数
-
最大公约数
int gcd(int a, int b) { if (b == 0) { return a; } else { return gcd(b, a % b); } }
-
最小公倍数
假设d为a和b的最大公约数,则a和b的最小公倍数是a/d*b。
分数
略
素数
- 除1和本身外不能被其他数整除的一类数
- 1既不是素数也不是合数
素数的判断
-
从2到
sqrt(n)
(下界)都不能被n整除就是素数bool isPrime(int n) { if (n <= 1) { return false; } int sqr = (int)sqrt(1.0 * n); for (int i = 2; i <= sqr; i++) { if (n % i == 0) { return false; } } return true; }
素数表
-
数据不超过105可以直接循环判断素数,复杂度O(n√n)
-
线性筛:对每一个素数,筛去它的所有倍数,剩下的就是素数,复杂度O(nloglogn)
const int maxn = 101; int prime[maxn], pNum = 0; bool p[maxn] = {0}; void Find_Prime() { for (int i = 2; i < maxn; i++) { if (!p[i]) { prime[pNum++] = i; for (int j = i + i; i < maxn; j += i) { p[j] = true; } } } }
质因子分解
-
先打印素数表
-
枚举1到
sqrt(n)
范围内的质因子p,判断p是否是n的因子 -
如果p是n的因子,给fac数组增加质因子p,初始化个数为0,只要p还是n的因子,就让n除以p,每次令p的个数加1,直到p不再是n的因子
-
如果p不是n的因子就跳过
-
如果上述步骤结束后n仍然大于1,说明n有且仅有一个大于
sqrt(n)
的质因子,把它加入fac数组,令个数为1#include <cstdio> #include <cmath> const int maxn = 100010; int prime[maxn], pNum, num; bool notPrime[maxn]; struct factor { int p, cnt; } fac[10]; // 对于int范围内的数数组大小开到10就够用了 void Find_Prime() { for (int i = 2; i < maxn; i++) { if (!notPrime[i]) { prime[pNum++] = i; for (int j = i + i; j < maxn; j++) { notPrime[j] = true; } } } } int main() { int n; scanf("%d", &n); int sqr = (int)sqrt(1.0 * n); Find_Prime(); for (int i = 0; i < pNum && prime[i] <= sqr; i++) { if (n % prime[i] == 0) { fac[num].p = prime[i]; fac[num].cnt = 0; while (n % prime[i] == 0) { fac[num].cnt++; n /= prime[i]; } num++; } } if (n != 1) { fac[num].p = n; fac[num].cnt = 1; num++; } for (int i = 0; i < num; i++) { printf("%d %d\n", fac[i].p, fac[i].cnt); } return 0; }
时间复杂度O(√n)。