还是数学题,理一下质因数的概念,什么是质因数?即:每个合数都可以写成几个质数相乘的形式,其中每个质数都是这个合数的因数。首先要确定一个数是不是质数,用笔不好计算。借助于计算机不难实现,以下使用php来分解质因数。
//判断一个数是否质数 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; } //求合数的质因数 function getPrimeFactorization($num) { if (isPrimer($num)) { //不是合数,直接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; } //调用求解 var_dump(getPrimeFactorization(100));
得到结果:
array(4) { [0]=> int(2) [1]=> int(2) [2]=> int(5) [3]=> int(5) }
即:100分解质因数为:2x2x5x5,质因数是:2和5