希腊欧几里得算法

2025年6月13日 | 阅读3分钟

欧几里得算法是一种数学算法。该算法通常用于查找两个正整数的最大公约数。该算法以希腊数学家欧几里得的名字命名。

什么是最大公约数？

GCD 是 最大公约数 的缩写。GCD 是能整除给定数字的最大数字。它也称为 GCF 或 HCF。其中，GCF 是 最大公因子 的缩写，HCF 是 最高公因子 的缩写。

如何找到两个正数的 GCD？

有三个重要的条件用于查找 GCD

1. If x = 0, then GCD(x, y) = y because GCD (0, y) = y.
2. If y = 0, then GCD(x, y) = x because GCD (x, 0) = x.
3. If x = y ? 0, then GCD(x, y) = (x = y * Q + R)      
Where, x is a dividend.
             y is a divisor.
             Q is a quotient. 
             R is a remainder.

让我们举例来说明这些条件。

示例 1：求 A = 0 和 B = 1023 的 GCD。

Given, 
             x = 0
             y = 1023

x is 0, so GCD(0, 1023) = 1023

示例 2：求 A = 120 和 B = 0 的 GCD。

Given, 
             x = 120
             y = 0

y is 0, so GCD(120, 0) = 120

示例 3：求 A = 30 和 B = 18 的 GCD。

Given,
             x = 30
             y = 18
             30 / 18 = 1 with remainder 12
             30 = 18 * 1 + 12
             GCD(30, 18) = GCD(18, 12)

Now, 
             x = 18
             y = 12
             18 / 12 = 1 with remainder 6
             18 = 12 * 1 + 6
             GCD(18, 12) = GCD(12, 6)
Now, 
             x = 12
             y = 6
             12 / 6 = 2 with remainder 0
             12 = 6 * 2 + 0
             GCD(12, 6) = GCD(6, 0)
Now,    
             x = 6
             y = 0
y is a zero, so GCD(6, 0) = 6

GCD(30, 18) = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) = 6
GCD(30, 18) = 6

示例 4：求 A = 270 和 B = 192 的 GCD。

Given, 
             x = 270
             y = 192
             270 / 192 = 1 with remainder 78
             270 = 192 * 1 + 78
             GCD(270, 192) = GCD(192, 78)
Now,
             x = 192
             y = 78
             192 / 78 = 2 with remainder 36
             192 = 78 * 2 + 36
             GCD(192, 78) = GCD(78, 36)
Now, 
              x = 78
              y = 36
              78 / 36 = 2 with remainder 6
              78 = 36 * 2 + 6
              GCD(78, 36) = GCD(36, 6)
Now, 
               x = 36
               y = 6
               36 / 6 = 6 with remainder 0
               36 = 6 * 6 + 0
               GCD(36, 6) = GCD(6, 0)
Now, 
               x = 6
               y = 0        
y is a zero, so GCD(6, 0) = 6

GCD(270, 192) = GCD(192, 78) = GCD(78, 36) = GCD(36, 6) = GCD(6, 0) = 6
GCD(270, 192) = 6

GCD 算法

GCD (x, y)
Step 1: if y = 0, return the value of x as the answer and exit, otherwise proceed to step 2.
Step 2: Divide x by y and assign the value of the remainder to r (i.e. r = x mod y).
Step 3: Replace x with y and y with r (i.e. x = y and y = r ? GCD(y, r)), and go to step 1. 

程序

#include <stdio.h>
 
int algorithm_gcd(int a, int b)
{
    if (b == 0) {
        return a;
    } else if (a >= b && b > 0) {
        return algorithm_gcd(b, (a % b));
    }
}
 
int main(void)
{
    int n1, n2, flag;
    printf("\nPlease enter the two positive numbers: ");
    scanf("%d%d", &n1, &n2);
    flag = algorithm_gcd(n1, n2); 
    if (flag)
        printf("\nThe GCD of %d and %d is %d\n", n1, n2, flag);
    else
        printf("\nInvalid input!!!\n");
    return 0;
}

输出

/tmp/884cRPPv22.o
Please enter the two positive numbers: 15
10

The GCD of 15 and 10 is 5

下一个主题Angular Material (MAT) Form-Field

← 上一个下一个 →

希腊欧几里得算法

什么是最大公约数？

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

博客

希腊欧几里得算法

什么是最大公约数？

相关帖子

天使数字 444

eMMC（嵌入式多媒体卡）

CMOS 制造

什么是网络间谍？

家庭计划方法及其优缺点

什么是进程间通信

世界上最长的河流是什么

反稀释证券和股份

什么是天花

什么是 Houdini

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器