태그 자료실

회원로그인

무료회원가입 보안로그인

아이디/비밀번호찾기

최대공약수 구하기 (유클리드 알고리즘)

12년 전

두수 사이에 최대공약수가 존재한다면,
$A와 $B 사이에는 최대공약수 $G를 가지는 수식이 완성된다.

인수분해

$A = $G * $x  ----- 1식
$B = $G * $y  ----- 2식

1식과 2식을 다시 표현하면,

$A - $B = ($G * $x) - ($G *$y) = $G * ($x - $y) ----- 3식
$A % $B = ($G * $x) % ($G *$y) = $G * ($x % $y) ----- 4식

3식에서, $A와 $B가 최대공약수를 가지면, $A-$B도 $A와 $B가 가지는 최대공약수를 같이 같는다.
$G = GCD($A, $B) = GCD($A - $B, $B)  = GCD($B, $A)

4식에서, $A와 $B가 최대공약수를 가지면, $A%$B도 $A와 $B가 가지는 최대공약수를 같이 같는다.
$G = GCD($A, $B) = GCD($A % $B, $B)  = GCD($B, $A)

즉, $G = GCD($A, 0) = $A 가 성립되는 것이다. ( 0은 어떤수와 곱해도 0이기 때문)

<?php
function get_cgd($u, $v)
{
    $t = 0;

    while($v) {
        $t = $u % $v;
        $u = $v;
        $v = $t;
    }
    return $u;
}
?>

echo get_cgd(45, 10);

추천 목록

번호	제목
2,225	특정한 달의 생일인 사람 리스트 가져오기
2,224	PHP의 소켓 함수
2,223	PHP와 Ajax을 이용해서 데이터 처리하기
2,222	파일을 무조건 다운로드 시키기
2,221	include()용 웹경로 -> 상대경로 변환 함수
2,220	빠른 프로세서를 위한 코딩스타일
2,219	환경변수 불러오기
2,218	잘못된 PHP 코딩 스타일
2,217	엑셀(*.xls) 화일을 PHP에서 읽기
2,216	파일 다운로드 함수(멀티 이어받기/속도제한)
2,215	주민등록 번호로 나이 구하기
2,214	echo & print 비교
2,213	썸네일 소스[GD 사용]
2,212	cURL을 이용한 웹페이지 가져오기
	최대공약수 구하기 (유클리드 알고리즘)
2,210	소수인지 확인하기 (유클리드 알고리즘)
2,209	PHP로 HTTP 인증하기
2,208	phpinfo 정보 - 미리 정의된 변수
2,207	문자열을 X로 마킹하는 함수
2,206	PHP에서 성능 개선을 위한 유용한 팁
2,205	파일 다운로드2 (헤더 이용)
2,204	자주 쓰이는 PHP 함수
2,203	PHP5의 새로운 기능
2,202	입력받은 IP주소를 127.0.☆.1 형태로 바꿈.
2,201	include(), require(), require_once() 차이점
2,200	DB의 무한카테고리 가져오기
2,199	어떤 경로로 해서 이 홈에 오게 됐는지 알아내는 방법
2,198	from 태그의 이해
2,197	첨부메일 보내기
2,196	항상 새로고침 해더 설정