如何计算多个数字的最小公倍数？
到目前为止,我只能在两个数字之间进行计算.但不知道如何扩展它来计算3个或更多数字.
到目前为止,这就是我做到的
LCM = num1 * num2 / gcd ( num1 , num2 )
使用gcd是计算数字的最大公约数的函数.使用欧几里得算法
但我无法弄清楚如何计算3个或更多数字.
在一组数字上计算最大公约数和最小公倍数的最简单方法是什么？可以使用哪些数学函数来查找此信息？
是否有C++算法来计算多个数字的最小公倍数,如lcm(3,6,12)或lcm(5,7,9,12)？
今天我读了一篇有趣的DailyWTF帖子,"Out of All the Possible Answers ...",我对它感兴趣,足以挖掘提交它的原始论坛帖子.这让我想到如何解决这个有趣的问题 - 最初的问题是在Project Euler上提出的:
2520是可以除以1到10中的每个数字而没有任何余数的最小数字.
可以被1到20的所有数字整除的最小数字是多少？
要将此作为一个编程问题进行改革,您将如何创建一个能够为任意数字列表找到最小公倍数的函数？
尽管我对编程很感兴趣,但我对纯数学的表现非常糟糕,但是我可以通过一些谷歌搜索和一些实验来解决这个问题.我很好奇SO用户可能采取的其他方法.如果你这么倾向,请在下面发布一些代码,希望还有一个解释.请注意,虽然我确定存在用于以各种语言计算GCD和LCM的库,但我更感兴趣的是比调用库函数更直接地显示逻辑的东西:-)
我最熟悉Python,C,C++和Perl,但您喜欢的任何语言都是受欢迎的.奖励积分,用于解释像我一样的其他数学挑战的人的逻辑.
编辑:提交后我确实发现这个类似的问题3个或更多数字的最小公倍数,但它回答了我已经想出的相同的基本代码,并没有真正的解释,所以我觉得这是不同的,足以让我们开放.
我有当前的编码,曾经是一个goto但我被告知不再使用goto,因为它不赞成.我有麻烦改变它说一段时间循环.我对C#和一般编程都很陌生,所以这对我来说是一些全新的东西.任何帮助,将不胜感激.实际问题是输入两个数字并找到最低的公倍数.
这是带goto的原文:
BOB:
if (b < d)
{
a++;
myInt = myInt * a;
b = myInt;
myInt = myInt / a;
if (b % myInt2 == 0)
{
Console.Write("{0} ", h);
Console.ReadLine();
}
}
if (d < b)
{
c++;
myInt2 = myInt2 * c;
d = myInt2;
myInt2 = myInt2 / c;
if (d % myInt == 0)
{
Console.Write("{0} ", t);
Console.ReadLine();
}
else
{
goto BOB;
}
}
else
{
goto BOB;
}
}
我环顾四周,找到了其他有问题的答案,但没有一个问题涉及这个问题的范围.包括这个问题,还有这个问题.
我必须以有效的方式计算大范围数字的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 …我正在尝试解决在线判断问题:http://opc.iarcs.org.in/index.php/problems/LEAFEAT
问题简而言之:
如果我们给出一个整数L和一组N个整数s1,s2,s3..sN,我们必须找到从0到L-1的数字,它们不能被任何'si'整除.
例如,如果我们得到, L = 20和S = {3,2,5}然后有6个号码从0到19,其不被整除3,2或5.
L <= 1000000000且N <= 20.
我使用包含 - 排除原则来解决这个问题:
/*Let 'T' be the number of integers that are divisible by any of the 'si's in the
given range*/
for i in range 1 to N
for all subsets A of length i
if i is odd then:
T += 1 + (L-1)/lcm(all the elements of A)
else
T -= 1 + (L-1)/lcm(all the elements of A) …以下关系仅适用于两个(3,12)数字,当用于三个数字(3,12,10)时,它无法产生正确的答案.只是想知道它是我的理解还是只是两个数字,对我来说同样适用于Euclid算法.
LCM(a, b) = (a x b) / GCD(a,b) or GCD(a,b) = (a x b) / LCM(a, b)
如何以最快的方式找到{1,2,...,n}的LCM,其中0 < n < 10001.一种方法是计算n!/ gcd(1,2,.....,n)但这可能很慢,因为测试用例的数量是t <501,输出应该是LCM(n!)%1000000007
代码相同的是:
#include<bits/stdc++.h>
using namespace std;
#define p 1000000007;
int fact[10001] = {1};
int gcd[10001] = {1};
int main()
{
int i, j;
for( i = 2;i < 10001; i++){
fact[i] = ( i * fact[i-1]) % p;
}
for(i=2 ;i < 10001; i++){
gcd[i] =__gcd( gcd[i-1], i );
}
int t;
cin >> t;
while( t-- ) …int lcm_old(int a, int b) {
int n;
for(n=1;;n++)
if(n%a == 0 && n%b == 0)
return n;
}
int lcm(int a,int b) {
int n = 0;
__asm {
lstart:
inc n;
mov eax, n;
mov edx, 0;
idiv a;
mov eax, 0;
cmp eax, edx;
jne lstart;
mov eax, n;
mov edx, 0;
idiv b;
mov eax, 0;
cmp eax, edx;
jnz lstart;
}
return n;
}
我试图用我自己的函数(底部)击败/匹配顶部函数的代码.您有什么想法可以优化我的日常工作吗？
PS.这只是为了好玩.