1樓：網友
電腦程式設計藝術》第一卷第一頁開始講的就是歐幾里德演算法。
去下一本自己看吧。沒有比那裡講得還詳細的了。
最大公約數的作用
2樓：新野旁觀者
最大公約數。
和最小公倍數有很多作用：
先不說計算題要用到的吧。
說生活方面的：
最大公約數：長8公尺和12公尺的鋼管，要截成最長但不能有剩餘，最長是多少？有多少段？
最小公倍數：電力公司對線路改裝，原來45公尺一根電杆，現改為30公尺一根電杆。原來9千公尺的線路，有多少根電杆不用移？
什麼是最大公約數，它有什麼用處？
3樓：網友
最大公約數。
就是幾個數中共有的約數中最大的那個數。
演算法通常歐幾里德演算法。
大素數。的時候會採用stein演算法。
最小公倍數。
是幾個數共有的銀脊倍數中最小的那個數。
求出最大公約數後，可以直接用兩數的乘積除以它們的最改跡大公約數，得到最小公倍數。
為什麼沒有最小公約數和最大公倍數。
在數學裡我們曾學過最大公約數以及最小公倍數。或許你會提出問題，為什麼公約數要講最大，但公倍數卻又講最小呢？是否有最小公約數和最大公倍數呢？假如有的話，為什麼不講呢？
奧開網。我們首先從乙個具體情況來看：
奧開網。例如有正整數。
16和24，它們有很多公約數，就是，它們的最大公約數是8，最小公約數是1。
奧開網。再看正整數15和56，它們都只有乙個公約數，就是1。我們從這裡能看出，任何兩個正整數，總會有公約數1，且1總是它們的最小公約數(公約數總是隻講整數的)。
兩個或兩個以上的數，它們的最小公約數既然總是1，就不必討論了。這也就是我們不談最小公約數的道理。但這並不是主要的道理。
主要的道理在**呢？
奧開網。我們學習數學，主要的目的是，必須要數學知識為我們服務，而不只是拿數學知識做遊戲。兩個正整數的最大公約數，在分數約分裡是用得到的。
通過約去分子分母的最大公約數，我們就能把乙個分數化成最簡分數。這樣就相當簡單了。而最小公約數1，卻沒有什麼用處。
這就是我們不研究最小公約數的原因。
奧開網。那麼，兩個正整數是否有最大公倍數呢？例如有兩個正整數16和24，它們的最小公倍數是48。顯然48乘核搏並上任何整數之後依然就是16和24的公倍數。
奧開網。例如48×2＝96，48×3＝144，48×4＝192，48×1000＝48 000等都是16和24的公倍數。由於自然數。
沒有最大的數，因此也就沒有最大的公倍數。
奧開網。實際上，在分數通分的時候，也只須用到最小公倍數。假如用較大的公倍數，還不方便。既然沒有最大公倍數，也不需任何較大的公倍數，這就是我們只研究最小公倍數的原因。
最大公約數求法
4樓：咿呀嚕嚕嚕嚕嚕
求最大公約數有多種方法，常見的有質因數分解法、短除法、輾轉相除法、更相減損法。如果有乙個自然數a能被自然數b整除，則稱a為b的倍數，b為a的約數。幾個自然數公有的約數，叫做這幾個自然數的公約數。
公約數中最大的乙個公約數，稱為這幾個自然數的最大公約數。下面就來介紹其中一種。
輾轉相除法。
使用到的原理很聰明也很簡單，假設用f（x,y）表示x，y的最大公約數，取k=x/y，b=x%y，則x=ky+b，如果乙個數能夠同時整除x和y，則必能同時整除b和y；而能夠同時整除b和y的數也必能同時整除x和y，即x和y的公約數與b和y的公約數是相同的，其最大公約數也是相同的，則有f（x,y）=f（y,x%y）（y>0），如此便可把原問題轉化為求兩個更小數的最大公約數，直到其中乙個數為0，剩下的另外乙個數就是兩者最大的公約數。
例如，12和30的公約數有，其中6就是12和30的最大公約數。
關於最大公約數定理的證明過程,關於最大公約數一個定理的證明過程
k,n 表示的意思是k和n的最大公約數。這個定理的意思是元素a的階是n，a k的階就是n除以k和n的最大公約數。算術基本定理的證明 算術基本定理的最早證明是由歐幾里得給出的。而以下是用現代的陳述方式去證明。待證命題 大於1的自然數必可寫成質數的乘積。用反證法 假設存在大於1的自然數不能寫成質數的乘積...
用歐幾里得演算法求32和24的最大公約數
32和24的最大公約數是 8 32 2x2x2x2x2 24 2x2x2x3 32和24的最大公約數是 8 如何用歐幾里德演算法球32和24的最大公約數 32和24的最大公約數 8 32 4x8 24 3x8 所以32和24的最大公約數 8 用歐幾里得演算法 輾轉相除法 求最大公約數,c語言程式設計...
c語言程式設計如何求最大公約數，C語言程式設計如何求最大公約數
源程式如下 include include int fun y int,int int main int fun y int x,int y return i 忙了半天，分採納，謝謝了 常規方法 include stdio.h int main while d2 0 printf 最大公約數是 d ...