Как найти нод списка чисел python

Как найти НОК или НОД в python 3.9 в списке из n кол-ва чисел? (Ввод чисел пользователем)
(н: math.gcd([1 , 2 , 3])

задан 26 окт 2021 в 16:22

So I’m writing a program in Python to get the GCD of any amount of numbers.

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]


    # i'm stuck here, this is wrong
    for i in range(len(numbers)-1):
        print GCD([numbers[i+1], numbers[i] % numbers[i+1]])


print GCD(30, 40, 36)

The function takes a list of numbers.
This should print 2. However, I don’t understand how to use the the algorithm recursively so it can handle multiple numbers. Can someone explain?

updated, still not working:

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]

    gcd = 0

    for i in range(len(numbers)):
        gcd = GCD([numbers[i+1], numbers[i] % numbers[i+1]])
        gcdtemp = GCD([gcd, numbers[i+2]])
        gcd = gcdtemp

    return gcd

Ok, solved it

def GCD(a, b):

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

and then use reduce, like

reduce(GCD, (30, 40, 36))

asked May 18, 2013 at 19:19

Since GCD is associative, GCD(a,b,c,d) is the same as GCD(GCD(GCD(a,b),c),d). In this case, Python’s reduce function would be a good candidate for reducing the cases for which len(numbers) > 2 to a simple 2-number comparison. The code would look something like this:

if len(numbers) > 2:
    return reduce(lambda x,y: GCD([x,y]), numbers)

Reduce applies the given function to each element in the list, so that something like

gcd = reduce(lambda x,y:GCD([x,y]),[a,b,c,d])

is the same as doing

gcd = GCD(a,b)
gcd = GCD(gcd,c)
gcd = GCD(gcd,d)

Now the only thing left is to code for when len(numbers) <= 2. Passing only two arguments to GCD in reduce ensures that your function recurses at most once (since len(numbers) > 2 only in the original call), which has the additional benefit of never overflowing the stack.

answered May 18, 2013 at 19:53

Python 3.9 introduced multiple arguments version of math.gcd, so you can use:

import math
math.gcd(30, 40, 36)

3.5 <= Python <= 3.8.x:

import functools
import math
functools.reduce(math.gcd, (30, 40, 36))

3 <= Python < 3.5:

import fractions
import functools
functools.reduce(fractions.gcd, (30, 40, 36))

answered May 13, 2020 at 16:08

A solution to finding out the LCM of more than two numbers in PYTHON is as follow:

#finding LCM (Least Common Multiple) of a series of numbers

def GCD(a, b):
    #Gives greatest common divisor using Euclid's Algorithm.
    while b:      
        a, b = b, a % b
    return a

def LCM(a, b):
    #gives lowest common multiple of two numbers
    return a * b // GCD(a, b)

def LCMM(*args):
    #gives LCM of a list of numbers passed as argument 
    return reduce(LCM, args)

Here I’ve added +1 in the last argument of range() function because the function itself starts from zero (0) to n-1. Click the hyperlink to know more about range() function :

print ("LCM of numbers (1 to 5) : " + str(LCMM(*range(1, 5+1))))
print ("LCM of numbers (1 to 10) : " + str(LCMM(*range(1, 10+1))))
print (reduce(LCMM,(1,2,3,4,5)))

those who are new to python can read more about reduce() function by the given link.

answered May 28, 2015 at 6:22

Try calling the GCD() as follows,

i = 0
temp = numbers[i]
for i in range(len(numbers)-1):
        temp = GCD(numbers[i+1], temp)

answered May 18, 2013 at 19:28

My way of solving it in Python. Hope it helps.

def find_gcd(arr):
    if len(arr) <= 1:
        return arr
    else:
        for i in range(len(arr)-1):
            a = arr[i]
            b = arr[i+1]
            while b:
                a, b = b, a%b
            arr[i+1] = a
        return a
def main(array):
    print(find_gcd(array))

main(array=[8, 18, 22, 24]) # 2
main(array=[8, 24]) # 8
main(array=[5]) # [5]
main(array=[]) # []

Some dynamics how I understand it:

ex.[8, 18] -> [18, 8] -> [8, 2] -> [2, 0]

18 = 8x + 2 = (2y)x + 2 = 2z where z = xy + 1

ex.[18, 22] -> [22, 18] -> [18, 4] -> [4, 2] -> [2, 0]

22 = 18w + 4 = (4x+2)w + 4 = ((2y)x + 2)w + 2 = 2z

answered Jul 24, 2018 at 2:06

As of python 3.9 beta 4, it has got built-in support for finding gcd over a list of numbers.

Python 3.9.0b4 (v3.9.0b4:69dec9c8d2, Jul  2 2020, 18:41:53)
[Clang 6.0 (clang-600.0.57)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import math
>>> A = [30, 40, 36]
>>> print(math.gcd(*A))
2

answered Aug 5, 2020 at 2:24

One of the issues is that many of the calculations only work with numbers greater than 1. I modified the solution found here so that it accepts numbers smaller than 1. Basically, we can re scale the array using the minimum value and then use that to calculate the GCD of numbers smaller than 1.

# GCD of more than two (or array) numbers - alows folating point numbers
# Function implements the Euclidian algorithm to find H.C.F. of two number 
def find_gcd(x, y): 
    while(y): 
        x, y = y, x % y 
    return x 
          
# Driver Code         
l_org = [60e-6, 20e-6, 30e-6]
min_val = min(l_org)
l = [item/min_val for item in l_org]
  
num1 = l[0] 
num2 = l[1] 
gcd = find_gcd(num1, num2) 
  
for i in range(2, len(l)): 
    gcd = find_gcd(gcd, l[i]) 
      
gcd = gcd * min_val
print(gcd) 

answered Aug 10, 2020 at 19:04

HERE IS A SIMPLE METHOD TO FIND GCD OF 2 NUMBERS

a = int(input("Enter the value of first number:"))
b = int(input("Enter the value of second number:"))
c,d = a,b
while a!=0:
    b,a=a,b%a
print("GCD of ",c,"and",d,"is",b)

answered Oct 24, 2020 at 5:35

As You said you need a program who would take any amount of numbers
and print those numbers’ HCF.

In this code you give numbers separated with space and click enter to get GCD

num =list(map(int,input().split()))  #TAKES INPUT
def print_factors(x):          #MAKES LIST OF LISTS OF COMMON FACTROS OF INPUT
    list = [ i for i in range(1, x + 1) if x % i == 0 ]
    return list

p = [print_factors(numbers) for numbers in num]
result = set(p[0])        
for s in p[1:]:             #MAKES THE SET OF COMMON VALUES IN LIST OF LISTS
    result.intersection_update(s)

for values in result:
    values = values*values     #MULTIPLY ALL COMMON FACTORS TO FIND GCD
    values = values//(list(result)[-1])  
print('HCF',values)

Hope it helped

answered Nov 11, 2022 at 14:03