“?！笔侵敢粋€(gè)計(jì)量系統(tǒng)的計(jì)數(shù)范圍。如時(shí)鐘等。計(jì)算機(jī)也可以看成一個(gè)計(jì)量機(jī)器，它也有一個(gè)計(jì)量范圍，即都存在一個(gè)“模”。例如：
時(shí)鐘的計(jì)量范圍是0～11，模=12。表示n位的計(jì)算機(jī)計(jì)量范圍是0～2^(n)-1，模=2^(n)。
“?！睂?shí)質(zhì)上是計(jì)量器產(chǎn)生“溢出”的量，它的值在計(jì)量器上表示不出來，計(jì)量器上只能表示出模的余數(shù)。任何有模的計(jì)量器，均可化減法為加法運(yùn)算。
例如：假設(shè)當(dāng)前時(shí)針指向10點(diǎn)，而準(zhǔn)確時(shí)間是6點(diǎn)，調(diào)整時(shí)間可有以下兩種撥法：一種是倒撥4小時(shí)，即：10-4=6；另一種是順撥8小時(shí)：10+8=12+6=6
在以12模的系統(tǒng)中，加8和減4效果是一樣的，因此凡是減4運(yùn)算，都可以用加8來代替。對“?！倍?，8和4互為補(bǔ)數(shù)。實(shí)際上以12模的系統(tǒng)中，11和1，10和2，9和3，7和5，6和6都有這個(gè)特性。共同的特點(diǎn)是兩者相加等于模。
對于16進(jìn)制，16就是這個(gè)進(jìn)制系統(tǒng)中的模，其使用的字符只有：0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F。
對于8進(jìn)制，8就是這個(gè)進(jìn)制系統(tǒng)中的模，其使用的字符只有：0,1,2,3,4,5,6,7。
對于2進(jìn)制，2就是這個(gè)進(jìn)制系統(tǒng)中的模，其使用的字符只有：0,1。
對于計(jì)算機(jī)，其概念和方法完全一樣。n位計(jì)算機(jī)，設(shè)n=8， 所能表示的最大數(shù)是11111111，若再加1成為100000000(9位），但因只有8位，最高位1自然丟失。又回了00000000，所以8位二進(jìn)制系統(tǒng)的模為2^8。在這樣的系統(tǒng)中減法問題也可以化成加法問題，只需把減數(shù)用相應(yīng)的補(bǔ)數(shù)表示就可以了。把補(bǔ)數(shù)用到計(jì)算機(jī)對數(shù)的處理上，就是補(bǔ)碼。
質(zhì)數(shù)（prime number）又稱素?cái)?shù)，有無限個(gè)。質(zhì)數(shù)定義為在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)。
isPrime沒有必要枚舉所有的因子。
I 只要發(fā)現(xiàn)任何一個(gè)大于1小于n的因子，就能停下來報(bào)告n不是素?cái)?shù)。
II 如果n能被2整除，直接報(bào)告n不是素?cái)?shù)。如果n不能被2整除，那么它也不可能被4或6或其他偶數(shù)整除。因此，isPrime只需要檢查2和奇數(shù)（由3開始，步長為2）。但注意有個(gè)特例，2能被2整除，但2是素?cái)?shù)。
III 如果n不是素?cái)?shù)，則必有一個(gè)因子小于√n 。因此不需要檢查到n為止。只需檢查到√n 。
因?yàn)槿绻鹡能被2~n-1之間任一整數(shù)整除，其二個(gè)因子必定有一個(gè)小于或等于√n，另一個(gè)大于或等于√n。例如24可以表示為：2*12、3*8、4*6，前面的因子小于√24，后面的因子大于√24，檢驗(yàn)出了小因子，即可判斷n是否為素?cái)?shù)，就像邏輯運(yùn)算的短路求值。
設(shè)c是a、b的最大公約數(shù)，記為c=gcd(a,b)，a>=b
令r=a mod b
要證明b與r的最大公約數(shù)也是c
設(shè)a=kc，b=jc，則k、j互素，否則c不是最大公約數(shù)。
設(shè)m為任一整數(shù)。
據(jù)上，r=a-mb=kc-mjc=(k-mj)c
可知r也是c的倍數(shù)，且k-mj與j互素，否則與前述k，j互素矛盾。
由此可知，b與r的最大公約數(shù)也是c，即gcd(a,b)=gcd(b,a mod b)。
這樣就可以通過不斷求余、不斷互換，直到余數(shù)為零，最后的結(jié)果就是最大公約數(shù)。
I a ÷ b，令r為所得余數(shù)（0≤r ）
II 互換：置 a←b，b←r，并返回第一步。
最小公倍數(shù)=兩數(shù)之積除于它們的最大公約數(shù)。
實(shí)例：
輸入兩個(gè)正整數(shù)m和n，求其最大公約數(shù)和最小公倍數(shù)。
－End－
