1.质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数的数称为质数。

2.互质指的是除了1，没有其他的公因子。

3.唯一分解定理：任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。(分解唯一,合成唯一)

4.若n为正整数，在 nn到 (n+1)(n+1) 之间至少有一个质数。

5.若n为大于或等于2的正整数，在n到n!之间至少有一个质数。

6.若质数p为不超过n(n>=2)的最大质数，则p>n/2。

7.所有大于10的质数中，个位数只有1,3,7,9。

8.对于任意的整型N，分解质因数得到N= P1^x1 * P2^x2 …… * Pn^xn，则N的因子个数M为 M=（x1+1） * （x2+1） * …… （xn+1）。

9.n的欧拉函数为ans,那么1~n/2内与n互质的数为ans/2,因为gcd(n,m)=gcd(n,(n-m))。

10.素数定理：不超过 x 的素数的个数近似为x / In(x)

1.判断质数
试除法 O(logn)

2.分解质因数
试除法
n可以整除i,设n=ix,因为n中不包含任何2~i-1的质因子,所以ix不包含任何2~n-1中的质因子,所以i中不包含任何2~i-1的质因子,所以一定是i一定是质数
n中最多只包含一个大于sqrt(n)的质数 O(logn)~O(sqrt(n))

3.质数筛
3.1朴素筛法:对于每个数筛掉它的倍数,nlogn的复杂度
3.2埃氏筛法:对于每个质数筛掉它的倍数,loglogn 的复杂度
3.3线性筛法:确保每个数都会被它的最小值因子筛掉:对于一个合数x来说,合数x一定存在一个最小值质因子primes[j],当i枚举到x/primes[j],这个合数一定会被筛掉
3.3.1线性筛法的正确性证明:每个合数都
3.3.2线性筛法确保每个数都会被它的最小值因子筛掉的证明:if(i%primes[j]==0) ,primes[j]一定是i的最小质因子,所以primes[j]一定是primes[j]i的最小质因子
if(i%primes[j]!=0),primes[j]一定小于i的所有质因子,所以primes[j]一定是primes[j]i的最小质因子
综上所述,每个数都会被它的最小质因子筛掉,因此是线性的
3.3.3不用写j<cnt 当i是合数时,primes[j]枚举到i的最小质因子时一定会停下来这个最小质因子一定小于i,而primes[j]存储的是小于等于i的所有质数,所以一定会停下来
当i是质数时,primes[j]枚举到i是一定会停下来捏
3.求约数
试除法 sqrt(n)
求一个数n的所有约数的时间复杂度:
while循环:O(sqrt(n))while循环:O(n)
sort操作：
1−n总共有nlogn个约数,所以一个数平均有logn个约数，所以n平均有logn个约数.1−n总共有nlogn个约数,所以一个数平均有logn个约数，所以n平均有logn个约数.
对n的所有约数排序,排序复杂度为NlogN,这里N=logn,所以sort的复杂度为logn∗log(logn)，相比于while循环可以忽略对n的所有约数排序,排序复杂度为NlogN,这里N=logn,所以sort的复杂度为logn∗log(logn)，相比于while循环可以忽略
所以求一个数的所有约数的时间复杂度为O(n√)O(n)
共tt个数据，所以总共时间复杂度为t∗O(n√)

4约数个数
约数个数,基于算数基本定理:对于任意的整型N，分解质因数得到N= P1^x1 * P2^x2 …… * Pn^xn，则N的因子个数M为 M=（x1+1） * （x2+1） * …… （xn+1）
N的任何一个约数都是这样的一个形式:P1^y1 P2^y2 …… * Pn^yn(0<=y<=x+1),由算数基本定理可得分解质因数不同,那么数一定不同,所以选法总数就是(x1+1） * （x2+1） * …… *（xn+1）
5.约数之和
ans=(p1^0+p1^1+…+p1x^1)…(pn^0+pn^1+..+pn^xn)展开可以得到所有约数捏

6.欧几里得算法
d可以整除a,d可以整除b,d可以整除a+b,d可以整除xa+yb
(a,b)=(b,a%b) 对于左边任何一个公约数d d能整除a,d能整出b,d可以整除a-cb
对于右边任何一个公约数d d能整除b,d能整除a-cb,d可以整除a
任何数和0的最大公约数是a