问题标签 [greatest-common-divisor]

我发现很难计算二进制 GCD 算法（也称为 Stein 算法）的时间复杂度，该算法为 O(n^2)，其中 n 是两个数字中较大者的位数。不应该是 O(n) 吗？ 算法如下：

1.gcd(0, v) = v，因为一切都整除零，而v是整除v的最大数。同样，gcd(u, 0) = u。gcd(0, 0) 通常没有定义，但设置 gcd(0, 0) = 0 很方便。

2.如果u和v都是偶数，那么gcd(u, v) = 2·gcd(u/2, v/2)，因为2是公约数。

3.如果u是偶数，v是奇数，则gcd(u, v) = gcd(u/2, v)，因为2不是公约数。类似地，如果 u 是奇数而 v 是偶数，则 gcd(u, v) = gcd(u, v/2)。

4.如果 u 和 v 都是奇数，并且 u ≥ v，则 gcd(u, v) = gcd((u − v)/2, v)。如果两者都是奇数且 u < v，则 gcd(u, v) = gcd((v − u)/2, u)。这些是简单欧几里得算法的一个步骤的组合，该算法在每一步都使用减法，以及上述步骤 3 的应用。除以 2 得到一个整数，因为两个奇数的差是偶数。 [3]

5. 重复步骤 2-4 直到 u = v，或（多一步）直到 u = 0。在任何一种情况下，GCD 都是 2kv，其中 k 是在步骤 2 中找到的 2 的公因数的数量。

我必须在两个文本框中写入 2 个不同的数字，并用一个按钮计算 GCD，但是当我运行它时，该按钮什么也不做。

X 和 y 都是写在文本框中的数字，我使用 num1 和 num2 来保存 x 和 y 的值，以便 num1 越大，num2 越小。有任何想法吗？

是的。这是一个作业，老实说，这对我来说是一个脑筋急转弯。这个程序的目标，或“问题”（如果你想用数学术语来看待它）是将两个数字相除。您可以将整数和分数相除。函数定义如下所示：

c1, c2 - 整数

n1, n2 - 分子 1, 分子 2

d1，d2 - 分母 1，分母 2

result[ ] - 显示答案的字符数组

len - 结果中允许的字符数 []

我会简单地使用长除法并以这种方式找到我的答案，但由于存在不使用double、float或string的限制，我对我的方法的选择更加有限。

好消息是我距离最终解决方案还有很长的路要走，我想就我的下一步行动征求意见。到目前为止，这是我的过程：

1）将每个数字转换为假分数

2) 取结果 1 * (1 / 结果 2 )

3）找到解的整数部分（如果有的话）

4）（从假分数）拿分子%分母来找到我的混合分数的新分子

5）我现在在这里，试图为分母找到一个以 10 为底的倍数，这样我就可以用十进制格式表示混合分数。任何指针都会有帮助！

这解决了它。

您将列表附加到 dentemp ([s[x]])，然后尝试在这些列表上应用 int。（也许你应该去掉多余的 []） – hcwhsa 19 分钟前

我无法让我的列表成员能够用作数字来计算 getgcd 函数中的 gcd。

我现在得到的错误：

编码：

我正在处理python中处理有理数的问题，它有一种简化它的方法。例如12/8给出3/2. 我已经完成了这个问题并得到了正确的答案，但是我通过找到分子和分母的 gcd 来完成。当您说“Pythonic 方式！”时，可能有人帮助使用一些内置的特殊 python 特性或函数、模块或 python 独有的任何东西来完成它。

是否有这样的方法或应该包含任何测试用例来涵盖所有可能性？

这是我的代码：

当我运行程序时，它会给出答案并给出错误：

请帮助我消除错误并改进代码并使其更加pythonic！

好的，所以相对素数意味着两个数没有大于 1 的公因数。它也可以看作是 gcd = 1 的两个数。

因此，沿着这些思路，这是我编写的用于查找两个相对素数 e,z 的代码：

gcd 函数定义为：

当我设置时z = 60，我得到的 e 是e= 0 ......实际上我一直得到与初始化 for 循环相同的e

我究竟做错了什么？有没有其他方法可以判断两个数是否互质？

编辑：

好的，根据 minitech 的建议，这里是修改后的代码：

现在，当我设置 z=60 时，我的 e 变成了 e = 60，这又是错误的。正确答案应该是 e = 7

为什么这个程序不起作用？这是使用递归函数的简单最大公约数程序。它编译没有错误，但是当我运行 program.exe 时它只是崩溃：“程序已停止工作”。我已经在代码块和 Notepad++ 上尝试过。我使用 gcc 编译器。

我想在 python 中做一个最大的公约数计数器，但我不完全确定如何去做，或者从哪里开始......我所拥有的几乎就是这个等式（a 和 b 是数字）：

我希望计数器打印所有步骤，直到余数低于 a，然后显示 GCD。

我还搜索了更多内容，发现两个数字的商可以简单地用 // 命令完成，余数用 % 命令完成，所以基本上：

我也知道我需要一个计数器的循环，但我不知道如何去做...帮助将不胜感激。

我看过一些 GCD 代码，但找不到能显示所有步骤的代码。

我应该基本上生成3种不同的算法来查找GCD（a，b）。

其中一个是欧几里得的版本，所以我还需要两个。

实现是在 C# 中完成的。

建议？

我正在编写一个添加 2 个分数的程序。我有 3 个课程：UI、Rechnen 和 RechnenTest。给出了 UI 和 RechnenTest 类，我必须编写 Rechnen 类来添加分数。问题是，程序运行良好，但 JUnit 测试失败。这些是类：

语言是德语。

谢谢