质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1与该数本身两个正因数的数)--wiki
那么怎么来判断一个数是不是素数呢?常用的方法一样平常有:
试除法 将n除以每个大于1且小于即是 n的平方根之整数 m。若存在一个相除为整数的结果,则 n不是素数;反之则是个素数; (本日的题目用到)筛法 一个能给出某个数值以下的所有素数之算法,称之为素数筛法,可用于只利用素数的试除法内。题目进入主题,题目哀求:将 n! (n的阶乘)分解成素数因子;举例解释;
n = 12; decomp(12) 终极输出结果-> \"大众2^10 3^5 5^2 7 11\"大众
由于12的阶乘 能够分解成 10个2 、5个3、2个5、一个7和11 的乘积;同理;
n = 22; decomp(22) 终极输出结果-> \"大众2^19 3^9 5^4 7^3 11^2 13 17 19\公众
n = 25; decomp(25) 终极输出结果-> 2^22 3^10 5^6 7^3 11^2 13 17 19 23
素数要递增排列;如果指数是1则不用显示;阶乘可以是一个很大的数字(4000!
有12674位数字,n从300到4000),所有要把稳算法的效率问题。
代码勉强通过了测试,但是实行效率很低;
<?phperror_reporting(0);function decomp($n) {$num_count = array();$primes = get_prime($n);for($i=2;$i<=$n;$i++){$start = $i;if(in_array($start,$primes)){$num_count[$start]++;continue;}foreach ($primes as $j) {if($i<$j){break;}$start = $i;while ($start>1) {if($start%$j==0){$num_count[$j]++;$start /= $j;}else{break;}}}}$decomp = '';foreach ($num_count as $key => $value) {if($value>1){$decomp .= ' '.$key.'^'.$value;}else{$decomp .= ' '.$key;}}return ltrim($decomp,' ');}function get_prime($num){$prime = array();for($i=2;$i<=$num;$i++){$is_prime = true;for ($j = 2; $j <= sqrt($i); $j++) { if ($i % $j == 0) { $is_prime = false; } } if($is_prime){ $prime[] = $i; }}return $prime;}var_dump(decomp(12));var_dump(decomp(22));var_dump(decomp(25));/n = 12; decomp(12) -> \公众2^10 3^5 5^2 7 11\"大众since 12! is divisible by 2 ten times, by 3 five times, by 5 two times and by 7 and 11 only once.n = 22; decomp(22) -> \公众2^19 3^9 5^4 7^3 11^2 13 17 19\"大众n = 25; decomp(25) -> 2^22 3^10 5^6 7^3 11^2 13 17 19 23/ 大神的代码
看到大神的逻辑,是不是恍然大悟?一起学习一下;