How Many Integers Can Be Expressed as the Product of Two Positive Integers Within N?

Revision en1, by Zaoly, 2024-01-22 16:12:55

Given a positive integer $$$n$$$, how many integers $$$z$$$ are there such that there exist two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$) such that $$$z = x \cdot y$$$?

For example, for $$$n = 5$$$, there are $$$14$$$ integers that can be legal values of $$$z$$$, which are: $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$8$$$, $$$9$$$, $$$10$$$, $$$12$$$, $$$15$$$, $$$16$$$, $$$20$$$, and $$$25$$$.


Is there any fast algorithm to solve this problem? At least, it should be much faster than the brute force solution (time complexity: $$$O(n^2)$$$).


Inspiration of the problem
Tags number theory, multiplication, product, counting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Zaoly 2024-01-22 16:12:55 1558 Initial revision (published)