php - 如何优化这个算法

Question

我试图找到能被从 1 到 20 的所有数字整除的最小正数，代码如下:

$num = 2520;
$x = 1;

while($x < 21){
    if($num % $x == 0){
        $x++;
    }else{
        $num += 20;
        $x = 1;
    }
}

echo $num;

它在不到 1 分钟的时间内给出了正确的输出。这个执行时间在专业领域不好吗？有什么办法可以优化吗？

附言我从 2520 开始，因为它是可以除以 1 到 10 中的每个数字而没有余数的最小数字。

Answer 1

建议:找出[1,20]中所有整数的质数。

例如，我们有素数 {2,3,5,7,11,13,17,19}。所以，如果解是可分的由 [1,20] 中的所有整数，那么它肯定可以被此中的每个元素整除素数列表。所以，至少，我们的解决方案是 >= 2*3*5*7*11*13*17*19，对吗？

现在的问题是我们在构建候选解决方案方面能有多聪明大于那个数字。嗯，先看看解决了多少……

2*3*5*7*11*13*17*19能被4整除吗？不，所以，让我们乘以 2 得到2*2*3*5*7*11*13*17*19，肯定能被2*2整除...

2*2*3*5*7*11*13*17*19能被6整除吗？是的。

2*2*3*5*7*11*13*17*19能被8整除吗？ ....

你明白了。虽然我不确定，但我相信这种方法会得出正确答案——即能被每个整数整除的最小整数[1,20] 中的整数。