PHP 质因数分解

  1. 找出比 $number 小的质素
  2. 再分别除以比 $number 小的质素找出质因子
<?php
$stime = microtime(true); #获取程序开始执行的时间

class PrimeNumber
{

    /**
     * 判断 $number 是否为质素
     *
     * @param [type] $number
     * @return boolean
     */
    static function isPrime($number)
    {
        if ($number == 1) return false;

        if ($number == 2 || $number == 3) return true;

        for ($i = 2; $i <= sqrt($number); $i++) {
            if ($number % $i == 0)
                return false;
        }
        return true;
    }

    /**
     * 找出比 $number 小的质素
     *
     * @param [type] $number
     * @return void
     */
    function getPrimes($number)
    {
        $result = [];
        for ($i = 2; $i <= $number; $i++) {
            if (self::isPrime($i)) {
                $result[] = $i;
            }
        }

        return $result;
    }

    /**
     * 分别除以比 $number 小的质素
     *
     * @param integer $number
     * @return void
     */
    function factorization(int $number)
    {
        if (self::isPrime($number)) {
            return $number . " is Prime Number";
        }
        $result = [];
        if ($number % 2 == 0) $result[] = 2;

        $primes = $this->getPrimes(ceil($number / 2));

        for ($i = 0; $i < count($primes); $i++) {
            if ($number % $primes[$i] == 0) {
                $result[] = $primes[$i];
            }
        }

        return [
            'number' => $number,
            'factors' => $result,
            //'primes' => $primes
        ];
    }
}

$factors = (new PrimeNumber())->factorization(65535);
print_r($factors);

$etime = microtime(true); #获取程序执行结束的时间
$total = $etime - $stime;   #计算差值

echo "\n{$total} times \n";

测试一下