前言

数论是蓝桥杯、洛谷、LeetCode 算法竞赛的高频考点，核心围绕质数、质因子分解、欧拉函数、数论性质展开。本文把所有必学知识点、模板、结论一次性整理完毕，新手也能直接上手。

一、质因数分解（试除法）

核心用途

分解一个数的质因子，统计质因子总个数（含重复），是数论最基础操作。

原理

唯一分解定理：任意大于1的正整数可唯一分解为质数乘积。

模板代码（统计质因子总个数）

# 功能：计算n的质因子总个数（重复计数）
n = int(input())
ans = 0
# 试除法枚举到根号n
for i in range(2, int(n ** 0.5)+1):
    # 除尽当前质因子
    while n % i == 0:
        ans += 1
        n //= i
# 剩余大于1的数，是最后一个质因子
if n > 1:
    ans += 1

print(ans)

二、线性筛（欧拉筛）最优模板

核心特点

• 时间复杂度 $O(n)$，每个合数仅被最小质因子筛一次，无重复、无遗漏
• 可批量筛质数、预处理最小质因子、搭配欧拉函数使用

经典例题：洛谷 P3383 【模板】线性筛素数

https://www.luogu.com.cn/problem/P3383

模板代码（筛质数 + 多次查询第k个质数）

import sys
# 竞赛快速读入（避免大数据超时）
input = lambda: sys.stdin.read()
a = list(map(int, input().split()))
Q = a[2:]
n, q = a[0], a[1]

primes = []
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False

for i in range(2, n+1):
    if is_prime[i]:
        primes.append(i)
    for p in primes:
        if i * p > n:
            break
        is_prime[i*p] = False
        # 核心：保证线性复杂度，仅被最小质因子筛除
        if i % p == 0:
            break

# 处理查询
ans = [str(primes[x-1]) for x in Q]
print('\n'.join(ans))

三、欧拉函数 φ(n) 两大模板

欧拉函数定义

$\phi (n)$：1~n 中与 n 互质的数的个数

核心公式

1. 质数 $p$：$\phi (p)=p-1$
2. 积性函数：若 $a,b$ 互质，则 $\phi (ab)=\phi (a)\phi (b)$
3. 幂次公式：$\phi (a^b)=\phi (a)\times a^{b-1}$

1. 试除法求单个数的欧拉函数

经典例题：蓝桥杯 互质数的个数

https://www.lanqiao.cn/problems/3522/learning/

a, b = map(int, input().split())
mod = 998244353

# 试除法计算欧拉函数
def phi(x):
    ans = x
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            ans = ans // i * (i-1)
            # 除尽当前质因子
            while x % i == 0:
                x //= i
    if x > 1:
        ans = ans // x * (x-1)
    return ans % mod

# 公式：φ(a^b) = φ(a) * a^(b-1)
print((phi(a) * pow(a, b-1, mod)) % mod)

2. 线性筛批量求欧拉函数（最优）

搭配线性筛，批量计算 1~n 所有数的欧拉函数，竞赛大数据必备：

n = int(input())

primes = []
phi = [0] * (n+1)
phi[1] = 1  # 边界：φ(1)=1
is_prime = [True] * (n+1)
is_prime[0] = is_prime[1] = False

for i in range(2, n+1):
    if is_prime[i]:
        primes.append(i)
        phi[i] = i - 1  # 质数的欧拉函数
    for p in primes:
        if i * p > n:
            break
        is_prime[i*p] = False
        if i % p == 0:
            # p是i的质因子，不互质
            phi[i*p] = p * phi[i]
            break
        else:
            # p与i互质，积性函数性质
            phi[i*p] = (p-1) * phi[i]

四、竞赛秒杀结论：2的幂次专属性质

核心结论

1. 判断一个数是否是 2 的幂次
   位运算秒杀：n & (n-1) == 0
   （前提：n > 0）
2. 2 的幂次 无法表示为 连续自然数之和
   反之：不是 2 的幂次的数，一定可以拆成连续自然数之和

证明核心

连续自然数求和公式：
$S=\frac{k\times (2a+k-1)}{2}$
若 $S=2^m$，则 $k$ 和 $2a+k-1$ 必须一奇一偶，但 $2^m$ 无奇数因子，无解。

代码判断2的幂次

def is_power_of_two(n):
    return n > 0 and (n & (n-1)) == 0

五、全文总结（考场速记）

1. 质因子分解：试除法枚举到 $\sqrt{n}$，除尽所有质因子
2. 线性筛：每个合数仅被最小质因子筛除，$O(n)$ 无重复无遗漏
3. 欧拉函数
   • 质数：$\phi (p)=p-1$
   • 互质：$\phi (ab)=\phi (a)\phi (b)$
   • 幂次：$\phi (a^b)=\phi (a)\times a^{b-1}$
4. 2的幂次：n&n-1==0，无法拆分为连续自然数之和