1 模数
“模”是指一个计量系统的计数范围。如时钟等。计算机也可以看成一个计量机器，它也有一个计量范围，求公约数的最简单方法，即都存在一个“模”。例如：，
时钟的计量范围是0～11，模=12。表示n位的计算机计量范围是0～2^(n)-1，模=2^(n)。
最大公约数的求法一共有三种：1、找查约数法：分别找出两个数的所有约数，再找出两个数的所有公约数，最大的那个就是最大公约数。2、更相减损法：任意两个数，判定是否为偶数，是就用2约简，不是就用较大的数减较。
对于16进制，16就是这个进制系统中的模，其使用的字符只有：0，1，2，3，4，5，6，7，8，9，A，B，C，D，E，F。
对于8进制，8就是这个进制系统中的模，其使用的字符只有：0，1，2，3，4，5，6，7。
对于2进制，2就是这个进制系统中的模，其使用的字符只有：0，1。
对于计算机，其概念和方法完全一样。n位计算机，设n=8， 所能表示的最大数是11111111，若再加1成为100000000(9位），但因只有8位，最高位1自然丢失。又回了00000000，所以8位二进制系统的模为2^8。在这样的系统中减法问题也可以化成加法问题，只需把减数用相应的补数表示就可以了。把补数用到计算机对数的处理上，就是补码。
2 素数
质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
int isPrime(int n){ if(n<= 1)// 小于等于1的整数不可能是素数 return 0; if(n == 2); // 2 是素数 return 1; if(n%2 == 0); // 能被2整除的其他整数都不是素数 return 0; int limit = (int)sqrt((double)n)+1; for(int i = 3; i <= limit; i=i+2) { if(n % i == 0) return 0; } return 1;}
isPrime没有必要枚举所有的因子。
I 只要发现任何一个大于1小于n的因子，就能停下来报告n不是素数。
最大公约数求算法方法如下：三个方法实现求两个数的最大公约数：1、辗转相除法：取两个数中最大的数做除数，较小的数做被除数，用最大的数除较小数，如果余数为0，则较小数为这两个数的最大公约数，如果余数不为0。
III 如果n不是素数，则必有一个因子小于√n 。因此不需要检查到n为止。只需检查到√n 。
3 用辗转相除法（又名欧几里德算法）求最大公约数和最小公倍数
设c是a、b的最大公约数，记为c=gcd(a，b)，a>=b
令r=a mod b
要证明b与r的最大公约数也是c
设a=kc，b=jc，则k、j互素，否则c不是最大公约数。
设m为任一整数。
辗转相除法和更相减损术以及短除法都可以求最大公约数1.辗转相除法例：求80和36的最大公约数80=36*2+836=8*4+48=4*2+0所以最大公约数是42算法：就是用小数除大数，如果余数不是零，就把余数和较小的数构成一。
据上，r=a-mb=kc-mjc=(k-mj)c
可知r也是c的倍数，且k-mj与j互素，否则与前述k，j互素矛盾。
由此可知，b与r的最大公约数也是c，即gcd(a，b)=gcd(b，a mod b)。
这样就可以通过不断求余、不断互换，直到余数为零，最后的结果就是最大公约数。
I a ÷ b，令r为所得余数（0≤r ）
辗转相除法也叫欧几里德算法。用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就。
II 互换：置 a←b，b←r，并返回第一步。
最小公倍数=两数之积除于它们的最大公约数。
实例：
最简单的算公约数的方法叫做：辗转相除法.比如求145和25的公约数 先用145减去25的若干倍,使得减剩下的数比25小.也就是145-5乘以25=20.然后只需要求25和20的公约数,重复上述过程：用25减去20的若干倍,使得减剩下的数。
输入两个正整数m和n，求其最大公约数和最小公倍数。
#include<iostream>using namespace std;int isPrime(int n);int main(){ int a，b，t，r; printf("请输入两个数字：\n"); scanf("%d %d"，&a，&b); if(a<b) {t=b;b=a;a=t;} r=a%b; int n=a*b; while(r!=0) { a=b; b=r; r=a%b; } printf("这两个数的最大公约数是%d，最小公倍数是%d\n"，b，n/b); system("pause"); return 0;}/*请输入两个数字：18 24这两个数的最大公约数是6，最小公倍数是72/*同样对于两个数1，000，005和1，000，000，用欧几里得算法只需要执行两次循环体。
－End－
