兩個正整數最大公約數怎麼求?“模”是指一個計量系統的計數範圍如時鐘等計算機也可以看成一個計量機器，它也有一個計量範圍，即都存在一個“模”例如：，下面我們就來說一說關于兩個正整數最大公約數怎麼求?我們一起去了解并探讨一下這個問題吧!

兩個正整數最大公約數怎麼求

“模”是指一個計量系統的計數範圍。如時鐘等。計算機也可以看成一個計量機器，它也有一個計量範圍，即都存在一個“模”。例如：

時鐘的計量範圍是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。在這樣的系統中減法問題也可以化成加法問題，隻需把減數用相應的補數表示就可以了。把補數用到計算機對數的處理上，就是補碼。

質數（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是否為素數，就像邏輯運算的短路求值。

設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－

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!