We present a new algorithm to compute M(n), the function that counts the number of distinct integers in an n by n multiplication table. A straightforward algorithm is O(n²) in both time and space. Our algorithm is O(n² (ln n)^.914 (ln ln n)^(-3/2) ) in time and O(n) in space. Since a sieve underlies both approaches, the time-space comparison is quite advantageous. We use this new algorithm to compute M(2^k -1) for k = 26,..,29.