【算法】常用的基础数论

作者：指针不指南吗
专栏：算法篇

🐾或许会很慢，但是不可以停下🐾

1.GCD&LCM

最大公约数&最小共倍数

欧几里得算法——高效

//最大公约数
int gcd(int x,int y)
{return y?gcd(y,x%y):x;
}//最小公倍数
int lcm(int x,int y)
{return x*y/gcd(x,y);
}

2.判断素数(质数)

孪生素数法——高效

• 分析过程如下

首先看一个关于质数分布的规律：大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等；

证明：令x≥1，将大于等于5的自然数表示如下：
······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······
可以看到，不在6的倍数两侧，即6x两侧的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。这里要注意的一点是，在6的倍数相邻两侧并不是一定就是质数。

此时用一个循环判断质数，可以以6为单元快进，i+=6，加快判断速度。

原因是，假如要判定的数为n，则n必定是6x-1或6x+1的形式，对于循环中6i-1，6i，6i+1,6i+2，6i+3，6i+4，其中如果n能被 6i，6i+2，6i+4整除，则n至少得是一个偶数，但是6x-1或6x+1的形式明显是一个奇数，故不成立；另外，如果n能被6i+3整除，则n至少能被3整除，但是6x能被3整除，故6x-1或6x+1（即n）不可能被3整除，故不成立。

综上，循环中只需要考虑6i-1和6i+1的情况，即循环的步长可以定为6，每次判断循环变量k和k+2的情况即可

bool isprime(int n)
{if(n<=3)   //特判几个较小的数return n>1;if(n%6!=1&&n%6!=5)  //不在6的倍数的两侧，一定不是素数return 0;for(int i=5;i<=sqrt(n);i+=6)  //判断在6的倍数的两侧的数，是不是素数if(n%i==0||n%(i+2)==0)return 0;return 1;
}

3.分解质因子

直接看例题吧

• 题目

  链接： AcWing 867. 分解质因数–解释+代码注释 - AcWing

  给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

  输入格式

  第一行包含整数 n。

  接下来 n 行，每行包含一个正整数 ai。

  输出格式

  对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

  每个正整数的质因数全部输出完毕后，输出一个空行。

  数据范围

  1≤n≤100,
  2≤ai≤2×$10^9$

  输入样例：

  2
  6
  8
  

  输出样例：

  2 1
  3 12 3
  

• 分析

  • x 的质因子最多只包含一个大于 根号x 的质数。如果有两个，这两个因子的乘积就会大于 x，矛盾。
  • i 从 2 遍历到 根号x。 用 x / i，如果余数为 0，则 i 是一个质因子。
  • s 表示质因子 i 的指数，x /= i 为 0，则 s++， x = x / i 。
  • 最后检查是否有大于 根号x 的质因子，如果有，输出。

• 代码实现

  #include<bits/stdc++.h>
  using namespace std;void divide(int x)
  {for (int i = 2; i <= x / i; i ++ )//i <= x / i:防止越界，速度大于 i < sqrt(x)if (x % i == 0)//i为底数{int s = 0;//s为指数while (x % i == 0) x /= i, s ++ ;cout << i << ' ' << s << endl;//输出}if (x > 1) cout << x << ' ' << 1 << endl;//如果x还有剩余，单独处理cout << endl;
  }int main()
  {int n;cin >> n;while (n -- ){int x;cin >> x;divide(x);}return 0;
  }