Distinct numbers in multiplication table Consider the multiplication table for the numbers $1,2,\dots, n$. How many different numbers are there? That is, how many different numbers of the form $ij$ with $1 \le i, j \le n$ are there?
I'm interested in a formula or an algorithm to calculate this number in time less than $O(n^2)$.
 A: Regarding the algorithmic question, a recent paper of Brent, Pomerance, Purdum, and Webster 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}$.
A: This is the multiplication table problem of Erdos. According to Kevin Ford, Integers with a divisor in 
$(y,2y]$, Anatomy of integers, 65-80, CRM Proc. Lecture Notes, 46, Amer Math Soc 2008, MR 2009i:11113, the number of positive integers $n\le x$, which can be written as $n=m_1m_2$, with each 
$m_i\le\sqrt x$, is bounded above and below by a constant times $x(\log x)^{-\delta}(\log\log x)^{-3/2}$, where  $\delta=1-(1+\log\log2)/\log2$. 
Erdos' work on this problem can be found (in Russian) in An asymptotic inequality in the theory of numbers, Vestnik Leningrad Univ. Mat. Mekh. i Astr. 13 (1960) 41-49. 
Another reference is http://oeis.org/A027424 where a PARI program is given. 
A: There's a beautiful lecture by Carl Pomerance in which he discusses Erdos's Multiplication Table Problem and then goes on to talk about dense product-free sets of integers. The talk was at the JMM in Boston in 2012. It's available at
https://math.dartmouth.edu/~carlp/sumproductboston.pdf
