最远互质算法

Question

给定一个包含 n 个数字的数组，用 [2, 250] 范围内最远的互质数替换每个元素。例如，2 的最远互质数是 249，243 的最远互质数是 2.

谁能帮我用最复杂的算法解决这个问题？

Answer 1

由于数量范围很小，我会选择一些筛法。

for (int i = 2; i <= N; ++i)
{
    if (N % i == 0)
    {
        sieve[i] = 1;
        for (int j = 2; j * i <= 250; ++j)
        {
            sieve[i * j] = 1;
        }
    }
}

使用它之后，您将寻找 sieve[sm] 为 0 的最小值 sm 以及 sieve[lg] 为 0 的最大值 lg。 然后从中得到距离N最大的那个。这就是你的答案。

Sieve 的复杂度为 O(nloglogn)。找到最远的循环将是 O(n)。所以整体复杂度是 O(nloglogn).

这背后的逻辑：

我们简单地标记了这个特定数字 N 的非互质值。

然后我们循环得到与给定数互质的最小和最大数。然后我们计算距离，然后取最大的作为答案。

Answer 2

对于距离[2, 250]范围最远的N的互质，候选者是：

• 如果 N 不能被 2 或 5 整除，则为 250。
• 249是候选人。它是质数，所以它肯定与 249 以下的所有数字互质。
• 最终候选数是 N 不能被其整除的第一个素数（例如，对于 N=240，该素数是 7）。从 2 到 250 的素数列表不需要在 运行 时计算，但可以拼写为数组初始化。

在这（最多）三个候选人中，选择离N最远的一个。