在质数的排序数组中，arr 找到 arr 中最小数的索引 i，使得 arr[i] 除以给定数-解网

问：

考虑以下数据：
arr = [2,3,5,7,11,13,17,19] n = 100
给定的输出应为 0，因为 n % 2 = 0 且 arr[0]
= 2。

由于数组是排序的，我想利用这一点来发挥我的优势，并设计一种可以在小于 O（n）的复杂度下工作的算法，您可以通过遍历整个数组并首先找到 i 使得 n % arr[i] = 0。

我立即想到使用修改后的二叉搜索，其复杂性与常规二叉搜索（O（logN））相同，它与常规二叉搜索相同，后者在每次迭代中将搜索间隔分成两半，并稍作修改。这是我使用的实现：

public int SmallestFactorIndex(int n)
{
    int left = 0;
    int right = max;
    int index = -1;

    while (left <= right)
    {
        int middle = (right - left) / 2 + left;
        int middleValue = sieve[middle];

        if (n % middleValue == 0)
        {
            index = middle;
            right = middle - 1;
        }
        else if (middleValue < n)
        {
            left = middle + 1;
        }
        else
        {
            right = middle - 1;
        }
    }

    return index;
}

Max 表示数组的长度 - 1，sieve 是质数的排序数组。对二进制搜索的唯一补充是，如果当前数字确实除以 n，我不会立即返回该索引，而是通过将右边框移动到中间边框来继续搜索比当前数字更小的数字。所有其他部分的工作方式几乎相同。我不认为我能利用数组只由素数组成的事实，但我可能是错的。

C# 数组算法素

当数据被预分类时，这非常有效（是的），并且可以知道一个项目（它自己！）以明确解决查询。这就是我们的麻烦。如果是 286 （2 x 11 x 13），那么 2、11 和 13 中的任何一个都是潜在的解决方案，通过二进制搜索登陆其中任何一个都不会告诉我们，直到我们完全完成搜索......我们仍然需要检查一切。n

抽象到一般情况，这表明对数组进行简单的二进制搜索本身是不够的，因为仅仅找到 A 解决方案并不能停止对 THE 解决方案的搜索。

但是，如果我们提前知道结果，它就可以起作用。也就是说，如果我们能求解在 O（log n）时间内找到最小的质因数（无论索引如何）——如果我们知道我们要寻找的值是 2，而不是 11 或 13——那么我们也可以在 O（log n）时间内搜索数组，并且 O（log n）加 O（log n）仍然是 O（log n）。

如果我们看一下输入，完全分解一个数字绝对不是O（log n）——众所周知，许多重要的加密算法都依赖于这一点，这要糟糕得多。

但我们不需要完全考虑这个数字。我们只需要第一个（最小的）素数。这显然可以做得更好一点......但它足够好吗？不幸的是，我认为答案仍然是“不”。

阅读快速复习，我认为我们很可能可以击败平均/典型情况的线性时间，甚至一路到 O（sqrt n）找到第一个素数。O（sqrt n₀） + O（log n₁）仍然是 O（sqrt n），但至少它仍然（表面上）比 O（n）好。

但这就是事情变得有点棘手的地方。现在，我们还必须担心将输入变量中的“n”与素数数组的“n”分开。当我们这样做时，我们意识到输入变量涉及的“n”是达到该值的每个整数，而不仅仅是预先计算的素数数组的（小得多的）长度。

因此，对于大约一百万左右的典型输入（这个数字完全是一个猜测，但你可以编写一些代码来验证和完善它），线性搜索可能是你能做的最好的。n

说到编写代码来预验证输入，这就引出了下一个选项：

O（1）

如果可以在可能的输入数据上放置某种合理的边界，那么完全预先计算每个候选整数的结果并将这些值放入 O（1）字典中并非不可能。即使是 100 万个候选者也只需要大约 8 MB 的 RAM，突然之间，现在每个输入只需要字典查找。

@NikolaSavić 在我回答的末尾，关于数据性质的观点值得强调，所以我将使用它的反面来重申：如果数据确实是未知的或随机的，并且包含大量数字，那么你可以通过预先分解你的输入来找到最小的质因数来做得更好。否则，知道你已经有一个预先计算的素数数组，你最好只是迭代这个数组......如果索引（而不是值）确实是你所追求的。SQRT(integer.MaxValue)

0赞 Dmitry Bychenko 10/26/2023

从技术上讲，这是一个悬而未决的问题：我们不知道任何算法在对数时间内返回质因数（我们也没有证据证明这种算法不存在）。希望能够找到快速算法：我们能够使用对数时间（AKS 素数测试）检查是否为素数，这可能是最后一步 - 因子也可以是对数。n

1赞 harold 10/26/2023 #2

设计一种可以在小于 O（n）的复杂度下工作的算法

好消息是，如果不是素数，那么线性遍历列表已经只是一个 O（sqrt（n））算法：合数的最小因子不能大于它的平方根。对于普通的旧设备来说，这还不错（但以这种方式分解 RSA 密钥没有希望）。nint

对于素数，当你到达一个大于的平方根的数字时，你可以缩短线性搜索（所以到目前为止这仍然是 O（sqrt（n）），现在你实际上可以使用二进制搜索来找到它的索引（这必须是此时要除以的最低素数，由于我们刚刚证明了这是素数），如果它在列表中。nnnnn

使用 PNT，我认为我们甚至可以争辩说，线性地遍历该素数列表直到找到最低质因数的时间复杂度为 O（sqrt（n） / log（n））。除以 log（n）来自素数的密度随着增加而“变薄”（因此，与迭代整数相比，我们可以通过仅迭代素数来更快地达到渐近的平方根，就像我们在这里所做的那样）。nn

1赞 Dmitry Bychenko 10/26/2023 #3

好吧，如果除以，那么最多是：在最坏的情况下.让我们检查质数，最多：pnpsqrt(n)n = p * psqrt(n)

public int SmallestFactorIndex(int n) {
  int result = -1;

  for (int i = 0; i < arr.Length; ++i) {
    int d = arr[i];
  
    (int q, int r) = Math.DivRem(n, d);

    if (r == 0)
       return i;
    if (q <= d)
       return -1;
  }

  return result; 
}

到目前为止，我们有时间复杂度，这比 .我们可以用更精细的算法来改善，例如波拉德的rho，它有时间复杂度，但这里仍然没有对数。对于对数时间，只能检查是否为质数（AKS 测试），但找不到质因数。O(sqrt(n))O(n)O(sqrt(sqrt(n))) = O(n^1/4)n

在质数的排序数组中，arr 找到 arr 中最小数的索引 i，使得 arr[i] 除以给定数

In a sorted array of prime numbers arr find index i of the smallest number in arr such that arr[i] divides given number

评论

O（1）

评论

评论