两个正整数最大公约数怎么求（C模数素数）

“模”是指一个计量系统的计数范围如时钟等计算机也可以看成一个计量机器，它也有一个计量范围，即都存在一个“模”例如：，下面我们就来说一说关于两个正整数最大公约数怎么求?我们一起去了解并探讨一下这个问题吧!

两个正整数最大公约数怎么求

1 模数

“模”是指一个计量系统的计数范围。如时钟等。计算机也可以看成一个计量机器，它也有一个计量范围，即都存在一个“模”。例如：

时钟的计量范围是0～11，模=12。表示n位的计算机计量范围是0～2^(n)-1，模=2^(n)。

“模”实质上是计量器产生“溢出”的量，它的值在计量器上表示不出来，计量器上只能表示出模的余数。任何有模的计量器，均可化减法为加法运算。

例如：假设当前时针指向10点，而准确时间是6点，调整时间可有以下两种拨法：一种是倒拨4小时，即：10-4=6；另一种是顺拨8小时：10 8=12 6=6

在以12模的系统中，加8和减4效果是一样的，因此凡是减4运算，都可以用加8来代替。对“模”而言，8和4互为补数。实际上以12模的系统中，11和1，10和2，9和3，7和5，6和6都有这个特性。共同的特点是两者相加等于模。

对于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不是素数。

II 如果n能被2整除，直接报告n不是素数。如果n不能被2整除，那么它也不可能被4或6或其他偶数整除。因此，isPrime只需要检查2和奇数（由3开始，步长为2）。但注意有个特例，2能被2整除，但2是素数。

III 如果n不是素数，则必有一个因子小于√n 。因此不需要检查到n为止。只需检查到√n 。

因为如果n能被2~n-1之间任一整数整除，其二个因子必定有一个小于或等于√n，另一个大于或等于√n。例如24可以表示为：2*12、3*8、4*6，前面的因子小于√24，后面的因子大于√24，检验出了小因子，即可判断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为任一整数。

据上，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，并返回第一步。

最小公倍数=两数之积除于它们的最大公约数。

实例：

输入两个正整数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－

,