This is a well-known problem and is about counting the number of distinct numbers in the $n \times n$ multiplication table.

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:

As far as I understand, the problem has currently only $O(n^2)$ computational solutions (strictly speaking, $kn^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 its cardinality without at least $A(n)$ operations. Also, there currently exists no solution to determine 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

withoutgenerating 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\}$

is it possible for such an algorithm to exist- and if so,how would it have to work?; still, I've added a clarification to the question. $\endgroup$disprovethe existence of an $O((\log n)^c)$ (let alone $O(n)$) algorithm without earth-shaking advances in complexity theory. $\endgroup$7more comments