0

这是一个简单的程序，用于查找质数，以便在稍后阶段检查数字的除法。

我试图通过最初取数字的整数平方根来缩短它以分解复杂性。但是执行脚本仍然需要很长时间。我可以在我的代码中实现哪些其他更改以减少执行时间（我已经将最大执行时间设置为 5 分钟）

<?php
error_reporting(E_ALL);
$num = 600851475143;
//$sqrt_num = (int)sqrt($num);

for( $j = 2; $j <= $num; $j++ )
{
    for( $k = 2; $k < $j; $k++ )
    {
        if( $j % $k == 0 )
        {
        break;
        }

    }
    if( $k == $j )
    {
        //echo "Prime Number : ", $j, "<br>";
        if( $num % $j == 0 )
        {
        echo "Prime number : ", $j, "<br>";
        }
    }
}

编辑刚刚评论了 sqrt 的行，因为这似乎是正确的..但循环仍然需要很多时间。

4

3 回答 3

2

减少此代码执行时间的最佳方法是删除它。每次运行时都没有必要计算每个素数——它们不会很快改变。

运行一次，将其写入文件或数据库，并在需要时使用。我个人将它放在一个数组中以备后用。

于 2013-03-03T09:57:33.353 回答
2

提高代码执行时间的一种方法是：

$num = 1000;

for($j = 2; $j <= $num; $j++)
{
    $cond = sqrt($j);
    for($k = 2; $k <= $cond; $k++)
    {
        if($j % $k == 0)
        {
        break;
        }

    }
    if($k > $cond)
    {
        echo 'Prime number: ' . $j . '<br>';
    }
}

但是没有必要每次都从一开始就计算素数。您可以每隔 30 秒左右记住一次您所在的位置，将结果保存到数据库、文件或数组中，然后重新启动脚本，该脚本应该从停止的地方继续。

于 2013-03-03T10:12:21.473 回答
1

这是通过试除法分解的基本算法；我不懂PHP，所以我只给出伪代码：

function factors(n)
    f, fs := 2, []
    while f * f <= n
        while n % f == 0
            append f to fs
            n := n / f
        f := f + 1
    if n > 1 append n to fs
    return fs

有比找到数的因数更好的方法，但即使是这种简单的方法也足以解决您试图解决的 Project Euler 问题；你应该在不到一秒钟的时间内就有一个解决方案。当您准备好使用素数进行更多编程时，我谦虚地在我的博客上推荐这篇文章。

于 2013-03-03T12:47:25.940 回答