数论：掌握辗转相除法、素数预算与快速幂计算

文章结构概述

• 求最大公约数的辗转相除法
  • 利用枚举方式获取小于等于n的素数-埃拉托斯特尼筛法
  • 高效计算幂次的快速幂算法

辗转相除法-最大公约数

辗转相除法是一种用于计算最大公约数的途径。其具体实施方式为：以较小的数值去除较大的数值，随后使用所得余数（即第一余数）去除之前的除数，再以新出现的余数（第二余数）去除第一余数，如此循环操作，直至最终余数为零时终止。若目标是确定两个数值的最大公约数，则此时所使用的最后一个除数即为这两个数值的最大公约数。这种方法与更相减损术在本质上具有相似之处。

首先对更相减损术的基本原理进行说明，假设存在两个数值161与63，我们希望求得它们的最大公因数，暂且设该最大公因数为m。可以将较大的数值161视为由63+98组成，由于161可被m整除，并且63同样可被m整除，则98也必然能够被m整除；

因此问题就转化为寻找98与63之间的最大公因数m（与之前设定的m相同）

接着将98表示为63+35的形式，其中63可被m整除，而98同样能够被m整除，则可以推断出35也可以被m整除；

因此问题进一步转化为寻找35与63之间的最大公因数m（仍与之前设定的m一致）

同理继续转换为求 (63-35)=28 与 35 的最大公因数
再进一步转换为求28和7的最大公因