Regarding the algorithmic question, a recent paper of [Brent, Pomerance, Purdum, and Webster][1] presents a subquadratic algorithm to compute the number of distinct products $M(n)$ of the $n \times n$ multiplication table.  They have implemented their results to compute $M(n)$ exactly for all $n \leq 2^{30}$.  They note that for larger values of $n$, exact algorithms become impractical, and so the paper also presents two Monte Carlo algorithms to approximate $M(n)$. Monte Carlo computations are presented for $n$ up to $2^{100000000}$.  


  [1]: https://arxiv.org/abs/1908.04251