如何计算多个数字的最小公倍数？
到目前为止,我只能在两个数字之间进行计算.但不知道如何扩展它来计算3个或更多数字.
到目前为止,这就是我做到的
LCM = num1 * num2 / gcd ( num1 , num2 )
使用gcd是计算数字的最大公约数的函数.使用欧几里得算法
但我无法弄清楚如何计算3个或更多数字.
我环顾四周,找到了其他有问题的答案,但没有一个问题涉及这个问题的范围.包括这个问题,还有这个问题.
我必须以有效的方式计算大范围数字的LCM.我对其他问题看起来并不太深入,因为它们没有处理与此算法必须处理的数字范围一样大的数字范围.
我现在得到的代码可以在大约90秒内计算1到350000之间的每个数字的最小值.(结果数字是大约76000十进制数字).我希望最终能够在数百万甚至数十亿元素的范围内扩展它.
它最终可能会被瘫痪.对于某些算法,这根本不会很难,对于其他算法,它会更棘手(例如,如果算法使用当前生成的LCM来计算其计算的其他部分的素数)
这里是:
public static BigInteger getLCMOfRange(BigInteger lower, BigInteger upper)
{
BigInteger M = BigInteger.ONE;
BigInteger t;
// long l = System.currentTimeMillis();
// System.out.println("Calculating LCM of numbers up to " + upper + "...");
for (; lower.compareTo(upper) != 1; lower = lower.add(BigInteger.ONE))
{
t = M.gcd(lower);
if (t.compareTo(lower) == 0)
continue;
M = M.multiply(lower).divide(t);
}
// System.out.println("Done. Took " + (System.currentTimeMillis() - l) + " milliseconds. LCM is " + M.bitCount()+ " bits …还有另一个最近的Project Euler问题,但我认为这有点具体(我只对基于PHP的解决方案感兴趣)所以我还是要问.
问题#5的任务是:"从1到20的所有数字均可被整除的最小数字是多少？"
现在,我已经解决了两次.曾经非常低效,而且效率更高,但我仍然远离一个特别复杂的答案(我在数学上并不是特别坚固,因此我的蛮力解决方案).我可以看到几个方面我可以改进这一点,但我想知道你们中是否有人能够证明这个问题更有效的解决方案.
*扰流板:这是我不太理想(运行7秒)但仍然可以容忍的解决方案(不知道如何处理双$ ...只是假装你只看到1 ......
function euler5(){
$x = 20;
for ($y = 1; $y < 20; $y++) {
if (!($x%$y)) {
} else {
$x+=20;
$y = 1;
}
}echo $x;
};
我正在尝试解决下面详述的项目拼图.我当前的函数适用于数字1到10,但是当我尝试1到20时,它只是永远循环而没有结果.
2520是可以除以1到10中的每个数字而没有任何余数的最小数字.可以被1到20的所有数字整除的最小正数是多少？
def calculate():
results = dict()
target = 20
num_to_test = 1
while len(results) < target:
for j in range(1, target+1):
results[num_to_test] = True
if num_to_test % j != 0:
# current num_to_test failed in the 1-10, move on
del results[num_to_test]
break
num_to_test += 1
return min(results)
任何人都可以在逻辑中看到任何问题,特别是我想知道为什么它适用于10的目标,但不是20.谢谢