数论基础，从入门到入门

一、常用算法

• 1.素数筛法
• 2.线性筛
• 3.快速幂
• 4.矩阵快速幂
• 5.辗转相除法/欧几里得算法
• 6.扩展欧几里得
• 7.中国剩余定理/CRT

---

一、常用算法

1.素数筛法

2.线性筛

大部分只需要判断素数的问题，埃氏筛已经够优秀了
但是一部分题需要更大的素数范围或需要快速求一些积性函数的问题，此时需要用到线性筛

• 我们发现埃氏筛在筛的过程中，同一个数字会被筛去很多次，正是这一步限制了它的效率
• 线性筛的优化在于每个数字只会被它的最小素因子筛去，每个数字只会被筛去一次

3.快速幂

4.矩阵快速幂

5.辗转相除法/欧几里得算法

6.扩展欧几里得

7.中国剩余定理/CRT