基本了解：
1.算术基本定理:每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。例如：6936=2^3*3*17^2，1200=2^4*3*5^2。
2.由于任何一个合数n至多会有一个大于根号n的因子.——这点很重要
3.最小的质数为2.
一、质因数分解：
cnt=0; //cnt为素因子个数，p数组存的是素因子，num存的是每个素因子的指数。 for(int i=2;i*i<=n;i++) { if(n%i==0) { ++cnt; p[cnt]=i; num[cnt]=0; while(n%i==0) { ++num[cnt]; n/=i; } } } if(n>1)//最多有一个大于sqrt(n)的素因子 { ++cnt; p[cnt]=n; num[cnt]=1; }
二、素数测试：判定一个数字n是不是质数：拿1 ~n 的所有数字来试除 bool divisibiity_test(int n) { for (int i=2; i<n; i++) if (n % i == 0) return false; // 不是质数 return true; // 是质数 } 改进：一个数至少有一个比sprt(n)小的质因数。 bool divisibiity_test(int n) { for (int i=2; i<=sqrt(n); i++) if (n % i == 0) return false; return true; } 时间复杂度：O(sqrtN)
三、Eratosthenes筛法
算法描述：
1.列出所有正整数。
2.从2开始，删掉 2 的倍数。找下一个未被删掉的数字。
3.找到 3 ，删掉 3 的倍数。找下一个未被删掉的数字
4.找到 5 ，删掉 5 的倍数。
…
重复步骤，就能删掉所有合数，找到所有质数。
bool prime[20000000]; void eratosthenes() { memset(prime,1,sizeof(prime)); prime[0] = 0; prime[1] = 0; // 0 和 1 不是质数 for (int i=2; i<20000000; i++) if (prime[i]==1) // 删掉质数i的倍数 for (int j=i+i; j<20000000; j+=i) prime[j] = 0; } 改进：删掉质数 i 的倍数时，早已删掉1 倍~ i-1 倍之间的合数了，所以直接从i倍开始删除。当删去2的倍数时就已经删去6了，所以从3开始只要从9开始删就行。
void eratosthenes(){ memset(prime,1,sizeof(prime)); prime[0] = 0;prime[1] = 0; for (int i=2; i<20000000; i++) if (prime[i]==1) //删掉i的倍数从i倍开始。 for (int j=i*i; j<20000000; j+=i) prime[j] = 0; } 四、欧拉函数1.定理：对正整数n，欧拉函数φ(phi)指是小于n的所有数中与之互质的个数(包含1)。如φ(8)=4，因为1,3,5,7均和8互质。
2.表达形式：
3.计算公式：
4.性质：
a)当p为质数时, φ(p) = p – 1。
b)对于互质的正整数a和n,有a^φ(n) ≡ 1 (mod n)
c)费马小定理：若正整数a 与素数p 互质，则有a^(p - 1)≡1 mod p。
d)当n为奇数时φ(2n)=φ(n).
e)当n和m互质时,φ(n*m)=φ(n)*φ(m).
f)若n=p^k(p为质数),φ(n)=p^k-p^(k-1).
朴素算法实现：
1.根据公式1：n=p1^k1*p2^k2*…*pr^kr和公式2：φ(n)=n* (1-1/p1) *…* (1-1/pr)。
2.可将公式2可拆成n* (1-1/p1)=n-n/p1计算。
int euler(int n) { int i,ans=n; for(i=2; i*i<=n; i++) if(n%i==0) { ans=ans-ans/i; do n/=i;//把该素因子全部约掉 while(n%i==0); } if(n>1) ans=ans-ans/n; return ans; } 快速欧拉：void fasteuler() { memset(phi,0,sizeof(phi)); for (int i=2;i<=1000000;i++)//筛选求phi { if (!phi[i])//当phi[i]未访问,就是phi[i]=0的时候. { for (int j=i;j<=1000000;j+=i) { if (!phi[j])//当phi[j]未访问 phi[j]=j;//将phi[j]设为访问且值为j，方便接下来计算。 phi[j]=phi[j]-phi[j]/i;//算出phi[j]的个数(欧拉公式)。 }}}}
