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

Question

Consider the following data:
arr = [2,3,5,7,11,13,17,19]
n = 100
Output of the given should be 0 since n % 2 = 0 and arr[0] = 2.

Since array is sorted I want to use that to my advantage and design an algorithm that can work in a complexity smaller than O(n), which you have by iterating over the whole array and finding first i such that n % arr[i] = 0.

I instantly thought of using modified Binary Search with the same complexity as the regular Binary Search(O(logN)), which does the same as a regular Binary Search which divides the search interval in half in each iteration with slight modification. Here is the implementation i used:

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 represents length of the array - 1 and sieve is the sorted array of prime numbers. Only addition to the Binary Search is that if the current number does divide n, I dont instantly return that index but continue searching for a smaller number than that current number by moving the right border to the middle one. All other parts work pretty much the same way. I dont think I can take advantage of the fact that the array only consists of the prime numbers but I might be wrong.

"an algorithm that can work in a complexity smaller than O(n)" why? If you need to manipulate the list into another format (such as a binary tree), that's going to be an O(n) operation, offsetting any advantage you get from another iteration method. — gunr2171
– gunr2171, Commented Oct 25, 2023 at 16:12
I think the fastest way is simply to iterate the list in ascending order until you find a divisor. — Olivier Jacot-Descombes
– Olivier Jacot-Descombes, Commented Oct 25, 2023 at 16:20
@gunr2171 I have several queries so i want to make this a log(N) operation — Nikola Savić
– Nikola Savić, Commented Oct 25, 2023 at 17:10

Joel Coehoorn · Accepted Answer · 2023-10-26 18:42:49Z

3

i want to make this a log(N) operation

O(log n) is commonly associated with a binary algorithm: you split the data set at some midpoint; based on this midpoint you then decide which half to keep and which to discard, and repeat with the kept half until you zero in on the result.

This works great when the data is presorted (it is, yay) and an item can be known (on it's own!) to definitely solve the query. And there's our trouble. If n is, say, 286 (2 x 11 x 13), then any of 2, 11, and 13 are potential solutions, and landing on any of them via binary search doesn't tell us we're done until we fully complete the search... we still have to check everything.

Abstracting to the general case, this suggests a simple binary search on the array is not good enough by itself, because simply finding A solution doesn't stop the search for THE solution.

But it can work if we know the result in advance. That is, if we can solve to find the smallest prime factor (regardless of index) in O(log n) time — if we know the value we're looking for is the 2, instead of the 11 or the 13 — we can then also search the array in O(log n) time, and O(log n) plus O(log n) is still O(log n).

If we look at the input, fully factoring a number is definitely NOT O(log n) -- famously so, to the point a number of important cryptographic algorithms rely on this being much worse.

But we don't need to fully factor the number. We only need the first (smallest) prime. This can obviously do a little better... but is it good enough? And unfortunately, I think the answer is still, "no".

Reading a quick refresher, I think it's likely we can beat linear time for the average/typical case, and even make it all the way to O(sqrt n) to find the first prime. O(sqrt n₀) + O(log n₁) is still O(sqrt n), but at least it's still better (on the surface) than O(n).

But this is where things get a little tricky. Now we also have to worry about keeping the "n" from the input variable separate from the "n" for the primes array. When we do that, we realize the "n" for the input variable involves is every integer up to that value, rather than just the (much smaller) length of the pre-computed primes array.

Therefore, for typical n inputs up to about a million or so (and that number is a complete guess, but you could write some code to validate and refine it), the linear search is likely the best you can do.

Speaking of writing code to pre-validate inputs, this brings up the next option:

O(1)

If you can put some kind of reasonable boundary on the possible input data, it's not out of the question to fully pre-compute the results for every candidate integer and put those values into a O(1) dictionary. Even a million candidates would only take about 8 MB RAM, and suddenly now every input only requires a dictionary lookup.

edited Oct 26, 2023 at 18:42

answered Oct 25, 2023 at 17:34

Joel Coehoorn

418k114 gold badges582 silver badges820 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Nikola Savić Over a year ago

So no matter the data structure I use i cant achieve anything less than O(N)? The problem is I have several queries so I made a sieve of Erathostenes so I specified that I have sorted array of prime numbers thinking these two factors could help someone come up with a solution.

Joel Coehoorn Over a year ago

@NikolaSavić The point at the end of my answer about the nature of the data is worth reinforcing, so I'll restate using its inverse: if the data is truly unknown or random and includes large numbers, you MAY do better by pre-factoring your inputs to find the smallest prime factor. Otherwise, knowing you already have a pre-computed a prime array up to SQRT(integer.MaxValue), you're probably better off just iterating the array... if the index (rather than the value) is indeed what you're after.

Dmitrii Bychenko Over a year ago

Technically, it's an open question: we don't know any algorithms which return a prime factor in a logarithm time (and we don't have a proof that such algorithm doesn't exist). There's a hope that the fast algorithm can be found: we are able to check if n is prime or not with logarithmic time (AKS primality test), may be the last step - a factor can be logarithmic as well.

user555045 · Accepted Answer · 2023-10-25 17:50:43Z

design an algorithm that can work in a complexity smaller than O(n)

The good news is that if n is not prime, then linearly going through the list is already only an O(sqrt(n)) algorithm: the smallest factor of a composite number cannot be larger than its square root. For a plain old int that's not too bad (but there's no hope of factoring an RSA key that way).

For an n that is prime, you can cut the linear search short when you reach a number larger than the square root of n (so this is still O(sqrt(n)) so far) and now you actually can use binary search to find the index of n itself (which must be the lowest prime to divide n at this point, since we just proved that n is prime), if it is in the list.

Using the PNT, I think we could even argue that the time complexity of linearly going through that list of primes until we find the lowest prime factor is O(sqrt(n) / log(n)). The division by log(n) comes from the density of primes "thinning out" as n increases (so we can reach the square root of n asymptotically faster by iterating only over the primes, as we do here, compared to iterating over the integers).

Dmitrii Bychenko · Accepted Answer · 2023-10-26 08:16:40Z

1

Well, if p divides n then p is at most sqrt(n): in the worst case n = p * p. Let's check prime numbers up to sqrt(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; 
}

So far so good we have O(sqrt(n)) time complexity which is better than O(n). We can be better off with more elaborated algorithms e.g. Pollard's rho which has O(sqrt(sqrt(n))) = O(n^1/4) time complexity, but still no logarithms here. For logarithm time you can only check if n prime or not (AKS test), but not find a prime factor.

edited Oct 26, 2023 at 8:16

answered Oct 25, 2023 at 18:05

Dmitrii Bychenko

188k20 gold badges178 silver badges231 bronze badges

1 Comment

Joel Coehoorn Over a year ago

Be careful not to conflate the n from the input variable with the n of the pre-computed primes array. We can certainly get to O(sqrt n) for the former, but then the n is potentially every positive integer, where with the latter is only the length of the array.

Collectives™ on Stack Overflow

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

3 Answers 3

O(1)

3 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

O(1)

3 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related