Since, you haven’t cleared you want uniqueness in divisors or not, also, there arises the case whether the divisors need to be prime or not. If you want only prime divisors and being unique is not required, then it can be
log2(max) since 2 is the smallest prime number. And if you want all unique prime divisors, then the maximum number I suppose will be
2*3*5*7*11... <=max i.e. number formed by product of all prime numbers till the product is less than the maximum allowed value.
If uniqueness is not the thing to work upon, then (nlogn) solution can work for you:
divisors[i*j]+=1; // this counts the number of divisors of the number i*j
// p= find maximum of all divisors*
// p is your answer then.
There’s also one more possibility the question may be asked which I can think of, you are given many queries of
(i,j) and you have to tell the answer of each one. In such a case, the complexity of the above way will come out to be
O(no_of_queries(nlogn)) which may not pass in the given time limit. We can do one more thing here for this case. Compute the answer for every number in the initial given range i.e. from 1 to 10^6. Now, build segment tree of the same with the internal nodes store the maximum number in the range of its childs which has maximum number of divisors. Then each query can be answered in
Will you please provide the link to the exact question.