How to find the greatest common divisor in Python

This time I will bring you PythonHow to find the greatest common divisor, what are the precautions for finding the greatest common divisor in Python, the following is a practical case, let’s take a look .

I have summarized the solution of the greatest common divisor in Knuth TAOCP before. In fact, the algorithm modification required in the after-school questions is to solve the greatest common divisor by the euclidean division method.

My initial understanding of this question was wrong, and naturally I didn’t have a standard answer. Now write the corresponding code implementation according to the standard answer:

# -*- coding:utf-8 -*-
#! python2
def MaxCommpisor(m,n):
  while m * n != 0:
    m = m % n
    if m == 0:
      return n
    else:
      n = n % m
      if n == 0:
        return m
print(MaxCommpisor(55,120))

The execution result of the program:

Exchange the positions of the two numbers, the code is as follows :

# -*- coding:utf-8 -*-
#! python2
def MaxCommpisor(m,n):
  while m * n != 0:
    m = m % n
    if m == 0:
      return n
    else:
      n = n % m
      if n == 0:
        return m
print(MaxCommpisor(120,55))

Execution results of the program:

The question prompt mentioned that it will reduce efficiency. Judging from the above code, the loss of efficiency should be Division and judgment. Here, take the code of the previous algorithm and compare it:

def CommDevisor(m,n):
  r = m % n
  while r != 0:
    m = n
    n = r
    r = m % n
  return n
print(CommDevisor(120,25))

Running results:

loop, There is one more division and comparison operation. In fact, the comparison efficiency is still good, but the division operation will lead to a reduction in efficiency.

How Python Numpy operates arrays and matrices

How to operate Python to traverse numpy arrays

The above is the detailed content of How to find the greatest common divisor in Python. For more information, please follow other related articles on the PHP Chinese website!