Hướng dẫn euclidean algorithm code python

Question

I'm trying to write the Euclidean Algorithm in Python. It's to find the GCD of two really large numbers. The formula is a = bq + r where a and b are your two numbers, q is the number of times b divides a evenly, and r is the remainder.

I can write the code to find that, however if it the original numbers don't produce a remainder (r) of zero then the algorithm goes to step 2 => b = rx + y. (same as the first step but simply subbing b for a, and r for b) the two steps repeat until r divides both a and b evenly.

This is my code, I haven't yet figured out how to do the subbing of values and create a loop until the GCD is found.

a = int(input("What's the first number? "))
b = int(input("What's the second number? ")) 
r = int(a - (b)*int(a/b))

if r == 0:
  print("The GCD of the two choosen numbers is " + str(b))

elif r != 0:
  return b and r
  (b == a) and (r == b)

print("The GCD of the two numbers is " + str(r))

Chris Martin

29.6k8 gold badges74 silver badges131 bronze badges

asked Feb 6, 2014 at 16:32

2

a = int(input("What's the first number? "))
b = int(input("What's the second number? ")) 
r=a%b
while r:
    a=b
    b=r
    r=a%b
print('GCD is:', b)

or use break in loop:

a = int(input("What's the first number? "))
b = int(input("What's the second number? ")) 
while 1:
    r=a%b
    if not r:
        break
    a=b
    b=r
print('GCD is:', b)

answered Feb 6, 2014 at 16:43

zhangxaochenzhangxaochen

31.2k15 gold badges71 silver badges105 bronze badges

Try This

a = int(input("Enter No.1"))

b = int(input("Enter No.2"))

r = a%b

q = int(a/b)

while(r!=0):

    a = b

    b = r

    q = int(a/b)

    r = a - (b * q)


print(b)

answered Oct 23, 2018 at 13:50

I know this is old post but here it is:

def GCD(x , y):
    """This is used to calculate the GCD of the given two numbers.
    You remember the farm land problem where we need to find the 
    largest , equal size , square plots of a given plot?"""
    if y == 0:
        return x
    r = int(x % y)
    return GCD(y , r)

Taken from Algorithms 4th edition.

Note: if your numbers are REALLY REALLY large then try to increase the recursion limit by:

import sys
sys.seterecursionlimit("your new limit")

but be very very careful with it. I was able to fill my 12GB RAM and cause a freeze quite easily.

answered May 15, 2021 at 22:27

I think that's the shortest solution:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

answered Sep 29, 2021 at 18:44

I think there's one missing important condition for Euclidean Algorithm to work, which is a >= b > 0. So may I suggest this code I just made (quite long cuz I haven't viewed prev answers before building it haha.

def gcd(int1: int, int2: int):
# I used a recursive algorithm
# Condition: a>=b>0
if int1 < int2:
    a = int2
    b = int1
else:
    a = int1
    b = int2

if a % b == 0:
    return b
else:
    r = a % b
    gcd(b, r)
    return r

answered Jan 13 at 13:10

I recently came across a question like this in my math class. The code I wrote was:

def EuclideanAlg(a,b):
    # switches the value of a and b if a is less than b
    if a <= b - 1:
        temp = a
        a = b
        b = temp
    # takes the remainder after a is divided by b
    r = a % b
    # iterates infinitely
    while True:
        # if a is divisible by b, b is the gcd of a,b
        if r == 0:
            return b
            break
        # a becomes the current value of b and b becomes the current value of r
        else:
            temp = r
            r = b % r
            b = temp

answered Aug 20 at 2:59

Not the answer you're looking for? Browse other questions tagged python or ask your own question.

View Discussion

Improve Article

Save Article

Read

Discuss

View Discussion

Improve Article

Save Article

Python3

def gcd(a, b):

if a == 0 :

return b

return gcd(b%a, a)

a = 10

b = 15

print("gcd(", a , "," , b, ") = ", gcd(a, b))

a = 35

b = 10

print("gcd(", a , "," , b, ") = ", gcd(a, b))

a = 31

b = 2

print("gcd(", a , "," , b, ") = ", gcd(a, b))

Output:

GCD(10, 15) = 5
GCD(35, 10) = 5
GCD(31, 2) = 1

Time Complexity: O(Log min(a, b))

Auxiliary Space: O(Log min(a, b)), due to recursion stack.

Please refer complete article on Basic and Extended Euclidean algorithms for more details!

programming python Denomination Python program

Hướng dẫn euclidean algorithm code python

Not the answer you're looking for? Browse other questions tagged python or ask your own question.

Python3

Bài Viết Liên Quan

Hướng dẫn form đăng ký php

Hướng dẫn dùng np astype python

Hướng dẫn php extension php_zip enabled

How do you delete a character in python?

How to add number to list python

Hướng dẫn dùng mail 1 trong PHP

Hướng dẫn dùng gaussian distribution python

Giá vé máy bay re tháng 7 2023

Hướng dẫn php _get _request parameters

Hướng dẫn dùng mysql last_insert_id trong PHP

MỚI CẬP NHẬP

Caâu lạc bộ thiện nguyện tiếng anh là gì năm 2024

File exel bị lỗi không đủ bộ nhớ năm 2024

Đề thi đại học môn toán khối b năm 2004 năm 2024

Bài tập chuyên đề vật lý hạt nhân năm 2024

Là viên chức làm gì để phát triển cơ quan năm 2024

Bệnh u nang buồng trứng tiếng anh là gì năm 2024

Đề kiểm tra 15 phút hóa 9 học kì 1 năm 2024

Soạn bài buổi học cuối cùng ngữ văn lớp 6 năm 2024

Cm trong xây dựng tiếng anh là gì năm 2024

Bài tập trắc nghiệm về tính từ sở hữu năm 2024

Xem Nhiều

On the weekend là thì gì năm 2024

Co số điện thoại di động nào 9 đó năm 2024

Himax premium lub ts40 là gì năm 2024

81 2 nguyễn văn giai quận 1 f dakao năm 2024

Cách mạng công nghiệp 4.0 cơ hội nào cho startup năm 2024

Các dạng toán chương 1 kinh tế vĩ mô năm 2024

Cấu trúc tiếng anh là con nghiện của cái gì năm 2024

Hoạt động văn hóa văn nghệ là một năm 2024

Khắc phục lỗi phần mềm fot làm bị out game năm 2024

Top phim xuyen khong hay nhat trung quoc năm 2024

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội