algorithm - 我如何通过以最小步长增加每个数字来使整数数组都相对质数？

Question

如何通过以最小步长增加每个数字来使整数数组都互质？

到目前为止，我想出了这样的策略:1)除以它们的公倍数(比如k，然后我执行的每一步都等于k)2)增加“最接近”素数的数字但是，我不确定这个策略的正确性。有人有更好的主意吗？

例如，a[5]={2,4,6,7,8}解决方案应该是 {2,5,9,7,11} 7 步。

Answer 1

您可以对所有整数 n 使用 gcd(n, n+1) = 1。因此，一种可能的策略是取绝对差值最小的两个数，并使较小的等于 the_value_of_the_bigger_one - 1。

顺便说一句，我认为你的第二个策略是不正确的。假设下一个素数是 p。然后你可以构造一个数组，其中所有数字(除此之外，你正在增加的数字)都可以将 p 作为因子。当你增加它时，数组的 gcd 将等于 p。示例数组可以是 (24, 2, 48) -- 当前 gcd 为 2，但是当您尝试第二个策略时，数组将变为 (24, 3, 48)，其 gcd 等于 3。