태그 자료실

회원로그인

무료회원가입 보안로그인

아이디/비밀번호찾기

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

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,072	텍스트 내부에 포함된 탭 문자 제거하기
1,071	[함수] 특수문자 제거 정규표현식 preg_replace 활용
1,070	페이징 기법과 등차수열
	최대공약수 구하기 (유클리드 알고리즘)
1,068	소수인지 확인하기 (유클리드 알고리즘)
1,067	정규표현식
1,066	여러 공백을 한개의 공백으로 치환, 특수문자 삭제
1,065	PHP를 이용한 이미지 사이즈 편집
1,064	데이타베이스의 테이블 리스트 가져오기
1,063	랜덤 문자열생성 1 (쿠폰기능에 활용)
1,062	외부문서 읽어오기
1,061	include(), require(), require_once() 차이점
1,060	랜덤 문자열생성 2 (쿠폰기능에 활용)
1,059	[함수] html_replace - HTML관련 문자를 해석되지 않도록 치환 함
1,058	정규식 표현 preg_match_all
1,057	[함수] break - 현재의 반복문을 빠져나간다
1,056	[함수] do..while
1,055	[함수] sizeof() 함수의 용도...
1,054	[함수] fileatime 해당 파일에 마지막으로 액세스한 시간 뽑기
1,053	[함수] filemtime 해당 파일의 마지막으로 수정된 시간 뽑기
1,052	현재보고 있는 파일의 폴더명 구하기
1,051	[함수] foreach 활용 예제
1,050	배열 중복 제거 array_unique
1,049	앞 글자 몇개만 보여주고 나머지 글자수는 * 로 치환하기
1,048	time()함수로 입력한 데이터들을 월별로 뽑아내기
1,047	flush , sleep 사용
1,046	하위 폴더 생성하기 소스
1,045	[함수] 이번달 일수 구하기
1,044	최대값 구하기
1,043	[함수] 업로드된 파일 마지막 수정 날짜 구해오기