数学
质数与约数
质数的定义：
质数是大于1的自然数，它只有两个约数一个1，一个自己本身。
怎样用代码找出质数
线性判断质数：
要找出质数其实很简单，只需要枚举2~n-1之间的数（包括2和n-1），让n不断除以这些数就行了，但这样虽然简单，但时间复杂度太高了。
根号(n)判断质数：
我们通过刚才的代码可以知道一个性质：当枚举到一半之后的数字，后面的可一不用再试了，因为如果i可以整除n，那么n/i也一定可以整除n。所以根据这个性质，我们只需要枚举完所有较小的数字即可。时间复杂度也就降低了。第一题就可以用这种方法。可以判断一个数n是否为质数，只需检查从2到根号(n)之间的所有整数是否能整除n如果存在任何一个数能整除n，则n不是质数。如果所有数都不能整除n，则n是质数。
分解质因数：
我们一定学过分解质因数，我们想要实现这种代码，需要用上上面两种方法，但想要使时间复杂度低，必须使用第二种方法。第二题就可以使用第二种方法。从最小的质数2开始尝试除法对于每个可能的因数i（从2开始），检查是否能整除当前数x如果能整除，就不断除以i并计数，直到不能整除为止这样就能得到一个质因数i及其指数s处理完所有可能的因数后，如果剩下的x>1，说明x本身就是一个质数。
质数筛
要想时间复杂度更低就要使用质数筛了。 质数筛有：朴素筛，埃氏筛和欧拉筛(线性筛)。 这里我就列举时间复杂度最低的。
朴素筛
筛法的思想很简单，数字的倍数一定不是质数。那么在选到一个数字时，把这个数字的所有倍数全部筛掉，这样过一轮之后，所有的质数也就被筛选出来了。
埃氏筛
可以发现，其实没必要把所有的数字的倍数都遍历一遍，因为如果数字是一个合数，它的倍数肯定也被之前的质数筛掉了，所以只需要遍历质数的倍数；这也是筛法的核心思想：质数的倍数一定不是质数。
欧拉筛(线性筛)
欧拉筛的意义就是：先将2~n的质数存入数组，再将n不断除以这些数，就可以判断这个数是否为质数。第三题就可以这样写。 ###约数 约数的定义：约数就是能把n整除的数。
约数如何用代码找出
其实两种数差不多，在这里就不细细讲了。
线性判断约数
要找出约数其实很简单，只需要枚举1~n之间的数（包括1和n），让n不断除以这些数就行了，但这样虽然简单，但时间复杂度太高了。
根号(n)判断约数：
我们通过刚才的代码可以知道一个性质：当枚举到一半之后的数字，后面的可一不用再试了，因为如果i可以整除n，那么n/i也一定可以整除n。所以根据这个性质，我们只需要枚举完所有数字的一半即可，等一半枚举完就跳出循环。时间复杂度也就降低了。第四题，第五题和第六题就是这样写。第六题还要在拓展一下，要将约数的和求出来。
最大公约数
定义：
两个或两个以上的正整数的约数相同的最大的约数被称为最大公约数。
代码实现
我们只需要把min(a,b)~1的数字列出来然后找到第一个相同的约数就可以找到了。我们还可以进行优化，如加一个判断，使如果是两个质数的话，就输出1，是一对倍数的话，输出那个较小值。第7题就是这个道理。
快速幂
定义
幂是一个数自乘若干次的形式，乘方的结果叫做幂。比如n的m次方，就是n个m相乘。n是底数，m是指数。
线性求幂
求a的n次方，只需要，循环n次，每次乘a。但这样时间复杂度太高了，有没有更快的方法呢？
快速幂推理过程
快速幂算法的核心思想是通过将指数b分解为二进制形式。转化为二进制原理：任何正整数b都可表示为二进制形式，如13=(1101)2。因此= × × ，只需计算这些分量的乘积35。 ### 快速幂代码实现 每一步乘法后立即取模，防止数值溢出利用公式(a*b)%p 保持结果范围不会偏大。对于偶数b，直接平方，对于奇数b：转化为偶数情况。(递推)
龟速乘
定义
龟速乘是一种用于防止大数乘法溢出的算法。
核心思想
通过加法模拟乘法，利用转化成二进制和移位操作，将乘法转化为多次加法运算。
代码实现
转化为二进制：将乘数b表示为二进制形式当b的最低位为1时，将当前a加入结果，每轮将a翻倍（相当于左移一位，也相当于*2）b右移一位处理下一位。
特点
防溢出：通过加法代替乘法，避免中间结果溢出。
