Closest divisors in array
No, probably not, if you care about theoretical worst-case running time.  The problem is as hard as the subset containment problem: given sets $S_1,\dots,S_n$, check whether there exists sets $S_i,S_j$ such that $S_i \subset S_j$.  It's known that there is no algorithm with $O(n^{2-\epsilon})$ running time, assuming the SETH conjecture is true.  Thus, any faster algorithm would imply a disproof of SETH, which is a famous open problem -- so you shouldn't expect any easy algorithm that does significantly better than $O(n^2)$ in worst-case running time.  (I don't count a $\log n$ factor speedup as significant.)  See https://cstheory.stackexchange.com/q/9896/5038.

If you only care about the "average case" it might be possible to do better.  The answer might also depend on the model of computation and the size of the integers, so it's possible there might be some choice of those that lets you evade this hardness result.



For instance, if your numbers are "random" in a particular specific way, you can use a divide-and-conquer algorithm.  First recursively solve the problem for $A[1..n/2]$, and recursively solve the problem for $A[n/2+1..n]$.  Then for each $i \le n/2$ such that $B[i]=-1$, we'll find the smallest $j &gt; n/2$ such that $A[j]$ divides $A[i]$ and overwrite $B[i]$ with $j$.  Suppose we can do that last step in $U(n)$ time.  Then the total running time will satisfy the recurrence $T(n) = 2 T(n/2) + U(n)$, i.e., $T(n) = O(U(n) \log n)$.

OK.  So how will we do that last step?   We'll solve that problem in turn using a separate divide-and-conquer algorithm.  Pick a prime number $p$ that hasn't been picked yet, and construct the sets $S^0 = \{i : p \not| A[i], i \le n/2\}$, $S^1 = \{i : p | A[i], i \le n/2\}$, $T^0 = \{i : p \not| A[i], i &gt; n/2\}$, $T^1 = \{i : p | A[i], i &gt; n/2\}$.  Now for each $i \in S^0$, find the smallest $j \in T^0$ such that $A[j]$ divides $A[i]$; and for each $i \in S^1$, find the smallest $j \in T^0$ such that $A[j]$ divides $A[i]$ (or, equivalently, such that $A[j]$ divides $A[i]/p$), and find the smallest $j \in T^1$ such that $A[j]$ divides $A[i]$ (or, equivalently, such that $A[j]/p$ divides $A[i]/p$).  Those are three subproblems each of size $n/2$ (heuristically, assuming the numbers are random and half are divisible by $p$ and half aren't), and then you can combine them to get a solution to the original problem in $O(n)$ time, so the total running time to do this last step is $U(n) = 3 U(n/2) + O(n)$, which solves to $U(n) = O(n^{\lg 3}) = O(n^{1.585})$.

So, heuristically the total running time of this approach is $O(n^{1.585} \log n)$ under a particular assumption on the distribution of the numbers.