題目 輸入兩個正整數m和n,求其最大公約數和最小公倍數。用C語言程式設計

時間 2021-08-16 10:13:10

1樓:匿名使用者

<1> 用輾轉相除法求最大公約數

演算法描述:

m對n求餘為a, 若a不等於0

則 m <- n, n <- a, 繼續求餘

否則 n 為最大公約數

<2> 最小公倍數 = 兩個數的積 / 最大公約數

#include

int main()

printf("greatest common divisor: %d\n", n_cup);

printf("lease common multiple : %d\n", m * n / n_cup);

} else printf("error!\n");

return 0;

} ★ 關於輾轉相除法, 搜了一下, 在我國古代的《九章算術》中就有記載,現摘錄如下:

約分術曰:「可半者半之,不可半者,副置分母、子之數,以少減多,更相減損,求其等也。以等數約之。」

其中所說的「等數」,就是最大公約數。求「等數」的辦法是「更相減損」法,實際上就是輾轉相除法。

輾轉相除法求最大公約數,是一種比較好的方法,比較快。

對於52317和75569兩個數,你能迅速地求出它們的最大公約數嗎?一般來說你會找一找公共的使因子,這題可麻煩了,不好找,質因子大。

現在教你用輾轉相除法來求最大公約數。

先用較大的75569除以52317,得商1,餘數23252,再以52317除以23252,得商2,餘數是5813,再用23252做被除數,5813做除數,正好除盡得商數4。這樣5813就是75569和52317的最大公約數。你要是用分解使因數的辦法,肯定找不到。

那麼,這輾轉相除法為什麼能得到最大公約數呢?下面我就給大夥談談。

比如說有要求a、b兩個整數的最大公約數,a>b,那麼我們先用a除以b,得到商8,餘數r1:a÷b=q1…r1我們當然也可以把上面這個式子改寫成乘法式:a=bq1+r1------l)

如果r1=0,那麼b就是a、b的最大公約數3。要是r1≠0,就繼續除,用b除以r1,我們也可以有和上面一樣的式子:

b=r1q2+r2-------2)

如果餘數r2=0,那麼r1就是所求的最大公約數3。為什麼呢?因為如果2)式變成了b=r1q2,那麼b1r1的公約數就一定是a1b的公約數。

這是因為一個數能同時除盡b和r1,那麼由l)式,就一定能整除a,從而也是a1b的公約數。

反過來,如果一個數d,能同時整除a1b,那麼由1)式,也一定能整除r1,從而也有d是b1r1的公約數。

這樣,a和b的公約數與b和r1的公約數完全一樣,那麼這兩對的最大公約數也一定相同。那b1r1的最大公約數,在r1=0時,不就是r1嗎?所以a和b的最大公約數也是r1了。

有人會說,那r2不等於0怎麼辦?那當然是繼續往下做,用r1除以r2,……直到餘數為零為止

2樓:

//輸入的兩個數請用空格分隔,如:12 18#include

int main()

p=n*m;

while(m!=0)

printf("它們的最大公約數為:%d\n",n);

printf("它們的最小公約數為:%d\n",p/n);

return 0;}

3樓:

我這個要複雜點:

#include

void main()

if(t%s==0)

else

for(i=t-1;i>=1;i--)}

4樓:歐文君愛分享

main()

a=num1;b=num2;

while(b!=0)/*利用輾除法,直到b為0為止*/printf("gongyueshu:%d\n",a);

printf("gongbeishu:%d\n",num1*num2/a);}

c語言程式設計:輸入兩個正整數m和n,求其最大公約數和最小公倍數。

5樓:冠夏登溪

用了一種比bai較笨的方法,du但是好理解zhi,希望對你有幫助dao

。#include

void

main()

//這個函式用於求最小公倍數

intmin_num(int

x,int

y)returni;}

//這個函式用於求最大公約數

intmax_num(int

x,int

y)returni;}

6樓:i樂於助人

#include

int main()

printf("greatest common divisor: %d\n", n_cup);

printf("lease common multiple : %d\n", m * n / n_cup);

} else printf("error!\n");

return 0;}

7樓:蘭昂位力

#include

using

namespace

std;

intmain()

用c語言編寫程式:輸入兩個正整數m,n.求其最大公約數和最小公倍數

8樓:匿名使用者

#include "stdio.h"

void main()

9樓:林柯伊南

#include"stdio.h"

main()

while (m%n!=0)

a=a/n;b=b/n;q=a*b*n;

printf("兩數最大公約數為

%d,最小公倍數為 %d\n",n,q);}

10樓:匿名使用者

if (n>m)

while (m%n)

演算法就是用輾轉相除法求最大公約

數演算法描述:

m對n求餘為a, 若a不等於0

則 m <- n, n <- a, 繼續求餘否則 n 為最大公約數

11樓:桔聚聚

還要考慮如果m/n等於零的情況

c語言程式設計:輸入兩個正整數m和n,求其最大公約數和最小公倍數,急!急!

12樓:彭玉英赫嬋

用了一種比較笨的方法,但是好理解,希望對你有幫助。

#include

void

main()

//這個函式用於求最小公倍數

intmin_num(int

x,int

y)returni;}

//這個函式用於求最大公約數

intmax_num(int

x,int

y)returni;}

13樓:靖蓄宇辰錕

#include

intmain()

printf("greatest

common

divisor:

%d\n",

n_cup);

printf("lease

common

multiple

:%d\n",m*

n/n_cup);

}else

