目录

1、gcd最大公约数

2、LCM最小公倍数

3、质数判断

4、埃及筛（筛 1~n 中所有质数）

5、线性筛（欧拉筛，最快筛质数）

6、质因数分解

7、唯一分解定理

8、快速幂

9、计数问题

---

1、gcd最大公约数

要求：求这两个数能同时整除的最大数

公式：辗转相除法 gcd(a,b)=gcd(b,a%b)

public static int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

2、LCM最小公倍数

要求：能同时整除这两个数的最小数

公式：lcm(a,b) = a*b / gcd(a,b)

//可能数据会很大，防止溢出，先转long类型
public static long lcm(int a,int b){
    return 1L*a*b/gcd(a,b);
}

3、质数判断

什么是质数：大于 1，且只能被 1 和自己整除（只需要判断【2，根号n】之间是否会被整除）

public static boolean isPrime(int n){
    if(n<2) return false;
    for(int i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}

4、埃及筛（筛 1~n 中所有质数）

思路：找到质数，把它所有倍数全部标记删掉

常用于进行批量质数判断，把一个范围内所有的质数做标记

//埃及筛：判断某一组中的数是否是质数
//返回 isPrime 数组，isPrime[x] = true 表示 x 是质数

//判断1~n质数的个数
public static boolean[] sieve(int n) {
        if (n < 2) return new boolean[0];  //返回一个空的boolean数组

        boolean[] isPrime = new boolean[n + 1];
        // 初始全部设为 true
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i <= n; i++) {
            //如果 i 是质数，筛掉其倍数，而且只需要筛掉i*i后面的元素
            if (isPrime[i]) {   
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        return isPrime;
    }

5、线性筛（欧拉筛，最快筛质数）

优点：每个数只筛一次，效率最高

static List<Integer> primes = new ArrayList<>();
static boolean[] vis;
public static void euler(int n){
    vis=new boolean[n+1];
    for(int i=2;i<=n;i++){
        if(!vis[i]) primes.add(i);
        for(int p:primes){
            if(i*p>n) break;
            vis[i*p]=true;
            if(i%p==0) break;
        }
    }
}

6、质因数分解

把一个数拆成 质数相乘，并且可以统计出每个质因子分别有多少个

public static void factor(int x){
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            int cnt=0;
            while(x%i==0){
                cnt++;
                x/=i;
            }
            System.out.println("质数"+i+" 次数"+cnt);
        }
    }

    //最后判断一下有没有被完全整除，如果没有，自身也算一个因子
    if(x>1) System.out.println("质数"+x+" 次数1");
}
// factor(12) 输出2^2 3^1

进阶：已经求出这个数的每个质因子的个数，求这个数“因数的总数”——>转化为组合问题（这里是因数，只要能被这个数整除的数就是因数）

7、唯一分解定理

定理：任意大于 1 正整数，只能唯一拆成一堆质数幂相乘
形式：

用途：求 LCM、GCD、约数个数、约数和全靠它

（1）求 GCD 最大公约数（取最小次方）

规则：同一个质数，挑两个数里次数更小的，全部乘起来

例子：

• 质数 2：次数选 min (2,1) = 1
• 质数 3：次数选 min (1,2) = 1

---

（2）求 LCM 最小公倍数（取最大次方）

规则：同一个质数，挑两个数里次数更大的，全部乘起来

还用 12 和 18

• 质数 2：max (2,1)=2
• 质数 3：max (1,2)=2

---

（3）求约数（因数）个数

规则：每个质数的次方数 +1，再全部相乘

例子：

• 2 的次方：2 → 2+1=3
• 3 的次方：1 → 1+1=2
• 总个数 = 3×2=6 ，对应因数：1,2,3,4,6,12

---

（4）求约数总和

公式人话：对每个质数单独算一串求和，再全部相乘

例子：

• 2 这边：
• 3 这边：
• 总和 =4*7=28

12 的所有因数加起来：1+2+3+4+6+12=28，对上

8、快速幂

快速算 a^b % mod，避免超时、爆数据。如果幂太大，暴力必超时

核心思路：

1、为什么要把b转成二进制？假如b是5，对应二进制：101。5=4+1

2、a的b次方就是：b个a相乘。(a×a×a×a)×a=a的4次方×a的1次

因为每一次循环，都会把a翻一倍，分别表示为a ，a的二次方，a的4次方。刚好对应二进制里的1，2，4，8....如果当前二进制位是1，就把此时的a乘入到结果中

static long pow(long a,long b,long mod){
      long res=1;
      //先取模防止溢出，怕a的值太大
      a=a%mod;   

      //把b看出二进制，一位一位判断
      while(b>0){
           //如果当前位是1，就把a乘入结果
           if((b&1)==1){
              res=(res*a)%mod;   //同样防止溢出
           }
           //每次循环a都要翻倍
           a=(a*a)%mod;
           //b右移一位
           b=b>>1;
      }
      return res;
}

9、计数问题

（1）约数（因数）个数

由唯一分解：

约数个数 =

public static int getDivNum(int x){
    int res=1;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            int c=0;
            while(x%i==0){
               c++;
               x/=i;
            }
            res*=c+1;
        }
    }
    //为什么是乘以2：因为最后只剩一个因数了，就是1+1
    if(x>1) res*=2;
    return res;
}

（2）欧拉函数 φ(n)

求1~n 中与 n 互质的数个数

先把 n 质因数分解：

p对应最小质因子

欧拉函数公式：

res = res / i * (i - 1)等价于：     

public static long phi(int n){
    long res=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            res=res/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) res=res/n*(n-1);
    return res;
}