태그 자료실 1524

회원로그인

무료회원가입 보안로그인

아이디/비밀번호찾기

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

16년 전

두수 사이에 최대공약수가 존재한다면,
$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,891	입력 필드에서 특정단어(예:#err)가 포함되었을 때 실시간 감지 및 경고창 띄우기
2,890	데이터베이스 최적화와 쿼리 효율성을 높이 검색 성능을 개선하는 방법
2,889	간단한 게시판 만들기
2,888	PHP의 php.ini 파일에서 설정할 수 있는 주요 항목들을 카테고리별로 정리
2,887	유튜브 동영상의 썸네일 이미지를 체크하여 유효한 영상이아닐때 연결된 체크박스를 자동으로 체크
2,886	이미지 URL이 유효하지 않을 때, 해당 이미지와 연결된 체크박스를 자동으로 체크
2,885	HTTPS로 접속한 사용자를 강제로 HTTP로 리디렉션 하려면
2,884	PHP에서 MP3 파일을 직접 읽고 스트리밍 하기
2,883	현재 페이지가 location.reload()에 의해 새로고침되었는지
2,882	텍스트 파일을 읽고, 각 줄의 끝에서 6글자를 삭제한 후, 결과를 새로운 파일에 저장합니다.
2,881	cURL을 사용하여 리다이렉트를 따라가 최종 URL 가져오기
2,880	[PHP] $_SERVER 환경변수
2,879	10진수 <-> 16진수 변환기 PHP소스
2,878	텍스트에 직접 그라데이션 색상을 적용하려면?
2,877	CSS를 사용하여 요소의 내용물에 따라 width를 조정하는 방법
2,876	웹서버 ip 확인
2,875	웹호스팅의 절대경로를 확인
2,874	input 입력 필드 앞뒤 공백 실시간 제거
2,873	Placeholder 포커스시 감추기
2,872	MySQL 중복된 데이터를 삭제
2,871	MySQL 중복 데이터 확인
2,870	sessionStorage.getItem 와 sessionStorage.setItem
2,869	제이쿼리 랜덤으로 배경색 변경
2,868	preg match에 관한 정규식
2,867	Stream an audio file with MediaPlayer 오디오 파일 스트리밍 하기
2,866	Audio Streaming PHP Code
2,865	PHP $ SERVER 환경 변수 정리
2,864	Vimeo (비메오) API 를 사용하여 플레이어 컨트롤하기
2,863	iframe 사용시 하단에 발생하는 공백 제거방법
2,862	아이프레임(iframe) 전체화면 가능하게 하기