求最大公约数-scratch真题2212四级

约数的基本性质：

1. ‌有限性‌：一个整数的约数个数是有限的 。
2. ‌最小与最大‌：任意正整数的最小约数是 ‌1‌，最大约数是 ‌它本身‌ 。
3. ‌正约数为主‌：在小学和中学阶段，通常讨论的“约数”默认指‌正约数‌ 。
4. ‌质数与合数‌：
• 质数（素数）只有两个正约数：1 和它本身，如 3、5、7。
• 合数有三个或更多正约数，如 4（1、2、4）、6（1、2、3、6）。

1. 二、公约数
2. 公约数（公因数），一个能被若干个整数同时整除的的整数，也就是几个数都共有的约数。公约数中最大的称为最大公约数
3. 例如：
   求12和18的公约数：
4. 1.先写出各自的约数
5.      12的约数：1、2、3、4、6、12
6.      18的约数：1、2、3、6、9、18
7. 2.找出都出现的数
8.     -->1、2、3、6
9. 所以：12和18的公约数是：1、2、3、6

1. 三、计算最大公约数的方法 

2. 辗转相除法（欧几里得算法）

   · 欧几里得算法，也称为辗转相除法，是一种用于计算两个正整数最大公约数（GCD）的高效算法。其核心原理基于这样一个数学事实：两个整数的最大公约数等于其中较小的数与两数相除余数的最大公约数。用数学表达式表示就是：
3. gcd(a,b)=gcd(b,amodb)

   其中 a 和 b 是两个正整数，且 a>b。

算法原理

该算法的原理可以这样理解：设 a=bq+r（其中q是商，r是余数），那么a和b的最大公约数就等于b和r的最大公约数。这是因为a和b的任何公约数也一定是b和r 的公约数，反之亦然。

算法步骤

1. ‌初始化‌：给定两个正整数 a 和 b（假设 a>b）。如果b>a，则需要交换值。
2. ‌计算余数‌：计算 a 除以 b 的余数 r。
3. ‌判断余数‌：
• 如果 r=0，则 b 就是 a 和 b 的最大公约数。 
• 如果 r≠0，则将 b 的值赋给 a，将 r 的值赋给 b，然后回到步骤 2。
4. ‌重复‌：重复步骤 2 和 3，直到余数 r 为 0。此时，最后一个非零的除数就是最大公约数。

举例说明

1.例如：如果 r=0

12÷6=2......0，则 6就是 12 和 6 的最大公约数。 

2.例如，如果 r≠0

计算 gcd⁡(48,18) 的过程如下：

1. 48÷18=2
    余 12，所以 gcd⁡(48,18)=gcd⁡(18,12)。
2. 18÷12=1
    余 6，所以 gcd⁡(18,12)=gcd⁡(12,6)。
3. 12÷6=2
   余 0，所以 gcd⁡(12,6)=6。因此，gcd⁡(48,18)=6。