일지 & 개발

이론 1. 유클리드 호제법이란? 두 개의 정수 혹은 다수의 자연수에서 최대공약수를 구하는 알고리즘이다. 원리는 두 수가 서로 나눠서 나머지를 구한다. 만약 나머지가 0이면 그 수가 최대 공약수가 되는것이다. 만약에 나머지가 0이 아니면 나머지가 0일 될때까지 두 수를 나누어 주면 된다. 기존 최대공약수를 구할때는 2개 이상에 각 수의 약수를 구한다음 공통으로 있는 약수중 최대값을 구해야 했다. 위의 그림을 보면 30, 24에서 학교에서 기본것으로 배운 토대로 최대공약수를 구한다면 먼저, 약수를 구해서 공통된 수가 6, 3, 2, 1이고 이중에서 가장 큰것이 6이다. 6이라는 숫자가 30, 24 최대 공약수이다 수가 30, 24라서 각 약수의 수가 적어서 구하는데 금방 걸리는데 100단위 또는 1000단위..