php - 计算欧拉计划的主要因素

标签 php performance algorithm

我需要找到一个大数的最大质因数:最多 12 位 (xxx,xxx,xxx,xxx)。我已经解决了这个问题,代码适用于小数字(最多 6 个地方);但是,代码运行速度不够快,不会在我的服务器上触发 1000 亿次超时。

我找到了解决方案,感谢大家。

代码:

<?php   
    set_time_limit(300);

    function is_prime($number) {
        $sqrtn = intval(sqrt($number));
        //won't work for 0-2
            for($i=3; $i<=$sqrtn; $i+=2) {
                if($number%$i == 0) {
                    return false;
                }
            }
        return true;
    }   

    $initial = 600851475143;
    $prime_factors = array();

    for($i=3; $i<=9999; $i++) {
        $remainder = fmod($initial, $i);
        if($remainder == 0) {
            if(is_prime($i)) {
                $prime_factors[] = $i;
            }
        }
    }

    //print_r($prime_factors);
    echo "\n\n";
    echo "<b>Answer: </b>". max($prime_factors);    
?>

本例测试编号为600851475143。

最佳答案

您的代码不会找到任何大于sqrt(n) 的质因数。要纠正这个问题,您还必须为找到的每个因子(不仅是质因子)测试商 $number/$i

您的is_factor 函数

function is_factor($number, $factor) {
    $half = $number/2;
    for($y=1; $y<=$half; $y++) {
            if(fmod($number, $factor) == 0) {
            return true;
        }
    }
}

没有意义。 $y 和循环的作用是什么?如果 $factor 不是 $number 的除数,那将执行 $number/2 完全没有意义的除法。解决了这个问题后,重新排序 is_prime_factor 中的测试将提供很好的加速,因为只需要对 $number 的少数除数执行昂贵的素数测试。

关于php - 计算欧拉计划的主要因素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9370839/

相关文章:

php - 使用 S2Members API 和 wc_create_order 在 WooCommerce 中创建订单

php - `$/i` 在正则表达式中的含义

python - 为什么内置 array.fromlist() 比 cython 代码慢?

java - 按排序顺序返回唯一条目的随机数生成器

c - 逐词短语匹配

php - UTF8中的字符编码表

php - WordPress PHP htmlspecialchars(get_field... 无法读取数组?

python - 将 Django ORM 查询从多个数据库查找优化为可能的一个数据库查找

android - 如何开始在 Android 上学习低级编码

c# - 随机选择设置位的有效方法