Python :: 유클리드 알고리즘 #GCD(최대공약수) 구하기

암호수학 수업

[유클리드 알고리즘 #GCD(최대공약수) 구하기]

GCD(Greatest common divisor) 구하기

소스코드

r=[]
s=[1,0]
t=[0,1]
q=[]
 
arg1=int(input("Arg1 : "))
arg2=int(input("Arg2 : "))
r.append(arg1)
r.append(arg2)
 
print(r)
while True:
   q.append(int(r[0]/r[1]))
   r.append(r[0]%r[1])
   s.append(s[0]-s[1]*q[0])
   t.append(t[0]-t[1]*q[0])
   print(r[0],"=",r[1],"x",q[0],"+",r[2],"---> s :",s[0],", t :",t[0])
   if r[2]==0:
      break
   del s[0]
   del t[0]
   del r[0]
   del q[0]
 
 
print("GCD =",r[1],"=",s[1],"*",arg1,"+",t[1],"*",arg2)

실행결과

================= RESTART: C:\Users\samsung\Desktop\암호수학.py =================
Arg1 : 252
Arg2 : 198
[252, 198]
252 = 198 x 1 + 54 ---> s : 1 , t : 0
198 = 54 x 3 + 36 ---> s : 0 , t : 1
54 = 36 x 1 + 18 ---> s : 1 , t : -1
36 = 18 x 2 + 0 ---> s : -3 , t : 4
GCD = 18 = 4 * 252 + -5 * 198
>>> 
================= RESTART: C:\Users\samsung\Desktop\암호수학.py =================
Arg1 : 9274
Arg2 : 4853
[9274, 4853]
9274 = 4853 x 1 + 4421 ---> s : 1 , t : 0
4853 = 4421 x 1 + 432 ---> s : 0 , t : 1
4421 = 432 x 10 + 101 ---> s : 1 , t : -1
432 = 101 x 4 + 28 ---> s : -1 , t : 2
101 = 28 x 3 + 17 ---> s : 11 , t : -21
28 = 17 x 1 + 11 ---> s : -45 , t : 86
17 = 11 x 1 + 6 ---> s : 146 , t : -279
11 = 6 x 1 + 5 ---> s : -191 , t : 365
6 = 5 x 1 + 1 ---> s : 337 , t : -644
5 = 1 x 5 + 0 ---> s : -528 , t : 1009
GCD = 1 = 865 * 9274 + -1653 * 4853
>>>