参考资料：
1.https://www.bilibili.com/video/BV1x3411s7Sy/?spm_id_from=333.788&vd_source=e66dd25b0246f28e772d75f11c80f03c
2.余红兵：《数学奥林匹克小丛书（第二版）高中卷10————数论》
素数
素数的定义：
除了1和它本身以外不再有其他因数的自然数。亦即，除了1和n以外，并无其他正整数整除n的正整数.
1既不是素数，也不是合数。
n为合数，则有n=ab;n>a>1,n>b>1.
我们可以视正整数为3类数。1为单独一类数，其二素数，其三合数.
素数（prime number）的表示常用字母p。
引理2-1：任何大于1的整数必有素因子。
证明使用反证法。插播一句，带有“必有”字样的定理都可尝试反证法，正难则反。
我们设集合S包含所有大于1且没有素因子的整数，只需证明S为空集即可。假设S不为空集，m∈S是S中最小的整数(m>1且没有素因子)。
情况分为2种：
（1）m不可能为素数，因为任何素数都有素因子（它本身）；
（2）m若为合数，则有m=ab（合数定义），则1 既然a 定理2-1 任何合数都至少有一个不超过n*1/2的素因子。（n>1是合数，则存在素数p，使得p<=n*1/2） 证明： 设任一合数n，根据定义有n=ab； 假设a>n*1/2，b>n*1/2，易证这种情况不存在，因为ab>n*1/2*n*1/2,矛盾于n=ab。同理，亦不可能有a,b 假设此其一为a，根据引理2-1得出a必有素因子p，p|a。而a|n，所以p|n,满足p<=n*1/2. 判断n为素数的方法：如果所有素数p<=n*1/2，都不能整除n，则n是素数. 定理2-2（算术基本定理）：任何非零整数n可以表示出如下乘积形式：n=±p1e1...prer。其中，p1...pr是互不相同的素数，e1...er是正整数. 1.该表示形式是唯一的（不计顺序） 2.认为±1可以表示成零个素数相乘的结果作为1. 接下来的文章中会证明该定理，此处暂时超纲. 欧几里得定理：素数有无穷多个. 其实它最好叫做欧几里得素数定理. 证明会使用算术基本定理。 假设素数仅有限个，设其为p1，...，pk;设M为这k个数的乘积，表示为M=p1...pk，设N=M+1. 显然，N>=2. 那么N也可以表示为一系列素数乘积的形式，则存在一个素数p，满足p|N. 且有p≠p1...pk（否则p|M，导致p|(N-M),有p|1，不可能） 所以，p不在p1...pk之中，这与假设相矛盾. 模运算 a mod b:设a,b∈Z且b>0，如果q,r∈Z满足a=qb+r,且0<=r 在C，C++语言中mod表示为%. 对于负整数的模运算，则与正整数正好相反， 设a<0,b>0.a mod b可理解为a不断地加上b直至得数d>0(d 但事实上，还存在这种争议结果：求出的d只需满足0<|d|<|b|，也就是说假设-5%3，得数可以是1，也可以是-2. 现如今大多数人认可的是这个模运算定义： 若a,b为整数,c≠0，那么余数d满足a=kb+c(k∈Z). 且，0<=|r|<=|d|. 在MSVC2021和Python 3.8中，对于-5%3，前者输出了-2，后者输出了1.这表示不同的语言、编译器都会有不同的理解。 (重要)模运算的性质 b|a即a mod b=0 (a+b) mod n= (a mod n + b mod n)mod n (a-b) mod n= (a mod n - b mod n)mod n (axb) mod n= (a mod n x b mod n)mod n 模运算的性质第一条显而易见，除此之外模运算没有类似的除法性质(本身就包含了一重除法). 为什么说重要呢？因为运用该性质C++不容易发生算术溢出。预先设置一个模数，对每个因数取模再总体取模，这样不容易发生long long悲剧.