关于质数和约数的一个小总结

约数

定义

​ 若整数n能够整除d，则d是n的约数，n是d的倍数，记作d|n

基本性质

• 唯一分解定理：任何一个正整数都可以分解为$p_1^{b_1}*p_2^{b_2}*p_3^{b_3}……p_n^{b_n}$（为了后面的叙述，若$i<j,p_i<p_j$）
• 它的正约数个数：$\prod_{i=1}^{m}(b_i+1)$
• $lcm(a,b)gcd(a,b)=ab$

基本算法和板子

• 试除法： 用来求解一个数的正约数集合，时间复杂度：$\Theta(\sqrt n)$
• 更相减损术： 当使用高精度的时候，使用它来求解最大公约数很方便

1
2
3

int gcd(int x,int y){
    return (!y)?x:gcd(y,x-y);
}

• 辗转相除法：比更相减损术更快

  1 2 3

  int gcd(int x,int y){ return (!y)?x:gcd(y,x%y); }

  当然了，有一个速度更快的二进制版本

  1 2 3 4 5 6 7 8 9 10 11 12 13

  inline int gcd(int x,int y){ int i,j; if(x==0)return y; if(y==0)return x; for(i=0;(x&1)==0;i++)x>>=1; for(j=0;(y&1)==0;j++)y>>=1; if(i>j)i=j; while(true){ if(x<y){x^=y;y^=x;x^=y;} if(!(x%=y))return y<<i; while(!(x&1))x>>=1; } }

素数

定义

这个很简单吧，小学就学过的

基本定理

• 唯一分解定理（同上）
• 威尔逊定理：如果$(p-1)!\equiv-1(mod\ p)$，则p为质数
• 质数有无穷多个
• 欧拉定理这些的就放在同余那一块来讲了

数论的板子都在这里面来看吧

数论板子