티스토리 뷰
유클리드 호제법을 이용한 최소공배수(GCD)구하기
유클리드 원론에 기술되어있으며, 서로간의 값을 나눈다 하여 붙여진 호제법, 최대공약수(GCD : Greatest common divisor) 를 구하기 위한 인류 최초의 알고리즘이라 불리운다.
두 양의 정수 a,b(b>a)에 대하여 b=aq+r,(0≤r<a)라 하면, a,b a,b의 최대공약수는 a,r a,r의 최대공약수와 같다. 즉, gcd(a,b)=gcd(a,r).
소인수 분해를 이용한 방법도 있지만 유클리드 호제법을 이용하면 훨씬 빠르게 구할 수 있다.
소인수 분해를 이용한 최대공약수 구하기
2 | 1000, 300
2 | 500, 150
5 | 250, 75
5 | 50, 15
10, 3
5^2 x 2^2 = 25 x 4 = 100
유클리드 호제법을 이용한 최대공약수 구하기
1000 = 300 x 10 + 100
300 = 100 x 3
유클리드 호제법 계산량이 더 간결하다는 것을 확인 해 볼 수 있다.
이러한 이유로 다양한 알고리즘에도 활용된다. (RSA 키생성 알고리즘 등)
python을 통해 유클리드 호제법에 대한 구현 예제를 작성하였다.
euclide.py
import sys def gcd(a, b) : print "%d = %d x %d + %d" % (a,b,a/b,a%b) if(a % b == 0) : print "GCD : %d" % b return else : gcd(b, (a%b)) if len(sys.argv) < 3 : print "Usage : python euclide.py \"INT\" \"INT\""; sys.exit(-1) else : a = int(sys.argv[1]) b = int(sys.argv[2]) if a > b : gcd(a,b) else : gcd(b,a)
참조 URL : https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95
'Developer' 카테고리의 다른 글
[Heroku] Getting started with Heroku (0) | 2016.05.09 |
---|---|
[gradle] How To Speed up Gradle build time (0) | 2016.04.27 |
[Redis] Installation Redis Cluster with Docker on OSX (0) | 2016.02.11 |
[Docker] How to use Docker on OS X (0) | 2016.02.11 |
[vim] How to use Shell Command on VIM (2) | 2016.01.28 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- 해외여행
- 도덕경
- 영문법
- JBOSS
- 대명사 구문
- it
- NGINX
- nodejs
- 베트남
- Python Django
- ubuntu
- 가정법
- hadoop
- 비지니스 영어
- 영작
- k8s
- 조동사
- 비교구문
- mongoDB
- maven
- memcached
- redis
- Business English
- 여행
- 스페인 여행
- 다낭
- hdfs
- Python
- AWS
- PostgreSQL
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
글 보관함