Zaoly's blog

By Zaoly, history, 10 months ago, In English

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
  • Vote: I like it
  • +21
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +7 Vote: I do not like it
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This recurrence is so close to solving it, but it occasionally gets off-by-one errors:

$$$S(n) = S(n-1) + \varphi(n) + 1$$$

The curly phi symbol is the Euler totient function.