Most Divisors | Algorithm Notes

Most Divisors | Algorithm Notes
Given an integer $n$, you are asked to find an integer less than $n$ with most divisors. The least such number is asked to be return.
Divisors has two types: prime or not prime divisors. Total number of divisors is proportional to number of distinct divisors in $[1, \sqrt{n}]$. To solve this problem, at first we find as much as prime divisors less than $\sqrt{n}$. Then, based on this, we find as many as non prime divisors as possible.
To find prime divisors, we uses sieve methods. To pick as many as prime divisors possible, we apply greedy strategy. We always pick the most least $k$ prime divisors until the product of all these divisors is larger than $n$. Then we start to find non-prime divisors. As any muliple of a prime number won't be prime, so we can choose to multiply one of our prime divisors to produce more divisor less than $\sqrt(n)$. We keep multiplying until the product exceed $n$. Obviously, to be able to multiply as many times as possible, we need to muliple the least divisor. So greedy strategy again, we always pick multiple of $2$ as a non-prime divisor.

Read full article from Most Divisors | Algorithm Notes