10000 이하의 모든 완전수

<?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

아주 좋은 답변 감사합니다~

다른 답안도 한번 제시해봅니다~

function get_perfect($num){
$sum = 0;

for($n=4; $n<=$num; $n++){
$sum=0;
for($s=1; $s<=sqrt($n); $s++){
if($n%$s==0) {
$sum+=$s;
if($n != $s * $s && $s>1) {
$sum+=$n/$s;
}
}
}
if($sum==$n){
echo $n . ", ";
}
}
}

get_perfect(10000);

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

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