求最小公约数

yobdc

x = int(input('请输入一个整数:'))
y = int(input('请输入一个整数:'))
c = 0
if x>y:
    big = x
    small = y
elif x<y:
    small = x
    big = y
else:
    small = x
    big  =y
   
    c+=1
   
a = big % small
while a != 0 and c!=0:
    small = big = a
    a = big % small
print('最大公约数为:'+ str(small))

傻眼貓咪

最大公因數/最大公約數 Highest Common Factor/Greatest Common Divisor (gcd)
範例：
54 的正因數為：1, 2, 3, 6, 9, 18, 27, 54
24 的正因數為：1, 2, 3, 4, 6, 8, 12, 24
54 和 24 的共同公因數：1, 2, 3, 6
54 和 24 的最大公因數為：6

代碼：（沒有任何導入模塊）

1. # 最大公因數/大公約數
   
2. # Highest Common Factor/Greatest Common Divisor (gcd)
   
3. 
   
4. def factor(num: int) -> int:
   
5.     for n in range(1, num+1):
   
6.         if not (num%n):
   
7.             yield n
   
8. 
   
9. a = int(input("輸入一個整數 a："))
   
10. b = int(input("輸入一個整數 b："))
    
11. 
    
12. gcd = max(set(factor(a))&set(factor(b)))
    
13. print(f"{a} 和 {b} 最大公約數：{gcd}")

复制代码

最小公倍數 Least Common Multiple (lcm)
範例：
18 的倍數為：18, 36, 54, 72, 90, 108, 126, 144...
12 的倍數為：12, 24, 36, 48, 60, 72, 84, 96, 108, 120, 132...
18 和 12 的最小公倍數：36

代碼：（沒有任何導入模塊）

1. # 最小公倍數
   
2. # Least Common Multiple (lcm)
   
3. 
   
4. a = int(input("輸入一個整數 a："))
   
5. b = int(input("輸入一個整數 b："))
   
6. 
   
7. x, y = max(a, b), min(a, b)
   
8. 
   
9. while True:
   
10.     if x == y:
    
11.         print(f"{a} 和 {b} 最小公倍數：{x}")
    
12.         break
    
13.     while y < x:
    
14.         y += min(a, b)
    
15.     while x < y:
    
16.         x += max(a, b)

复制代码

---

代碼：導入模塊（math）

1. import math
   
2. 
   
3. a = int(input("輸入一個整數 a："))
   
4. b = int(input("輸入一個整數 b："))
   
5. 
   
6. print(f"{a} 和 {b} 最大公約數：{math.gcd(a, b)}")
   
7. print(f"{a} 和 {b} 最小公倍數：{math.lcm(a, b)}")

复制代码

niuniuniu666

1. >>> def gcd(x,y):
   
2.     while y:
   
3.         z = x%y
   
4.         x = y
   
5.         y = z
   
6.     return(x)
   
7. 
   
8. >>> gcd(22,33)
   
9. 11

复制代码