<?php

set_time_limit(0);
//ini_set('memory_limit','1G');
header('Content-Type: text/html; charset=utf-8');



/*

최대공약수 찾는 방법

1. 개별의 약수를 구해 각 약수의 최대값을 서로 비교해본다

2. 공통 소인수분해해서 나눈 소인수만 곱한다.

3. 개별적으로 소인수 분해하여 소인수를 곱하고 지수끼리의 곱으로 만든다음
두 수사이의 공통부분을 찾아 곱한다.

숫자가 작아서
1의 방법도 아주 빠르겟지만
2의 방법으로 구현 해봄
*/



function microtime_float() {

    list($usec, $sec) = explode(" ", microtime());
    return (((float)substr((string)$usec, 0, 4) + (float)$sec)) * 1000;
}



function get_excute_time($msg, $start_time){

    $end_time = microtime_float();
    $time = ($end_time - $start_time) / 1000;

    echo "$msg : $time seconds" . PHP_EOL ;
}



//주어진 숫자까지 포함된 모든 소수를 구함
function get_prime ($end) {

    $end = (int)$end;
    $end = ($end > 100000) ? 100000 : (($end <= 10) ? 10 : $end); //100000 보다 크면 100000, 10보다 작거나 같으면 10

    $prime = Array(2, 3, 5, 7);

    if ($end == 10) {

        return $prime;
    }

    for ($search = 11; $search <= $end; $search += 2) { //홀수만 대입

        if (substr((string)$search, -1) == 5)// 5보다 큰 자연수 중에 5로 끝나는 소수는 없다. 모두 5로 나누어짐, 직접 나누는것보다 끝자리만 확인하는것이 더 빠를것 같아 처리
            continue;

        if (check_prime ($prime, $search) == true)
            $prime[] = $search;
    }

    return $prime;
}



//기존에 가진 소수 배열로서 소수인지 판별
function check_prime ($prime, $search) {

    $search = (float)$search;//float(double) 형으로 형변환

    if ($search > 2 && (int)substr((string)$search, -1) % 2 == 0)// 2보다 큰 자연수 중에 0, 2, 4, 6, 8로 끝나는 소수는 없다. 모두 2로 나누어짐
        return false;

    if ($search > 5 && substr((string)$search, -1) == 5)// 5보다 큰 자연수 중에 5로 끝나는 소수는 없다. 모두 5로 나누어짐
        return false;

    $max = bcsqrt((string)$search, 1);//결과값이 문자형으로 반환, $search 가 2147483647 보다 클수 있으므로 bcsqrt

    if (strpos($max, '.') === false) {//$search 는 $max 의 제곱이라는 의미

        //echo "$search $max 제곱근" . PHP_EOL;
        return false;
    }

    $max = (int)$max; //정수형으로 변환, 소수점 이하 버려짐
    foreach($prime as $p){

        if ($p > $max) {//비교를 위해 대입하는 소수가 비교되는 수의 제곱근보다 클수 없다.

            return true;
        }
        else if (bcmod($search, (string)$p)  == 0) {//다른소수의 배수이므로 소수가 아니다. $search 가 2147483647 보다 클수 있으므로 bcmod

            //echo "$search $p 의 배수" . PHP_EOL;
            return false;
        }
    }

    return true;
}



function get_prime_divisor ($a, $b) {

    $result = 1;

    if ($a > $b) {

        $high = $a;
        $low = $b;
    }
    else {

        $high = $b;
        $low = $a;
    }

    if ($high >= $low * 2) {//두배이상의 수이므로 배수 인지 한번 나누어본다.

        if ((int)($high / $low) * $low == $high) {//큰수가 작은수의 배수이므로 작은수가 최대 공약수

            echo "$high 는 $low 의 배수" . PHP_EOL;
            return $low;
        }
    }

    //사용할 소수를 구한다.
    $max = (int)sqrt($high);
    $prime = get_prime($max);

    while(1) {

        $high_last = (int)substr((string)$high, - 1);
        $low_last = (int)substr((string)$high, - 1);

        if ($high_last % 2 == 0 && $low_last % 2 == 0) {//둘다 2로 나누어짐

            echo "$high 와 $low 는 2로 나누어짐" . PHP_EOL;

            $high /= 2;
            $low /= 2;
            $max = (int)sqrt($high);
            $result *= 2;
        }
        else if ($high_last %5 == 0 && $low_last %5 == 0) {//둘다 5로 나누어짐

            echo "$high 와 $low 는 5로 나누어짐" . PHP_EOL;

            $high /= 5;
            $low /= 5;
            $max = (int)sqrt($high);
            $result *= 5;
        }
        else {

            reset($prime);
            foreach($prime as $p) {

                if ($p == 2 || $p == 5)
                    continue;

                if ($p > $max)
                    return $result;

                if ($high % $p == 0 && $low % $p == 0) {//둘다 $p로 나누어짐

                    echo "$high 와 $low 는 $p 로 나누어짐" . PHP_EOL;

                    $high /= $p;
                    $low /= $p;
                    $max = (int)sqrt($high);
                    $result *= $p;
                    break;
                }
            }
        }
    }
}



$a = 3024;
$b = 4752;

$start_time = microtime_float();
$result = get_prime_divisor ($a, $b);
echo PHP_EOL . "$a 와 $b 의 최대공약수는 ? " . $result . PHP_EOL . PHP_EOL;
get_excute_time("일반 방식으로 구한 시간", $start_time);

?>

4752 와 3024 는 2로 나누어짐
2376 와 1512 는 2로 나누어짐
1188 와 756 는 2로 나누어짐
594 와 378 는 2로 나누어짐
297 와 189 는 3 로 나누어짐
99 와 63 는 3 로 나누어짐
33 와 21 는 3 로 나누어짐

3024 와 4752 의 최대공약수는 ? 432

일반 방식으로 구한 시간 : 0 seconds

오래전에 이걸 배운거 같은데
생각을 못햇습니다.

좋은 내용 감사합니다.