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
▶▶ Python 파이썬] 최소공배수 구하기 함수; LCM
최대공약수 온라인 계산기: ▶▶ 최대공약수 계산기; GCD 구하기 Calculator
둘 이상의 정수들이 있고, 그 정수들을 어떤 숫자로 동시에 나누었을 때, 나머지가 없이 딱 나누어 떨어지는 숫자들이 몇 개 있을 것입니다. 그 숫자들 중에서 가장 큰 양수를 최대공약수라고 합니다. 분수의 약분에 사용됩니다.
예를 들어, 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
# -*- 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
<< Home