태그 자료실

회원로그인

무료회원가입 보안로그인

아이디/비밀번호찾기

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

13년 전

두수 사이에 최대공약수가 존재한다면,
$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);

추천 목록

번호	제목
1,895	웹 서버 접속자의 IP 주소 혹은 도메인명을 가져오는 함수
1,894	디렉 토리별 용량 구하기 3가지
1,893	http://홈주소/?mode=xxx 하는방법
1,892	www 떼고 접속하면 다시 www붙은 주소로 리다이렉션 걸기
1,891	특정시간에만 음악 튿기
1,890	일반페이지 일경우 메뉴클릭시 현재 페이지 표시하기
1,889	[함수] eregi_replace 내용중 html 태그 모두 제거 하기
1,888	한글기준으로 문자 자르기 함수
1,887	도메인주소/?2ustory
1,886	[함수] shuffle 활용한 랜덤 텍스트 추출
1,885	[함수] htmlspecialchars() 역변환(반대) 함수
1,884	GET, POST 하나로 묶기
1,883	[함수] sprintf 소수점 자리수 줄이기
1,882	[함수] foreach 폼(form)으로 넘긴 폼값 리스트 뽑기
1,881	date 함수 이용한 요일 구하기
1,880	셀렉트 박스 선택시 선택 옵션보여주기
1,879	[함수] implode , join 문자열 자르기와 합치기
1,878	[함수] stripslashe \를 제거
1,877	[함수] addslashes \를 추가
1,876	[함수] str_replace 치환함수
1,875	[함수] strcmp 두개의 문자열 비교
1,874	[함수] substr 전체 문자열중 일정 부분 추출
1,873	[함수] strtolower / strtoupper 대소문자 변환
1,872	[함수] fwrite / fputs 파일에 문자열을 쓴다.
1,871	텍스트 내부에 포함된 탭 문자 제거하기
1,870	[함수] 특수문자 제거 정규표현식 preg_replace 활용
1,869	페이징 기법과 등차수열
	최대공약수 구하기 (유클리드 알고리즘)
1,867	소수인지 확인하기 (유클리드 알고리즘)
1,866	정규표현식