Page

[算法]使用php算法得出1万以内的完全数并列出因子

3340Anson16-06-27


完全数(Perfect number),又称完美数或完备数,是一些特殊的自然数。它所有的真因子(即除了自身以外的约数)的和(即因子函数),恰好等于它本身。如果一个数恰好等于它的因子之和,则称该数为“完全数”。

完全数(Perfect number),又称完美数完备数,是一些特殊的自然数。它所有的真因子(即除了自身以外的约数)的和(即因子函数),恰好等于它本身。如果一个数恰好等于它的因子之和,则称该数为“完全数”。


1到10000的完全数有四个:


6--因数有:1+2+3
28--因数有:1+2+4+7+14
496--因数有:1+2+4+8+16+31+62+124+248
8128--因数有:1+2+4+8+16+32+64+127+254+508+1016+2032+4064


具体代码如下:

<?php
header("content-type:text/html;charset=utf-8");


    for ($i = 1; $i <= 10000; $i++) {
        for ($j = 1; $j <= $i/2; $j++) {
            if ($i % $j == 0) {
                $arr[] = $j;
            }
        }
        if (isset($arr)) {
            if (array_sum($arr) == $i) {
                $res[$i]['perfect'] = $i;
                $res[$i]['factors'] = $arr;
            }
            $arr = array();
        }
    }
    
    if (isset($res)) {
        foreach($res as $key =>$value) {
            echo $value['perfect'].'--因数有:'.implode(',', $value['factors']).'<br>';
        }
    }else {
        echo '没有完全数';
}


效果图如下:


blob.png

代码解释:


①第一个for循环循环这1万个整数$i,接着嵌套一个for循环,作用是使用比$i小的整数$j,通过取模算法计算出$i的因子,并将所有因子存进数组$arr中;


②接下来的if判断使用isset函数判断数组是否有值,有值就是有因子的意思,再通过array_sum函数求数组里面整数的总和,判断和是否等于当前的$i,等于的话就是完全数,将完全数存进二维数组$res中,并将该完全数的因子赋值给$res[$i]['factors'];


③然后将原来的$arr数组清空,重新存下一个完全数;


④最后判断$res有没有值,使用foreach遍历$res中的键值,使用implode分离数组的因子。


后记:代码是我从网络上搜集然后自己做了一些修改,使用这种方法获取完全数并不是很理想,延迟很高,获取1到10万的完全数会提示30秒超时停止,如果大家有什么更好的方法,欢迎分享!


代码来源网络

2016年6月27日


-------------------------2016年6月29日更新------------------


考虑到完全数最大的因子就是它的二分之一,所以我将第六行的for语句改成for($j=1;$j<=$i/2;$j++),运行速度大概提高一秒


-------------------------2016年6月30日更新-------------------


有朋友问我,下面的完全数为什么要存在三维数组里面,我今天发现其实不写三维数组,写成二维数组也可以,这之间影响不大,可能主要考虑的是数据看起来更加直观而已;

if (array_sum($arr) == $i) {
                $res[$i]['perfect'] = $i;
                $res[$i]['factors'] = $arr;
            }
 
 //改动之后
 
 if (isset($arr)) {
            if (array_sum($arr) == $i) {      
                $res[$i] = $arr;
            }
            $arr = array();
        }
        
  //相应的下面的遍历也要修改成如下
  
  foreach($res as $key =>$value) {
            echo $key.'--因数有:'.implode('+', $value).'<br>';
        }


以上两种方法都是可以运行得,速度差不多。