還是數(shù)學(xué)題，理一下質(zhì)因數(shù)的概念，什么是質(zhì)因數(shù)?即：每個(gè)合數(shù)都可以寫成幾個(gè)質(zhì)數(shù)相乘的形式，其中每個(gè)質(zhì)數(shù)都是這個(gè)合數(shù)的因數(shù)。首先要確定一個(gè)數(shù)是不是質(zhì)數(shù)，用筆不好計(jì)算。借助于計(jì)算機(jī)不難實(shí)現(xiàn)，以下使用php來(lái)分解質(zhì)因數(shù)。
[code lang=”php”]
//判斷一個(gè)數(shù)是否質(zhì)數(shù)
function isPrimer($n)
{
if ($n < 2) {
return false;
}
$flag = true;
$sqrt = floor(sqrt($n));
for ($i = 2; $i <= $sqrt; $i++) {
if ($n % $i === 0) {
$flag = false;
break;
}
}
return $flag;
}
//求合數(shù)的質(zhì)因數(shù)
function getPrimeFactorization($num)
{
if (isPrimer($num)) {
//不是合數(shù),直接pass并返回false
return false;
}
static $primeFactor = array();
for ($i = 2; $i < $num; $i++) {
if ($num % $i === 0) {
$m = $num / $i;
if (isPrimer($i)) {
$primeFactor[] = $i;
if (isPrimer($m)) {
$primeFactor[] = $m;
break;
} else {
getPrimeFactorization($m);
}
break;
}
}
}
return $primeFactor;
}
//調(diào)用求解
var_dump(getPrimeFactorization(100));
[/code]
得到結(jié)果：
[code lang=”bash”]
array(4) {
[0]=>
int(2)
[1]=>
int(2)
[2]=>
int(5)
[3]=>
int(5)
}
[/code]
即：100分解質(zhì)因數(shù)為：2x2x5x5，質(zhì)因數(shù)是：2和5