printf("error!\n");

return0;}

14樓:匿名使用者

main()

p=n*m;//p是原來兩個數n,m的乘積.

while(m!=0)//求兩個數n,m的最大公約數.

printf("its maxgongyueshu:%d\n",n);//列印最大公約數.

printf("its mingongbeishu:%d\n",p/n);列印最小公倍數.

基本原理如下:

用歐幾里德演算法(輾轉相除法)求兩個數的最大公約數的步驟如下:

先用小的一個數除大的一個數,得第一個餘數;

再用第一個餘數除小的一個數,得第二個餘數;

又用第二個餘數除第一個餘數,得第三個餘數;

這樣逐次用後一個數去除前一個餘數,直到餘數是0為止。那麼,最後一個除數就是所求的最大公約數(如果最後的除數是1,那麼原來的兩個數是互質數)。

例如求1515和600的最大公約數,

第一次:用600除1515,商2餘315;

第二次:用315除600,商1餘285;

第三次:用285除315,商1餘30;

第四次:用30除285,商9餘15;

第五次:用15除30,商2餘0。

1515和600的最大公約數是15。

兩個正整數的最小公倍數=兩個數的乘積÷兩個數的最大公約數

由於兩個數的乘積等於這兩個數的最大公約數與最小公倍數的積。這就是說,求兩個數的最小公倍數,可以先求出兩個數的最大公約數,再用這兩個數的最大公約數去除這兩個數的積,所得的商就是兩個數的最小公倍數。

例 求105和42的最小公倍數。

因為105和42的最大公約數是21,

105和42的積是4410,4410÷21=210,

所以,105和42的最小公倍數是210。

c++實現輸入兩個正整數m和n,求其最大公約數和最小公倍數?

15樓:凌亂心扉

#include "stdio.h"

void main()

}if(i == c+1)

printf("沒有最大公約數 ");

c = m > n ? m : n ;           // 取 m n 中較大的數,賦值給c //

for (i = c ; i <= m*n; i++)}}

16樓:

#include

using namespace std;

int main()

num1 = a;

num2 = b;

while(num2 != 0)

cout << "最大公約數為:" << num1<< " 最小公倍數為:" << (a * b) / num1 << endl;

return 0;}

c語言程式設計:輸入兩個正整數,求最大公約數和最小公倍數

17樓:匿名使用者

1、新建一個

工程來和.c檔案 ,輸入標頭檔案和源主函式。

2、定義變數型別。

3、接下來需要輸入a和b。

4、用一個if 語句去判斷這兩個數是否大於1。

5、用while 語句去求得最大公倍數和最小公約數。

6、輸出最大公約數和最小公倍數。

7、編譯,執行得到最後的結果。

18樓:凌亂心扉

#include

int main()

p=n*m;

while(m!=0)

printf("它們的最大公約數為:%d\n",n);

printf("它們的最小公約數為:%d\n",p/n);

return 0;}方法

二、//窮舉法解兩個數的最大公約數和最小公倍數void exp(int num1,int num2)

19樓:匿名使用者

main()

printf("its maxgongyueshu:%d\n",n);//列印最大公約數.

printf("its mingongbeishu:%d\n",p/n);列印最小公倍數.

基本原理如下:

用歐幾里德演算法(輾轉相除法)求兩個數的最大公約數的步驟如下:

先用小的一個數除大的一個數,得第一個餘數;

再用第一個餘數除小的一個數,得第二個餘數;

又用第二個餘數除第一個餘數,得第三個餘數;

這樣逐次用後一個數去除前一個餘數,直到餘數是0為止。那麼,最後一個除數就是所求的最大公約數(如果最後的除數是1,那麼原來的兩個數是互質數)。

例如求1515和600的最大公約數,

第一次:用600除1515,商2餘315;

第二次:用315除600,商1餘285;

第三次:用285除315,商1餘30;

第四次:用30除285,商9餘15;

第五次:用15除30,商2餘0。

1515和600的最大公約數是15。

兩個正整數的最小公倍數=兩個數的乘積÷兩個數的最大公約數

由於兩個數的乘積等於這兩個數的最大公約數與最小公倍數的積。這就是說,求兩個數的最小公倍數,可以先求出兩個數的最大公約數,再用這兩個數的最大公約數去除這兩個數的積,所得的商就是兩個數的最小公倍數。

例 求105和42的最小公倍數。

因為105和42的最大公約數是21,

105和42的積是4410,4410÷21=210,

所以,105和42的最小公倍數是210。

C語言程式設計 輸入兩個正整數m和n,求其最大公約數和最小公倍數,急!急

彭玉英赫嬋 用了一種比較笨的方法,但是好理解,希望對你有幫助。include void main 這個函式用於求最小公倍數 intmin num int x,int y returni 這個函式用於求最大公約數 intmax num int x,int y returni 靖蓄宇辰錕 include...

輸入兩個正整數m和n,求其最大公約數和最小公倍數

include int main int a,b,num1,num2,temp printf please input two number n scanf d d num1,num2 if num1temp num1 num1 num2 num2 temp a num1 b num2 while ...

C語言 程式設計輸入正整數m和n mn ,求S 1 n。結果保留10位小數,咋寫

雲舒輕寒 include main int m,n,i double s 0 scanf d d m,n for i 0 i n m i s 1.0 m i printf 10lf n s 文字 include stdio.h int main int argc,char ar double s i...