Skip to content

Instantly share code, notes, and snippets.

@CCCougar

CCCougar/getGCD.py

Last active November 30, 2021 13:00
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save CCCougar/f219d56c0455aeb1539ba2f96c9d3e0c to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save CCCougar/f219d56c0455aeb1539ba2f96c9d3e0c to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. CCCougar revised this gist Nov 30, 2021. 1 changed file with 19 additions and 0 deletions.
    19 changes: 19 additions & 0 deletions getGCD.py
    View file
    Original file line number Diff line number Diff line change
    @@ -9,8 +9,27 @@ def getGCD(num_1, num_2):
    return num_2
    num_1 = num_2
    num_2 = remainder

    def EEA(r0, r1):
    # Extended Euclidean algorithm
    S = [1, 0]
    T = [0, 1]
    R = [r0, r1]
    i = 1
    while True:
    i += 1
    R.append(R[i - 2] % R[i - 1])
    q = (R[i-2]-R[i])/R[i-1]
    S.append(S[i-2]-q*S[i-1])
    T.append(T[i-2]-q*T[i-1])
    if R[i - 2] % R[i - 1] == 0:
    break
    print("gcd(", r0, ", ", r1, ") = (",
    int(S[i-1]), ") * ", r0, " + (", int(T[i-1]), ") * ", r1)
    return S[i-1], T[i-1]


    print(getGCD(2, 3))
    print(getGCD(27, 21))
    print(getGCD(973, 301))
    a, b = EEA(973, 301)
  2. CCCougar renamed this gist Nov 30, 2021. 1 changed file with 0 additions and 0 deletions.
    0 gistfile1.txt → getGCD.py
    View file
    File renamed without changes.
  3. CCCougar created this gist Nov 30, 2021.
    16 changes: 16 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,16 @@
    def getGCD(num_1, num_2):
    if num_2 > num_1:
    tmp = num_1
    num_1 = num_2
    num_2 = tmp
    while True:
    remainder = num_1 % num_2
    if remainder == 0:
    return num_2
    num_1 = num_2
    num_2 = remainder


    print(getGCD(2, 3))
    print(getGCD(27, 21))
    print(getGCD(973, 301))