php分解质因数

还是数学题,理一下质因数的概念,什么是质因数?即:每个合数都可以写成几个质数相乘的形式,其中每个质数都是这个合数的因数。首先要确定一个数是不是质数,用笔不好计算。借助于计算机不难实现,以下使用php来分解质因数。

[code lang=”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));
[/code]

得到结果:

[code lang=”bash”]

array(4) {
[0]=>
int(2)
[1]=>
int(2)
[2]=>
int(5)
[3]=>
int(5)
}

[/code]

即:100分解质因数为:2x2x5x5,质因数是:2和5

分析质因数java版

相关文章

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注




Enter Captcha Here :

qq
微信
微信
分享本页
返回顶部