一、最大公约数和最小公倍数
最大公约数
正整数a与b的最大公约数是指a与b的所有公约数中最大的那个公约数。一般用gcd(a,b)来表示a和b的最大公约数。例如4和6的最大公约数是2,3和9的最大公约数是3。而求解最大公约数常用欧几里得算法（辗转相除法）。
定理：设a、b均为正整数，则gcd(a,b)=gcd(b,a%b)。
递归式代码：
int gcd(int a,int b)///递归调用 { if(b==0) { return a; } gcd(b,a%b); }
函数调用：
#include<algorithm>///直接使用c++的内置函数 using namespace std; __gcd(int a,int b)
最小公倍数
最小公倍数的求解是在最大公约数的基础上进行的。一般用lcm(a,b)来表示a和b的最小公倍数。
这里需要用到一个公式：lcm(a,b)*gcd(a,b)=a*b
所以 lcm(a,b) = a*b/gcd(a,b)
但在a*b计算时有可能造成溢出，因此更恰当的写法是lcm(a,b) = a/gcd(a,b)*b
二、素数
素数又称质数，是指除了1和本身之外，不能被其他数整除的一类数。即对给定的正整数n，如果对任意的正整数a(1<a<n)，都有n%a！=0成立，那么称n是素数，否则，如果存在a(1<a<n)，有n%=0成立，那么称n为合数。应特别值得注意的是，1既不是素数，也不是合数。
素数的判断
注意到如果在2~n-1中存在n的约数，不妨设为k，即n%k==0，那么由k*(n/k)==n可知，n/k也是n的一个约数，且k与n/k中一定满足其中一个小于等于sqrt(n)，另一个大于等于sqrt(n)。
bool isPrime(int n) { if(n<=1) { return false; } int sqr = (int)sqrt( (double)m ); for(i=2; i<=sqr; i++) { if(n%i==0) return false; } return true; }
如果n没有接近int型变量的范围上界，有更简单的写法：
bool isPrime(int n) { if(n<=1) { return false; } for(i=2; i*i<=n; i++) { if(n%i==0) return false; } return true; }
筛法求素数
逐一判断1~n范围内的素数，总的时间复杂度很高，这里引入筛法求素数。
筛法的理论依据，任何一个数都能拆成多个素数的乘积（唯一分解定理），其思想是筛掉范围内所有的合数，而合数由素数乘积的到，素数的倍数就是合数，那么出现一个素数，我们就筛掉它的倍数。
素数筛法代码：
const int maxn =101;//表长 int prime[maxn];//存放所有素数 int pNum=0;//素数的个数 bool p[maxn]= {0}; //如果i是素数，p[i]为false,否则，p[i]为true 初始化为0 void Find_Prime() { for(int i=2; i<maxn; i++) { if(p[i]==false) //如果i是素数 { prime[pNum++]=i;//把素数i存放到prime数组中 for(int j=i*2; j<maxn; j+=i) { //筛去所有i的倍数，循环条件不能写成j<=maxn p[j]=true; } } } }
求解100以内所有素数代码：
#include<stdio.h> const int maxn =101;//表长 int prime[maxn];//存放所有素数 int pNum=0;//素数的个数 bool p[maxn]= {0}; //如果i是素数，p[i]为false,否则，p[i]为true 初始化为0 void Find_Prime() { for(int i=2; i<maxn; i++) { if(p[i]==false) //如果i是素数 { prime[pNum++]=i;//把素数i存放到prime数组中 for(int j=i*2; j<maxn; j+=i) { //筛去所有i的倍数，循环条件不能写成j<=maxn p[j]=true; } } } } int main() { Find_Prime(); for(int i=0; i<pNum; i++) { printf("%d ",prime[i]); } return 0; }
三、质因子分解
所谓质因子分解是指将一个正整数 n 写成一个或多个质数的乘积形式，例如 24=2*2*2*3。显然，由于最后都要归结到若干不同质数的乘积，不妨先把素数表打印出来。
由于每个质因子都可以不止出现一次，因此不妨定义结构体 factor ，用来存放质因子及其个数，如下所示：
struct factor { int x, cnt; // x 为质因子，cnt 为其个数 } fac[10];
而有一个结论：对一个正整数 n 来说，如果它存在 [2,n] 范围内的质因子，要么这些质因子全部小于等于 sqrt(n) ，要么只存在一个大于 sqrt(n) 的质因子，而其余质因子全部小于等于 sqrt(n) 。这就给进行质因子分解提供了一个很好的思路：
1. 枚举 1~sqrt(n) 范围内的所有质因子 p，判断 p 是否是 n 的因子。如果 p 是 ｎ 的因子，那么给 fac 数组中增加质因子 p ，并初始化其个数为 0。然后只要 p 还是 n 的因子，就让 n 不断除以 p，每次操作令 p 的个数加 1，直到 p 不再是 n 的因子为止。如果p不是质因子，就直接跳过。
if(n % pri[i] == 0) // prime[i] 是质因子 { fac[num].x = pri[i];//记录该质因子 fac[num].cnt = 0; while(n%pri[i] == 0) // 计算该质因子的个数 { fac[num].cnt++; n /= pri[i]; } num++; // 不同质因子个数 +1 }
2. 如果在上面步骤结束后 n 仍然大于 1，说明 n 有且仅有一个大于 sqrt(n) 的质因子（有可能是n本身），这时需要把这个质因子加入 fac 数组，并令其个数为 1。
if(n != 1) // 存在大于 sqrt(n) 的质因子 { fac[num].x = n; fac[num++].cnt = 1; }
至此，fac 数组中存放的就是质因子分解的结果，时间复杂度为O(根号n)。