數學題目

好久沒有打電話來的叔叔打電話來問我兩個問題：

1. 求一正整數，其除以 680, 912, 1260 的餘數都相同。
2. 1-1000的整數中，與 72 互質，且與 720不互質的數有幾個？

第一題反射就是求最小公倍數。怎麼算勒？國小數學都還給老師了。

答案是 lcm(680,912,1260)=1627920

第二題解法：

1. 先將 72 跟 720 的質因數分解，得到 72的質因數是 2,3, 720 是 2,3,5.
2. 滿足與 720 不互質表示該數字需要是 2,3,5 的倍數，但不能是 2,3 的倍數。所以答案是 1-1000 中 5 的倍數的數量，扣除又是 2 的倍數，又是 3 的倍數。
3. 5 的倍數 1000/5=200 ,是2又是5的倍數, 1000/(2x5)=100, 是3又是5的倍數,1000/(3x5)=66, 是2又是3又是5的倍數 1000/(2x3x5)=33 個: 又是 2 又是3的倍數有 100+66-33=133
4. 故 200-(100+66-33)=67

驗算法:

第一題 小公倍數的程式

/* 笨蛋暴力法
(float)$i=680;
$a=0;
while($a==0){
$x=(float)$i%680;
$y=(float)$i%912;
$z=(float)$i%1260;
if($x == $y and $y == $z ) {
echo “$i,$x,$y,$zn”;
break;
}
$i++;
}
*/
function gcd ($a, $b) { //最大公因數
echo “.”;
if ($b < 0 || $a < 0) {
return gcd(abs($a), abs($b));
}
if ($b > $a) {
return gcd($b, $a);
}
$rem = $a % $b;
return (($rem == 0)?$b:gcd($b,$rem));
}

function lcd($a,$b) { // 最小公倍數
return (($a * $b) / gcd($a, $b));
}

echo lcd(lcd(680,912),1260);
?>

第二題 暴力法

$count=0;
for ($i=1; $i<=1000; $i++) {
if ($i % 5 != 0 or $i % 2 == 0 or $i % 3 == 0 ) continue;
$count++;
echo “$i “;
}
echo “\n$count”;
?>

5 25 35 55 65 85 95 115 125 145 155 175 185 205 215 235 245 265 275 295 305 325 335 355 365 385 395 415 425 445 455 475 485 505 515 535 545 565 575 595 605 625 635 655 665 685 695 715 725 745 755 775 785 805 815 835 845 865 875 895 905 925 935 955 965 985 995
67

當然漂亮一點就是用 最大公因數囉

for ($i=1;$i<=1000;$i++)
if(gcd($i,72)==1 and gcd($i,720)!= 1)
echo “$i “;