标签: greatest-common-divisor

我的LCM计划结果出错了.

如果找到数字的gcd,然后用gcd划分产品.

int gcd(int x, int y)
{
  while(y != 0)
  {
    int save = y;
    y = x % y;
    x = save;
  }
  return y;
}

int lcm(int x, int y)
{
  int prod = x * y;
  int Gcd = gcd(x,y);
  int lcm = prod / Gcd;

  return lcm;
}

任何帮助非常感谢.

所以我写了

function gcd(a, b)
  if b <> 0
    gcd (b, a % b)
  else
    return a

print gcd (12, 9)

所以它会:

1. gcd(12,9)
2. 9 <> 0表示TRUE
3. gcd(9,12%9 = 3)
4. 3 <> 0表示TRUE
5. gcd(3,9%3 = 0)
6. 0 <> 0表示FALSE
7. 返回a为3,但不返回任何内容

你能帮我找到我的错吗？

根据维基百科(http://en.wikipedia.org/wiki/Binary_GCD_algorithm),我试图为bignums编写二进制GCD(最多5000个数字).

我的GCD本身看起来像这样:

bitset<N> gcd(bitset<N> u, bitset<N> v) {
    bitset<N> one (string("1"));
    bitset<N> zero (string("0"));

    int shift;

    if (u == 0) return v;
    if (v == 0) return u;

    for (shift = 0; ((u | v) & one) == zero; ++shift) {
        u >>= 1;
        v >>= 1;
    }

    while ((u & one) == zero) u >>= 1;

    do {
        while ((v & one) == zero) v >>= 1;

        if (u.to_string() > v.to_string()) {
            bitset<N> t = v;
            v …

我使用的公式是“两个数的乘积等于它们的 GCD 和 LCM 的乘积”。

这是我的代码：

# Uses python3

import sys

def hcf(x, y):

    while(y):
        x, y = y, x % y

    return x

a,b = map(int,sys.stdin.readline().split())

res=int(((a*b)/hcf(a,b)))
print(res)

它适用于小数字。但是当我输入时：

输入：226553150 1023473145

我的输出：46374212988031352

正确输出：46374212988031350

谁能告诉我我哪里错了？

我刚刚在网上找到了这段代码,它可以计算2个数字的最大公约数.它是如何工作的？

int gcd(int a, int b){
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}

我有一个大小为 n 的数组。我需要找到具有给定数字的每个元素的 GCD，如果它大于 1，则将其添加到另一个数组中。这样做的最快方法是什么？

理解该算法如何找到 GCD 的直观方法是什么？