# [Python 2 (PyPy)], 145 bytes

Because turning code-golf competitions into fastest-code competitions is fun, here is an O(*n*) algorithm that, on TIO, solves *n* = **5,000,000,000** in 30 seconds.  ([Dennis’s sieve](https://codegolf.stackexchange.com/a/128176/39242) is O(*n* log *n*).)

<!-- language-all: lang-python -->

    import sympy
    n=input()
    def g(i,p,k,s):
     while p*max(p,k)<=n:l=k*p;i+=1;p=sympy.sieve[i];s-=g(i,p,l,n/l*(n/l*k+k-2)/2)
     return s
    print~g(1,2,1,-n)

[Try it online!][TIO-j4c0bp0j]

[Python 2 (PyPy)]: http://pypy.org/
[TIO-j4c0bp0j]: https://tio.run/##NYy9DsIgFEZ3noIRWrCWxMXKkxgHE7G9gd7eAFVZfHX8i99whpOcj0qeFjSaCpVaYaYlZp7KTIWhBaQ1C8ku7spHAYqUV0nuGb9PEBynZj4/xFvKg8V9sL6hAVrbD2S/D5sE7uaOcBqStr8@KOxCIz7wrddGdkYyHl1eI/LEKALm5yh6ZVSvNMpad9v/Xg "Python 2 (PyPy) – Try It Online"

### How it works

We count the size of the set

*S* = {(*a*, *b*) | 2 ≤ *a* ≤ *n*, 2 ≤ *b* ≤ largest-proper-divisor(*a*)},

by rewriting it as the union, over all primes p ≤ √n, of

*S*<sub>*p*</sub> = {(*p*⋅*c*, *b*) | 1 ≤ *c* ≤ *n*/*p*, 2 ≤ *b* ≤ *c*},

and using the [inclusion–exclusion principle](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle):

|*S*| = ∑ (−1)<sup>*m* − 1</sup> |*S*<sub>*p*<sub>1</sub></sub> ∩ ⋯ ∩ *S*<sub>*p*<sub>*m*</sub></sub>| over *m* ≥ 1 and primes *p*<sub>1</sub> < ⋯ < *p*<sub>*m*</sub> ≤ √n,

where

*S*<sub>*p*<sub>1</sub></sub> ∩ ⋯ ∩ *S*<sub>*p*<sub>*m*</sub></sub> = {(*p*<sub>1</sub>⋯*p*<sub>*m*</sub>⋅*c*, *b*) | 1 ≤ *c* ≤ *n*/(*p*<sub>1</sub>⋯*p*<sub>*m*</sub>), 2 ≤ *b* ≤ *p*<sub>1</sub>⋯*p*<sub>*m* − 1</sub>*c*},  
|*S*<sub>*p*<sub>1</sub></sub> ∩ ⋯ ∩ *S*<sub>*p*<sub>*m*</sub></sub>| = ⌊*n*/(*p*<sub>1</sub>⋯*p*<sub>*m*</sub>)⌋⋅(*p*<sub>1</sub>⋯*p*<sub>*m* − 1</sub>⋅(⌊*n*/(*p*<sub>1</sub>⋯*p*<sub>*m*</sub>)⌋ + 1) − 2)/2.

The final result is then |*S*| + *n* − 1.