Finding coprimes closest to a certain target
If you want the truely closest coprime to $\frac 4 7m$, you could start with $n = \mathrm{round}(\frac 4 7m)$. Then, while $\gcd(n,m) \neq 1$, try again with $n$ being the closest number to $\frac 4 7 m$ such that $n - q \not \equiv 0 \mod \gcd(q,m)$ for any previously checked number $q$ (keep track of previously checked numbers and gcds in a list)

Checking one candidate has complexity $\mathcal O(\log(m))$. The probability of any two numbers being coprime is $\frac 6 {\pi^2} \approx 60\%$ so the numbers of candidates to check should be $\mathcal O(1)$ on average.

Overall this should find you the closest coprime in $\mathcal O(\log(m))$ operations.