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

 
Previous Post MS 워드] 줄번호, 행번호 넣기 (행마다 줄 번호, 행 번호); MS-Word Line ...C언어 사칙연산, 덧셈, 뺄셈, 곱셈, 나눗셈; Multiply DivideVBA 곱하기 나누기 방법, 곱셈 나눗셈 기호 [엑셀 Excel 비베울트라에디트, 많은 파일들 속에서 문자, 문자열 찾기; UltraEdit Find Stri...현재 시간으로 된 파일명 만들기 BAT 배치 파일; Time To File Name일본어 후리가나 자동 변환 사이트, 한자어 읽기 발음 히라가나 붙이기; Furigana, ...오늘 날짜로 된 디렉토리명, 폴더명 만들기 BAT 배치 파일; Date To Directo...리눅스 history 지우기 명령, Linux 히스토리 파일 위치, 삭제 Clear 방법Java 자바] 디렉토리 생성, 중첩 패스의 폴더 만들기 함수; mkdir, mkdirs,...매스매티카, 환경 설정 파일 저장, 폴더 위치; Mathematica Config Setu...

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

Friday, March 16, 2007

두 정수의 최대공약수(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



0 Comments:

Post a Comment

<< Home RSS 2.0 feed

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