피타고라스의 수

흠.. 숙제는 직접 ㅋㅋㅋ



농담인거 아시죠? ^.^

<?php

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



/*
원시 피타고라스의 수를 찾아서
각 그것들의 배수들이 모든 피타고라스의 수가 된다.



원시 피타고라스의 수를 찾는 방법

(1) m과 n은 모두 홀수이다.
(2) m과 n은 서로 소이다.

자연수 m, n (m > n) 에 대해서
a = mn
b = (m^2 - n^2)/2
c = (m^2+n^2)/2

참고 http://ko.wikipedia.org/wiki/%ED%94%BC%ED%83%80%EA%B3%A0%EB%9D%BC%EC%8A%A4_%EC%88%98

*/



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 gcd ($p, $q) {

if ($q == 0) return $p;

return gcd ($q, $p % $q);
}



$start_time = microtime_float();



$input = 100;// c가 100 미만인 모든 피타고라스의 수

$default = Array();

//$n. $m 은 홀수, $n < $m, $n과 $m 은 서로소
for ($n = 1; $n < $input; $n++) {

for ($m = $n + 2; $m < $input; $m++) {

if (gcd ($m, $n) != 1)
continue;

$a = $m * $n;

$b_ = (pow($m, 2) - pow($n, 2));
$b = $b_ / 2;

$c_ = (pow($m, 2) + pow($n, 2));
$c = $c_ / 2;

if ($c >= 100)
break;

if ($b_ % 2 == 1 || $c_ % 2 == 1)
continue;

if ($a > $b) {

$t = $a;
$a = $b;
$b = $t;
}

$default[] = Array('a' => $a, 'b' => $b, 'c' => $c);
}
}


//print_r($default);
$result = $default;
foreach($default as $v) {

$i = 2;
while (1) {

$v['c_'] = $v['c'] * $i;
if ($v['c_'] >= 100)
break;

$v['a_'] = $v['a'] * $i;
$v['b_'] = $v['b'] * $i;

$result[] = Array('a' => $v['a_'], 'b' => $v['b_'], 'c' => $v['c_']);

$i++;
}
}

sort($result);
print_r($result);

get_excute_time("진행 시간", $start_time);

?>

// (1) m과 n은 모두 홀수이다. => 이므로 for문에서 홀수만 증가되도록 수정해 보았습니다.

$input = 100;

function gcd ($p, $q) {

if ($q == 0) return $p;

return gcd ($q, $p % $q);
}

for ($n = 1; $n < $input; $n += 2) {

for ($m = $n + 2; $m < $input; $m += 2) {

if (gcd ($m, $n) != 1) continue;

$c = ($m * $m + $n * $n) / 2;

if ($c >= $input) break;

$a = $m * $n;

$b = ($m * $m - $n * $n) / 2 ;

if ($a > $b) {
$t = $a; $a = $b; $b = $t;
}

printf('%d^2 + %d^2 = %d^2 <br>', $a, $b, $c);

}
}

2씩 더하는 것을 빼먹었네요

고맙습니다

너무나 좋은 답변 늘 감사합니다~

피타고리스의 수를 찾는 또다른 방법을 소개합니다.

일단 첫번째 방법으로 유창화님께서 소개해주신 방법

a^2 + b^2 = c^2 를 만족하는 a,b,c 쌍을 찾을 때,
a = mn
b = (m^2 - n^2)/2
c = (m^2+n^2)/2
를 만족하고,
(1) m과 n은 모두 홀수이다.
(2) m과 n은 서로 소이다.
를 만족하면 a, b ,c 는 피타고라스의 수가 됩니다.

다른 방법도 존재합니다.
a = 2n+1
b = 2 * n^2 + 2*n
c = 2 * n^2 + 2*n + 1
n 은 자연수

순서대로 대입하면
n =1 일 때 a = 3, b = 4, c = 5
n =2 일 때 b = 5, b = 12, c = 13

이런 식으로 구할 수 있습니다~

함수로 구현하는 건 패쓰............