파이썬의 최대공약수 코드

파이썬의 최대공약수 코드

닫힘.이 질문은 더 필요합니다.집중적인현재 답변을 수락하고 있지 않습니다.

---

이 질문을 개선하고 싶으십니까?이 게시물을 편집하여 하나의 문제에만 초점을 맞추도록 질문을 업데이트합니다.

3년 전에 문을 닫았습니다.

이 질문을 개선합니다.

a와 b의 최대 공약수(GCD)는 나머지 없이 둘을 나누는 가장 큰 숫자입니다.

두 숫자의 GCD를 찾는 한 가지 방법은 유클리드 알고리즘인데, 이 알고리즘은 다음과 같은 관측에 기초합니다.r다음과 같은 경우의 나머지입니다.a로 나눕니다.b,그리고나서gcd(a, b) = gcd(b, r)베이스 케이스로서, 우리는gcd(a, 0) = a.

매개 변수를 사용하는 gcd라는 함수를 작성합니다.a그리고.b그리고 그들의 최대 공약수를 반환합니다.

표준 도서관에 있습니다.

>>> from fractions import gcd
>>> gcd(20,8)
4

의 소스 코드inspectPython 2.7의 모듈:

>>> print inspect.getsource(gcd)
def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a

파이썬 3.5 기준,gcd 모듈에 있습니다. 모듈에 있는 것입니다.fractions사용되지 않습니다.게다가.inspect.getsource두 메서드 모두에 대한 설명 소스 코드를 더 이상 반환하지 않습니다.

m-n을 사용하는 알고리즘은 매우 오래 실행될 수 있습니다.

이것이 훨씬 더 나은 성능을 발휘합니다.

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x

이 버전의 코드는 GCD를 찾기 위해 유클리드 알고리즘을 사용합니다.

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

gcd = lambda m,n: m if not n else gcd(n,m%n)

재귀를 사용하여,

def gcd(a,b):
    return a if not b else gcd(b, a%b)

사용하는 동안,

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

람다 사용,

gcd = lambda a,b : a if not b else gcd(b, a%b)

>>> gcd(10,20)
>>> 10

def gcd(m,n):
    return gcd(abs(m-n), min(m, n)) if (m-n) else n

재귀를 사용하는 매우 간결한 솔루션:

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

a=int(raw_input('1st no \n'))
b=int(raw_input('2nd no \n'))

def gcd(m,n):
    z=abs(m-n)
    if (m-n)==0:
        return n
    else:
        return gcd(z,min(m,n))


print gcd(a,b)

유클리드 알고리즘에 기반한 다른 접근법.

def gcdRecur(a, b):
    '''
    a, b: positive integers

    returns: a positive integer, the greatest common divisor of a & b.
    '''
    # Base case is when b = 0
    if b == 0:
        return a

    # Recursive case
    return gcdRecur(b, a % b)

저는 재귀를 사용하는 또 다른 방법이 있다고 생각합니다.내 코드는 다음과 같습니다.

def gcd(a, b):
    if a > b:
        c = a - b
        gcd(b, c)
    elif a < b:
        c = b - a
        gcd(a, c)
    else:
        return a

재귀가 있는 파이썬:

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

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

위해서a>b:

def gcd(a, b):

    if(a<b):
        a,b=b,a
        
    while(b!=0):
        r,b=b,a%r
        a=r
    return a

---

어느 쪽이든a>b또는a<b:

def gcd(a, b):

    t = min(a, b)

    # Keep looping until t divides both a & b evenly
    while a % t != 0 or b % t != 0:
        t -= 1

    return t

저는 위드 루프를 이용한 숙제를 위해 이런 일을 해야 했습니다.가장 효율적인 방법은 아니지만 기능을 사용하지 않으려는 경우 다음과 같이 작동합니다.

num1 = 20
num1_list = []
num2 = 40
num2_list = []
x = 1
y = 1
while x <= num1:
    if num1 % x == 0:
        num1_list.append(x)
    x += 1
while y <= num2:
    if num2 % y == 0:
        num2_list.append(y)
    y += 1
xy = list(set(num1_list).intersection(num2_list))
print(xy[-1])

def _grateest_common_devisor_euclid(p, q):
    if q==0 :
        return p
    else:
        reminder = p%q
        return _grateest_common_devisor_euclid(q, reminder)

print(_grateest_common_devisor_euclid(8,3))

이 코드는 # 사용자가 제공한 선택에 따라 두 개 이상의 숫자의 gcd를 계산합니다. 여기서 사용자는 숫자를 제공합니다.

numbers = [];
count = input ("HOW MANY NUMBERS YOU WANT TO CALCULATE GCD?\n")
for i in range(0, count):
  number = input("ENTER THE NUMBER : \n")
  numbers.append(number)
numbers_sorted = sorted(numbers)
print  'NUMBERS SORTED IN INCREASING ORDER\n',numbers_sorted
gcd = numbers_sorted[0]

for i in range(1, count):
  divisor = gcd
  dividend = numbers_sorted[i]
  remainder = dividend % divisor
  if remainder == 0 :
  gcd = divisor
  else :
    while not remainder == 0 :
      dividend_one = divisor
      divisor_one = remainder
      remainder = dividend_one % divisor_one
      gcd = divisor_one

print 'GCD OF ' ,count,'NUMBERS IS \n', gcd

저는 가치 스와핑이 잘 되지 않았습니다.그래서 저는 단지 < b 또는 a > b에 입력된 숫자에 대해 거울과 같은 상황을 설정했습니다.

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

print gcd(18, 2)

#This program will find the hcf of a given list of numbers.

A = [65, 20, 100, 85, 125]     #creates and initializes the list of numbers

def greatest_common_divisor(_A):
  iterator = 1
  factor = 1
  a_length = len(_A)
  smallest = 99999

#get the smallest number
for number in _A: #iterate through array
  if number < smallest: #if current not the smallest number
    smallest = number #set to highest

while iterator <= smallest: #iterate from 1 ... smallest number
for index in range(0, a_length): #loop through array
  if _A[index] % iterator != 0: #if the element is not equally divisible by 0
    break #stop and go to next element
  if index == (a_length - 1): #if we reach the last element of array
    factor = iterator #it means that all of them are divisibe by 0
iterator += 1 #let's increment to check if array divisible by next iterator
#print the factor
print factor

print "The highest common factor of: ",
for element in A:
  print element,
print " is: ",

greatest_common_devisor(A)

def gcdIter(a, b):
gcd= min (a,b)
for i in range(0,min(a,b)):
    if (a%gcd==0 and b%gcd==0):
        return gcd
        break
    gcd-=1

다음은 다음과 같은 개념을 구현하는 솔루션입니다.Iteration:

def gcdIter(a, b):
    '''
    a, b: positive integers

    returns: a positive integer, the greatest common divisor of a & b.
    '''
    if a > b:
        result = b
    result = a

    if result == 1:
        return 1

    while result > 0:
        if a % result == 0 and b % result == 0:
            return result
        result -= 1

언급URL : https://stackoverflow.com/questions/11175131/code-for-greatest-common-divisor-in-python