How can I make my algorithm more efficient or Is there a better way to solve the problem
Your attempt runs into a huge problem with the input [1, 2, $2^{63}$]. 

Either your numbers are so small that it doesn’t matter. Otherwise, you start with a solution, find its speed and why it is slow, and then iteratively improve it. That’s usually a much better method than hoping that someone does the work for you. 

For this specific problem, I think that for any algorithm you give someone will be able to come up with input that makes it behave badly. So I would try to find what are typical inputs and design a solution for those. 

With the given restrictions, if the numbers are unique, I’d probably turn the number into a bit array, so to find all multiples of k only max / k numbers need checking. If k is tiny, check the elements of the original array. If k = 1 return the number of array elements. And cache the results. 

For example to count the multiples of 1,234 you’d check if bits 1,234, 2,468, 3,702 etc are set which would be 800 checks or so. If large numbers are allowed the solution would be awful.