컴퓨터 엑셀 워드 포토샵 구글어스 WINDOWS JAVASCRIPT JAVA C++

 
Friday, March 16, 2007

Python 파이썬] 최대 공약수 구하기 함수; gcd, Greatest Common Divisor Function


두 정수의 최대공약수(gcd; Greatest Common Divisor)를 구하는 파이썬 소스입니다.

둘 이상의 정수들이 있고, 그 정수들을 어떤 숫자로 동시에 나누었을 때, 나머지가 없이 딱 나누어 떨어지는 숫자들이 몇 개 있을 것입니다. 그 숫자들 중에서 가장 큰 양수를 최대공약수라고 합니다. 분수의 약분에 사용됩니다.

예를 들어, 12와 18의 최대 공약수는 6인데,
6으로 12와 18을 나누면 나머지가 없이 딱 떨어집니다.

6은 {1, 2, 3, 6} 으로 나누어 떨어지고
18은 {1, 2, 3, 6, 9, 18} 로 나누어 떨어지지만

공통되는 약수 즉 공약수 중에서 가장 큰 숫자는 6입니다.


최대공약수 계산 예제
스크립트 파일명: example.py
#!/usr/bin/python
# -*- coding: cp949 -*-

# 최대 공약수 구하기 함수
# (Euclidean Algorithm; Euclid's Algorithm)
def gcd(a, b):
  while (b != 0):
    temp = a % b
    a = b
    b = temp
  return abs(a)



##############################
# 이제 테스트를 해보겠습니다.

print gcd(12, 18)
# 6

print gcd(5154, 3435)
# 3

print gcd(0, 0)
# 0
# 이 경우는 0으로 정의되어 있음

print gcd(1, 0)
# 1
# 이것도 맞습니다.

print gcd(0, 12)
# 12
# 이것도 맞습니다.

print gcd(13, 12)
# 1
# 공약수가 1밖에 없는 '서로소(Relatively Prime; Coprime)'입니다.

print gcd(-42, -56)
# 14
# 최대공약수는 항상 양수임

# 세 가지 수의 최대공약수 구하기
print gcd(gcd(42, 12), 48)
# 6



▶▶ Python 파이썬] 최소공배수 구하기 함수; LCM


최대공약수 온라인 계산기: ▶▶ 최대공약수 계산기; GCD 구하기 Calculator




tag: python
Python | 파이썬
tag: study
학습 | Study

0 Comments:

Post a Comment

<< Home RSS 2.0 feed

구글 Google 에서 제공하는 무료 블로그 서비스인 블로거 Blogger 의 인터넷 주소는 www.blogger.com 입니다. Blogger 에 블로그를 만들면, blogspot.com 이라는 주소에 블로그가 생성됩니다.
블로그를 직접 방문하지 않고도 최신 게시물을 구독하려면 RSS 2.0 feed 주소를 리더기에 등록하시면 됩니다.
Previous Posts
Monthly Archives
Top