问题标签 [greatest-common-divisor]

我正在尝试做一个获取数字列表的练习，并显示如下元素列表：如果 A=[a0,a1,a2] 那么有 U=[u0,u1,u2]，知道 a0 *u0 + a1*u1 + a2*u2 = d 并且 d 是 A 的 gcd。

对于 2 个元素是一件非常简单的事情，因为 Sage 具有从 a0 和 a1 中检索 u0 和 u1 的功能：

我只是不明白我怎么能用 n 个元素的列表来做到这一点。

我正在尝试创建一个最大公约数计算器。我必须为这个项目创建一个 GUI 界面，我认为我这样做是正确的，但是我无法测试它，因为我的计算有问题。

具体来说，我在编译器中遇到以下两行错误：

错误是“类型不匹配，无法从 String 转换为 int”我尝试插入 int x = 0; 和 int x = 0; 在它之前没有运气。我也尝试过将这些从整数更改为字符串，但它会使一切变得更加混乱。我不确定如何获取我应该使用的文本。

这是我的代码的计算部分：

这是我的整个代码：

我必须确保 3 个数字之间的 GCD 不大于 1。

这是我到目前为止的方法代码：

当return 1我开始在实验室工作时，它就已经在那里了。如何确保 GCD 不超过 1？并返回所有三个整数？

如果它有助于弄清楚需要做什么，这是代码的其余部分：

更新

这是我为同一个实验室编写的新代码：

这是问题：

“编写一个名为 gcd 的方法，它接受两个整数作为参数并返回两个数的最大公约数。两个整数 a 和 b 的最大公约数 (GCD) 是作为 a 和 b 的因子的最大整数。任意数加 1 的 GCD 为 1，任意数加 0 的 GCD 为该数。

计算两个数字的 GCD 的一种有效方法是使用 Euclid 算法，该算法说明如下：

我真的很困惑如何解决这个问题。我只是想要一些提示和提示，说明我在迄今为止的程序中做错了什么。（我必须放入扫描仪，这是我老师的要求。）不要给我完整的代码，因为我有点想自己解决这个问题。也许只是给我一个提示，说明我如何合并您在上面看到的这个公式。（如果你想知道为什么我输入 == 0，那是因为我认为如果你有两个数字，比如 0 和 90，它们的 GCD 应该是 0 对吧？？）

此外，我的代码必须包含 while 循环......我更喜欢 if 循环......

提前致谢！:)

我目前的程序：

我无法编译我的代码，特别是在我调用“gcd();”的主程序中 我应该把什么放在括号里？谢谢你。

根据维基百科（http://en.wikipedia.org/wiki/Binary_GCD_algorithm），我试图为 bignums（最多 5000 位）编写二进制 GCD。

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

我也在使用自己的位集减法函数：

我没有看到任何地方可以提高这个算法的速度（二进制 GCD 本身很快），但我收到反馈说我的程序太慢了。

我已经有一个函数可以找到 2 个数字的 GCD。

但是现在，我想扩展这个函数来找到 N 个点的 GCD。有什么建议吗？

我正在用c实现一个非常简单的计算机代数系统。我的程序在一段时间后崩溃时遇到了一些问题。

这个想法是有一个像 3^(21+8^(3^100)) + 4 这样的表达式，并看到它等于 2 mod 7。我已经用 java 编写了程序，并试图将它移植到 c。

我就是这样做的：我有一个名为 expr 的结构。它可以是二进制表达式或原子 int

我怀疑（其中一个）问题是我没有在 gcd 函数中释放内存。这就是我编写 gcd 函数的方式。

这在java中很好用，但我不确定它是否在c中有效，因为它没有自动垃圾收集。当函数是递归的时，我不确定如何构造它。所以我想我的问题是，我应该把 free_expr 函数放在哪里？mod(a, b) 分配一个新的 expr 结构，因此它最终会创建很多永远不会被释放的 expr。我怀疑这可能是它崩溃的原因。构建这个的正确方法是什么？还是我做错了？

由于代码可维护性，我宁愿在 struct expr 中进行计算，而不是在 int 中进行计算。

谢谢你的帮助。

[编辑] 这是我的模组功能

}

phi(n) 计算欧拉函数。

[编辑 2] 这是我的平等

我编写了以下函数来计算浮点数的 GCD，但是当我为输入 (111.6, 46.5) 运行此函数时，函数中 fmod(a,b) 的计算在 2 次递归调用后开始给出错误的结果。我在这里找不到错误。谁能找到这里出了什么问题？

}

我有一个关于 GNU MP 的问题，请你帮我解决这个问题。我在 Windows 上使用“GNU 多精度算术库”5.1.1 版。(MinGW\gcc + MSYS)

存在一个 mpz_gcd 函数来计算两个整数的“gcd”。

据我从文档中得到的，在 GNU MP 中实现了几种算法，用于计算最大公约数。其中：

• 二进制 GCD
• Lehmer 算法
• 次二次 GCD

使用的算法似乎是根据整数的输入大小自动选择的。

目前，二进制算法仅在 N < 3 时用于 GCD。

对于大于 GCD_DC_THRESHOLD 的输入，通过 HGCD（Half GCD）函数计算 GCD，作为对 Lehmer 算法的推广。

所以，我想至少有三种不同的方法可以得到 gcd(a, b)。我的主要问题：我想自己指定使用哪种算法。我将比较这些算法在随机大输入（即 10^5 位）上的执行时间，以找出一些常见趋势：使用“二进制 GCD”变得比“Lehmer 方法”更差的点是“HGCD-Lehmer”泛化”确实比直接的 Lehmer 等要好。

有没有简单的方法来指定您要使用的算法？从库中提取此算法的任何方式，修改某些“#define”变量的任何方式。是否可以在不重新编译库的情况下做我想做的事情？我只是那里的初学者，我觉得无法弄清楚图书馆里的所有东西。

PS 可能有人会对此感兴趣。我在 github 上有一些代码：https ://github.com/int000h/gcd_gcc