最大公約數

鎖定

質因數分解(9張)

質因數分解法：把每個數分別分解質因數，再把各數中的全部公有質因數提取出來連乘，所得的積就是這幾個數的最大公約數。

import java.util.Scanner;
public class Six {
public static void main(String[] args) {
System.out.print("請輸入a和b");
Scanner scan = new Scanner(System.in);//以空格作為分隔符
int a = scan.nextInt();
int b = scan.nextInt();
int middle1,middle2,middle3;
middle1=a;
middle2=b;
middle3=0;
for (int i=0;i<i+1;i++) {
middle3=middle1%middle2;
if(middle3==0)
break;
else{
middle1=middle2;
middle2=middle3;
}
}
System.out.println("最大公約數為："+middle2);
}
}

programzuidagongyueshu;
var
m,n,a,b,r:integer;
begin//主程序
write('Inputm,n=');
readln(m,n);
a:=m;
b:=n;
repeat
r:=amodb;
a:=b;
b:=r;
untilr b=0;
writeln('Thegreatestcommondivideis:',a);
end.

programgcd;
var
k,a,b:integer;
functiongcd(a,b:integer):integer;
begin
ifamodb=0thenexit(b)
elsegcd:=gcd(b,amodb);
end;

begin
readln(a,b);
k:=gcd(a,b);
writeln(k);
end.

#include<stdio.h>
int main()
{
    int m,n,i;
    scanf("%d",&m);
    scanf("%d",&n);
    for(i=m;i>=1;i--)
        if(m%i==0 && n%i==0)
            break;
    printf("%d\n",i);
    return 0; 
}

1.C語言程序如下：
#include <stdio.h>
#include <math.h>
/*
 * 最大公約數的遞歸：
 * 1、若a可以整除b，則最大公約數是b
 * 2、如果1不成立，最大公約數便是b與a%b的最大公約數
 * 示例：求(140,21)
 * 140%21 = 14
 * 21%14 = 7
 * 14%7 = 0
 * 返回7
 * */
int gcd(int a,int b){
 if(a%b==0)
  return b;
 return gcd(b,a%b);
}
int main(void){
 int a=10,b=8;
 scanf("%d %d",&a,&b);
 printf("GCD: A=>%d, B=>%d (A,B)=%d\n",a,b,gcd(a,b));
 return 0;
}

C++:
int gcd(int a,int b)
{
    int temp;
    while(b)
    {    
        /*利用輾除法，直到b為0為止*/
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n;
    cin>>m>>n;
    cout<<__gcd(m,n);
}
分數的最大公約數為：例（5/6，5/9）=（5,5）/【6,9】=5/18
遞歸算法(c++實現)

2.C++程序如下：
#include<cstdio>
int GCD(int a,int b)
{
    return a%b?GCD(b,a%b):b;
}
int main()
{
    int x,y;
    scanf("%d%d",&x,&y);
    printf("%d",GCD(x,y));
    return 0;
}



3.輾轉相除法(Matlab實現)
function GCD=Euclid(m,n) 
%輾轉相除法(即歐幾里德算法)。
r=mod(m,n);
while r~=0
    r=mod(m,n);
    m=n;
    n=r;
end
GCD=m;


>> m=319;n=377;Euclid(m,n)
ans =
    29

4.遞歸算法（Python實現）
def gcd(n1,n2):
    """greatest common divisor function """
    if(n1%n2 == 0):
        return n2
    return gcd(n2,n1%n2)

參考資料

• 1.    如何理解“更相減損法”中的可半者半之？？  ．草蓆.海賊喊抓賊的地方[引用日期2013-06-14]
• 2.    輾轉相除法與更相減損術  ．孫麗君博客[引用日期2013-06-14]
• 3.    C++算法：輾轉相除法與更相減損術  ．潘學軍博客[引用日期2013-06-14]
• 4.    擴展的歐幾里得算法  ．紅黑聯盟[引用日期2013-06-14]
• 5.    歐幾里德與擴展歐幾里德算法  ．jumping_frog博客[引用日期2013-06-14]
• 6.    歐幾里德算法 vs Stein算法——求最大公倍數  ．深呼空氣的空間[引用日期2013-06-14]
• 7.    最大公約數(Gcd)兩種算法(Euclid && Stein)  ．一切隨心博客[引用日期2013-06-14]