数论是研究整数性质的算法题型，在蓝桥杯占比 20%~30%，是最容易拿分、最依赖模板的板块。

核心高频方向：

1. 最大公约数 / 最小公倍数

2. 质数判断与质数筛（埃氏筛）

3. 快速幂

4. 因数与倍数

一、最大公约数

1、原理

不断用大数取余小数，把数字缩小。

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

直到 b=0，a 就是最大公约数。

2、运用

// 辗转相除法求最大公约数
public static long gcd(long a, long b) {
    // 当 b 不为 0 时，继续循环
    while (b != 0) {
        long temp = b;    // 保存 b
        b = a % b;        // a, b 变成 b, a%b
        a = temp;         // a 更新为原来的 b
    }
    return a;             // 最后 a 就是最大公约数
}

def gcd(a, b):
    while b != 0:
        a, b = b, a % b  # 同步赋值，简化写法
    return a

二、最小公倍数

1、原理

必须依赖最大公约数：

公式：LCM(a,b) = a × b // GCD(a,b)

注意：必须先除后乘，防止溢出

2、运用

public static long lcm(long a, long b) {
    return a / gcd(a, b) * b;  // 先除再乘，不溢出
}

def lcm(a, b):
    return a // gcd(a, b) * b

例题

[消失的蓝宝 - 蓝桥云课]

推导结论：N = 最小公倍数 - a - b

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
​
public class Main {
    public static void main(String[] args) {
      Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
      long a=20250412l;
      long b=20240413l;
      long g=gcd(a,b);
      long lcm=a*b/g;
      System.out.println(lcm-a-b);
       
    }
    public static long gcd(long a,long b){
      while(b!=0){
        long temp=b;
        b=a%b;
        a=temp;
      }
      return a;
    }
}

三、质数与埃氏筛

1、质数判断

普通判断法（适合小数据）

一个数从 2 试用到 √n，能整除就不是质数。

缺点：多次判断会超时。

public static boolean isPrime(long n) {
    if (n < 2) return false;    // <2 不是质数
    // 只需循环到根号 n，优化效率
    for (long i = 2; i * i <= n; i++) {
        if (n % i == 0) {       // 能被整除，说明是合数
            return false;
        }
    }
    return true;
}

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

例题

魔法科考试

import java.util.Scanner;
import java.util.*;
// 或者精确导入：import java.util.Set; import java.util.HashSet;
// 1:无需package
// 2: 类名必须Main, 不可修改
​
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n=scan.nextInt();
        int m=scan.nextInt();
        int arrn []=new int[n];
        int arrm []=new int[m];
       
        for(int i=0;i<n;i++){
          arrn[i]=scan.nextInt();
        }
        for(int i=0;i<m;i++){
          arrm[i]=scan.nextInt();
        }
        Set<Long> set =new HashSet<>();
        for(int i=0;i<n;i++){
          for(int j=0;j<m;j++){
          long s=arrn[i]+arrm[j];
          if(s<=(m+n)&&isPrime(s)){
            set.add(s);
          }
        }
        }
        System.out.println(set.size());
        scan.close();
    }
    public static boolean isPrime(long a){
      if (a<2) return false;
      for(long i=2;i*i<=a;i++){
        if(a%i==0){
          return false;
        }
      }
      return true;
    }
}

这样常规的去求解，会导致超时，无法完全通过，这时候就需要质数的埃氏筛法

什么是埃氏筛

埃氏筛（埃拉托斯特尼筛法）是一次性找出一段范围内所有质数的高效算法，专门解决 “多次判断质数导致超时” 的问题。

核心思想

先假设所有数都是质数，再把所有合数（非质数）“筛” 掉，最后剩下的就是质数。

步骤（以筛 2~200 为例）

1. 建表：开一个布尔数组 isPrime，下标代表数字，先把 2~200 全部标记为 true（假设都是质数）。

2. 筛除：从 2开始遍历：

   如果当前数 i 是质数（isPrime[i] = true），就把 i 的所有倍数（从 i*i 开始）都标记为 false（因为它们是合数）。

3. 结果：数组里最后还是 true 的下标，就是质数。

       boolean [] isPrime=new boolean[n+m+1]; // 记录质数的布尔数组
        for(int i=2;i<=n+m;i++) isPrime[i]=true; //先假设所有的数都是质数
        for(int i=2;i*i<=n+m;i++){
          if(isPrime[i]){
            for(int j=i*i;j<=n+m;j+=i){
              isPrime[j]=false;
            }
          }
        }

//  为什么从 i*i 开始标记，而不是从 2*i 开始？
// 	对于质数 i，小于 i*i 的倍数（比如 2i, 3i, ..., (i-1)i），其实已经被更小的质数筛掉了。
//  比如 i=5，2*5=10 已经被 i=2 筛过，3*5=15 被 i=3 筛过，4*5=20 被 i=2 筛过，所以直接从 5*5=25 开始标记就够了。
        Set<Integer> set =new HashSet<>();
        for(int i=0;i<n;i++){
          for(int j=0;j<m;j++){
          int s=arrn[i]+arrm[j];
          if(s>=2&&s<=(m+n)&&isPrime[s]){
            set.add(s);
          }
        }
        }
        System.out.println(set.size());

四、快速幂

1、核心原理

求 a 的 b 次方再取模。

暴力循环会超时，快速幂能秒算

把指数拆成二进制，时间复杂度 O (log n)

2、代码

public static long powMod(long a, long b, long mod) {
    long res = 1;        // 结果初始为 1
    a = a % mod;         // 先取模，防止 a 过大
    while (b > 0) {
        if ((b & 1) == 1) {      // 二进制最后一位是 1
            res = res * a % mod; // 结果乘上当前 a
        }
        a = a * a % mod;         // a 平方
        b = b >> 1;              // 指数除以 2
    }
    return res;
}

def pow_mod(a, b, mod):
    res = 1
    a = a % mod
    while b > 0:
        if b % 2 == 1:
            res = res * a % mod
        a = a * a % mod
        b = b // 2
    return res

例题

数的次幂

五、因数个数统计

1、原理

因数成对出现：

12 = 1×12 = 2×6 =×4

3

所以只需要循环到 √n 就能统计完。

2、代码

int n = sc.nextInt();
int count = 0;
// 循环到根号 n 即可，因数成对出现
for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
        if (i == n / i) {
            count++;        // 平方数，只算一次
        } else {
            count += 2;     // 一对因数
        }
    }
}

System.out.println(count);
n = int(input())
count = 0
for i in range(1, int(n**0.5) + 1):
    if n % i == 0:
        if i == n // i:
            count += 1
        else:
            count += 2
print(count)