The well-known problem is acquiring a cardinality of the set of distinct numbers in the multiplication table n x m.
The very problem has been discussed in-depth and, as such, I require no further input on it by itself. There has been, however, a significant amount of debate about it on StackOverflow, namely this question:
and this question/bounty:
As far as I understand, the problem has currently only O(n^2) computational solutions (strictly speaking, k*n^2 iterations, with k=0.5), while the asymptotic size of the set is equal to $$\left|\lbrace a\cdot b:\ a,b\leq N\rbrace\right|\asymp \frac{N^2}{(\log N)^c(\log\log N)^{3/2}}$$ where $$c=1-\frac{(1+\log \log 2)}{\log 2}.$$ (Ford, 2008).
As far as my knowledge goes, there is no explicit way to generate a set of size A(n) and to calculate it's cardinality without at least A(n) operations. Also, there currently exists no solution to acquiring the exact value of A(n) without generating the set and counting its unique elements.
There has been significant amount of dispute about it by certain individuals, convinced there is an O(n) solution to the problem [calculating A(n)], and that they have found it. Although such solutions are usually disproven, I'm interested if it's at all possible for this problem to be solved strictly below O(n^2), either with explicitly generating the set or using some functional relationship between n and A(n). Currently, both the reference solutions and the one sent by David are O(n^2).
[edit] for clarity, let us split this into two questions: a) can exact A(n) for a specific n be actually calculated without generating the set itself (i.e. without any need to know and possibly without any method to tell if a number is in the set, or not) - and if so, how? If not, possible reasons for practical/theoretical possibility/impossibility of creating such solution would be perfect, b) can A(n) be computed by generating the set in strictly below O(n^2) complexity (e.g. O(n^2/log log N) or similar)? If so, how would that be possible?
related:
How many different numbers can be obtained as product of first $n$ natural numbers?
Distinct numbers in multiplication table
Number of elements in the set $\{1,\cdots,n\}\cdot\{1,\cdots,n\}$
