Code for Greatest Common Divisor in Python

python finding the greatest common divisor of two numbers program

Explanation:

Yes, HSK is right. In the 2nd loop:

while b:
    a = b
    b = a % b
print(a)

First a is changed to b and then what you do is b = b% b. But here:

a, b = b, a % b

it is executed as one-line so a is still a.

---

Solution:

So just add a third variable:

a = 1071
b = 462
while b:
    c = a
    a = b
    b = c % b
print(c)

One thing that distinguishes Python from other programming languages is that it is interpreted rather than compiled. This means that it is executed line by line.

greatest common divisor (python)

def ggt2(a, b):
    while b != 0:
        t = b
        b = a % b
        a = t
    return a if a != 0 else None

a = int(input("Enter a: "))
b = int(input("Enter b: "))
print("Their GCD is: "+str(ggt2(a,b)))

This code was converted to Python from the pseudocode on Wikipedia, with minor changes made.

There are some things wrong with your code. Here is your give pseudocode:

GCD :var X,Y,R: int;
input X,Y;
R:=1;
while R ≠ 0 do
R:=X mod Y; X:=Y; Y:=R;
od;
output X.

What this says is:

1. Start GCD
2. create variables X, Y, and R of type int each
3. Input a value to X and Y
4. Set R to 1
5. While R is not equal to 0 do:
6. (in loop of 5) set R to X % Y (the remainder of X and Y)
7. (in loop of 5) set X to Y
8. (in loop of 5) set Y to R
9. End of loop started on statement 5 iteration
10. Print out X

This pseudocode converted to Python would be:

def GCD():
    X = int(input("Enter X: "))
    Y = int(input("Enter Y: "))
    R = 1
    while R != 0:
        R = X % Y
        X = Y
        Y = R
    print(X)

GCD()

Try to figure out how this works, and tell me in the comments if it worked for you!

How to code for a Greatest Common Denominator function that only takes positive integers? (Python)

You can't combine multiple variables like that in a conditional expression. You need to compare each variable separately.

Also, you need to do that check before the other if statement. Otherwise, the function will return before you check for negative numbers.

def divisor(x,y):
    if x < 0 or y < 0:
        raise ValueError("This function only takes positive integers!")
    if (y==0):
        return x
    else:
        return divisor(y,x%y)

When you write (x or y) < 0, it calculates the value of x or y, then compares that to 0. x or y is the first truthy value of the two variables, and any non-zero value is truthy. So if x is not zero, then this is equivalent to x < 0, and if x is zero it's equivalent to y < 0. There's no automatic distribution of < over or.

Turn pseudocode into functioning code to find greatest common divisor

To find if a value evenly divides another, you need to have the smaller (divisor) on the right side of the modulus operator. So change your code to:

if (m %d != 0) or (n % d != 0):

This evaluates if d evenly divides mor n, instead of if m or n evenly divide d.

python: Greatest common divisor (gcd) for floats, preferably in numpy

Seems like you could just modify the code of fractions.gcd to include the tolerances:

def float_gcd(a, b, rtol = 1e-05, atol = 1e-08):
    t = min(abs(a), abs(b))
    while abs(b) > rtol * t + atol:
        a, b = b, a % b
    return a

---

Related Topics