<?php

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



/*

완전수 자체는 몇개 존재 하지 않는다.
유클리드 공식을 이용하면 쉽게 구할수 있다.

유클리드 공식에 의한 방법과
일반적인 방법 두가지방법으로 개별 처리

유클리드 방정식
2^(n-1) * (2^n - 1)
n 은 소수만 대입가능
100^100 내에서는 사실인것으로 검증됨

일반적인 방식
약수의 갯수가 4개 이상인 것만 가능
즉, 소수는 애초에 검색 대상에서 제외
약수의 합 - (자기자신 * 2) == 0

*/



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_divisor ($number) {

    $return = Array(1, $number);

    $max = (int)sqrt($number);
    for ($i = 2; $i <= $max; $i++) {

        $div = $number / $i;
        if ((int)$div * $i == $number) {

            $return[] = $i;
            $return[] = $div;
        }
    }

    return $return;
}



function get_perfet ($search) {

    $return = Array();

    $prime = get_prime($search);

    for($number = 2; $number <= $search; $number++) {

        if (in_array($number, $prime))
            continue;

        $number_divisor = get_divisor ($number);

        if (array_sum($number_divisor) - ($number * 2) === 0) {

            $return[] = $number;
        }
    }

    return $return;
}



function get_perfet_euclid ($search) {

    $result = Array();

    //적당히 큰 소수를 뽑는다
    $prime = get_prime(100);

    foreach($prime as $number){

        $x = pow(2, $number - 1) * (pow(2, $number ) - 1);
        if ($x >= $search) {

            break;
        }

        $result[] = $x;
    }

    return $result;
}



$search = 10000;

$start_time = microtime_float();
$result = get_perfet ($search);
print_r($result);
get_excute_time("일반 방식으로 구한 시간", $start_time);

echo PHP_EOL;

$start_time = microtime_float();
$result = get_perfet_euclid ($search);
print_r($result);
get_excute_time("유클리드공식을 사용한 방식으로 구한 시간", $start_time);

?>

Array
(
    [0] => 6
    [1] => 28
    [2] => 496
    [3] => 8128
)
일반 방식으로 구한 시간 : 1.01 seconds

Array
(
    [0] => 6
    [1] => 28
    [2] => 496
    [3] => 8128
)
유클리드공식을 사용한 방식으로 구한 시간 : 0 seconds

이것도 좋은 방법 같습니다.
제가 풀은 두가지 방법중 get_perfect 보다는 훨신 좋은듯합니다.

그러나 100000 부터 많이 느려지는 단점이 있습니다.