<p><strong>Yes</strong>, there is a better algorithm, which runs in subquadratic time.  See this recent paper of <a href="https://arxiv.org/abs/1908.04251" rel="nofollow noreferrer">Brent, Pomerance, Purdum, and Webster</a>. Their algorithm also outputs all the values in the <strong>n</strong> x <strong>n</strong> multiplication table.  Note that the number of values is known to be subquadratic, due to a classic result of <a href="https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Tenenbaum%E2%80%93Ford_constant" rel="nofollow noreferrer">Erdős</a>.  The linked <a href="https://mathoverflow.net/questions/31663/distinct-numbers-in-multiplication-table/400593#400593">question</a> on MathOverflow has more information.</p>
Find the number of distinct numbers in multiplication table
<p>Inspired by <a href="https://mathoverflow.net/questions/31663/distinct-numbers-in-multiplication-table">this question on mathoverflow</a>  </p>

<p>Suppose I have a <strong>n</strong> x <strong>n</strong> multiplication table, what is the number of <strong>distinct values</strong> on it?</p>

<p>For example, a 3X3 multiplication table  </p>

<p>1  2  3<br>
   2  4  6<br>
   3  6  9  </p>

<p>has  <strong>6</strong> unique values namely <em>[1, 2, 3, 4, 6, 9]</em></p>

<p>So far I only have a <strong>O(n<sup>2</sup>)</strong> solution</p>

<pre><code> public static void findDistinctNumbers(int n) {

    Set&lt;Integer&gt; unique = new HashSet&lt;&gt;();

    for(int i=1; i&lt;=n; i++) {
        for(int j=1; j&lt;=n; j++) {
            unique.add(i*j);
        }
    }
    System.out.println("number of unique values: " + unique.size());
  }
</code></pre>

<p>Is there a better approach which is less than <strong>O(n<sup>2</sup>)</strong> ?</p>