一.质数

1.定义

质数与合数的定义：在大于1的整数中，如果只包含1和本身两个约数，就被称为质数（素数）；反之为合数。

2.判断质数

Ⅰ线性判断质数

只需要枚举2~n-1的所有数字，依次判断它们能否整除n，只要有一个可以就是合数；而如果都不能整除，则是质数。不过，这个算法的时间复杂度是O(n)级别，所以容易超时。

Ⅱ根号n判断质数

其实，我们只需要枚举完所有较小的数字即可，因为如果i可以整除n，那么n/i必然也可以整除n。通过计算会发现只需要枚举完小于根号n就可以了，这样代码的时间复杂度就变成了 O(根号n)。

3.分解质因数

最容易想到的一个解法，就是枚举所有可能的质数，然后让这个质数一直去除n，直到不能整除为止。

这样写是可以但太费时间了，我们可以直接枚举2~n-1然后一直循环去除。因为假设当前枚举的数i是合数，那么前面必然已经枚举过i的质因子了，所以合数 i并不会影响程序的结果。

但是这个算法还是太慢了，其实，我们枚举的范围同样可以只到n/i，而如果最后计算完后n!=1的话，那它里面的数字一定就是最后的质因子。

4.质数筛

在需要多次判断质数的场景，就要用到质数筛法了，常见的筛法有 朴素筛、埃氏筛和欧拉筛。

Ⅰ朴素筛

这个筛法的思想很简单，数字的倍数一定不是质数。那么在选到一个数字时，把这个数字的所有倍数全部筛掉，这样过一轮之后，所有的质数也就被筛选出来了。可是这个筛法还是很慢。

Ⅱ埃氏筛

可以发现，其实我们只需要遍历质数的倍数就可以，所以这个筛法的核心思想：质数的倍数一定不是质数。

Ⅲ欧拉筛(线性筛)

这个算法的核心思想是每个合数都可以分解为一个最小质因数乘以另一个数的形式，即 合数 = 最小质因数 * 自然数。

二.约数

1.定义

如果a能够整除b，那么a是 b的约数，b是a的倍数。

2.线性枚举约数

枚举1~n的数字，然后依次判断并加到数组中即可， 显然，这样做太慢了。

3.根号n枚举约数

与质数判断的性质相同，i小于根号n。

三.最大公约数

1.定义

最大公约数，指两个或多个整数共有的约数中最大的一个。

2.线性找最大公约数

要求a和b 的最大公约数，我们只需要把min(a,b)~1的数字列出来，然后找到第一个能同时整除a和b的数字，就是最大公约数了。

3.辗转相除法

欧几里得算法又称辗转相除法，原理为gcd(a,b)=gcd(b,a%b),(a>=b,a%b!=0)。 辗转相除法便是利用这个原理不断往下计算，直到a%b为0时。

四.什么是幂

幂是一个数自乘若干次的形式，乘方的结果叫做幂。

1.线性求幂

求a^b^只需要循环n次，每次乘a即可。