David Purdum *Butler University*

**Faculty Sponsor(s): **Jonathan Webster *Butler University*

We present a new algorithm to compute M(n), the function that counts the number of distinct integers in the n x n multiplication table. Our new algorithm runs faster than a straightforward algorithm by using less memory, prime sieve segmentation, parallelization, and clever optimizations. Specifically, the straightforward algorithm is O(n^2) in both time and space complexity. Our algorithm runs in o(n^2 ln n) in time and O(n) in space. The algorithm has been developed in C++ and has gone through many optimizations to reduce runtime. We will discuss these optimizations of the C++ implementation.

Mathematics & Computer Science