Example of algorithm for solving the greatest common divisor implemented in Python

This article mainly introduces the algorithm for solving the greatest common divisor implemented in Python, involving operating skills related to Python mathematical operations. Friends in need can refer to it

The example of this article describes the algorithm for solving the greatest common divisor implemented in Python . Share it with everyone for your reference, the details are as follows:

When using Python to find the greatest common divisor of two numbers, the decomposition of prime factors introduced earlier is used. In fact, when I wrote the prime factorization program, I discovered that this function was used in the process of solving the greatest common divisor.

What makes me happy is that the Python collection processing function I learned before actually comes in handy at this time. The completion of the small program makes people feel more comfortable.

The code is implemented as follows:

#!/usr/bin/python from collections import Counter def PrimeNum(num): r_value =[] for i inrange(2,num+1): for jin range(2,i): if i % j == 0: break else: r_value.append(i) return r_value def PrimeFactorSolve(num,prime_list): for n inprime_list: if num % n == 0: return [n,num / n] def Primepisor(num): num_temp =num prime_range= PrimeNum(num) ret_value =[] while numnot in prime_range: factor_list= PrimeFactorSolve(num,prime_range) ret_value.append(factor_list[0]) num =factor_list[1] else: ret_value.append(num) return Counter(ret_value) def Maxpisor(num1,num2): dict1 =Primepisor(num1) dict2 =Primepisor(num2) max_pisor= 1 for key1 indict1: if key1 in dict2: if dict1[key1] < dict2[key1]: max_pisor*= (key1 ** dict1[key1]) else: max_pisor*= (key1 ** dict2[key1]) return max_pisor print(Maxpisor(12,18)) print(Maxpisor(7,2)) print(Maxpisor(7,13)) print(Maxpisor(24,56)) print(Maxpisor(63,81))

The execution result of the program is as follows:

E:\WorkSpace\01 _Programming Language\03_Python\math>python max_pisor.py
6
1
1
8
9

passed the verification and the calculation result is accurate.

Related recommendations:

OpenCV cv.Mat and .txt file data reading and writing operations

The above is the detailed content of Example of algorithm for solving the greatest common divisor implemented in Python. For more information, please follow other related articles on the PHP Chinese website!