汉扬编程 编程大纲 C|模数、素数,辗转相除法的证明及求最大公约数和最小公倍数

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-

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/mianfei/5851.html

你所不知道的C语言:指针篇

很多学C语言的人不知道的事儿,小数是如何存储的?二进制白学了

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部