For the case where x > sqrt(n), the answer would just be the number of primes between x + 1 and n, since all numbers other than the primes can be written as P*Q (1 < P ≤ Q ≤ n), where P must be lower than sqrt(n) so it will not be coprime with the LCM. This is probably impossible to calculate for very large n so the limit for n should be lower, maybe around 10^6 or just make x ≤ sqrt(n) (I am not sure what happens in this case).

I am not sure what you mean with lcm. Edit: Thanks for help I got it now .

I have an idea which I thought on top of my head.

The $$$lcm(1, 2, \cdots x) = \prod\limits_{p \in primes}p^{max(k)_{p}}$$$. $$$max(k)_{p}$$$ is the largest power that satisfies $$$p^{max(k)_{p}} \le x$$$. Then, just subtract the number of multiples of $$$p^y$$$, $$$1 \le y \le max(k)_{p}$$$ in the range $$$[1, n]$$$, make sure to subtract each number uniquely by any technique. So, if you have a fast enough way to get the primes in the range $$$[1, x]$$$, I think that should be enough.

The tittle shows my whole life :)

Ok so I've figured out one way to solve this in $$$O(N^{2/3}logN + N/logN)$$$.

Basically, we'll have an array P of primes lesser than or equal to X and calculate a dp that'll solve the problem using PIE:

dp[i][j] = sum of (-1)^|s| for every subset s of primes in prefix of size i of P such that floor(N/product of si in s) = j

but instead of using that array like that, we'll process the primes over sqrt(N) by grouping them together by the floor of the division between N and them. This is the same idea as in the problem that I mentioned here https://codeforces.net/blog/entry/110878?#comment-987973. Using that problem's solution, we can solve this part in $$$O(N^{2/3} logN)$$$. We can do this because we can't use more than one such number otherwise their product will be larger than N. Then, what remains is the primes less than sqrt(N), there'll be $$$O(sqrt(N)/log(sqrt(N)))$$$ of those and we can simply find them and do the dp using two pointers to aid the transition to solve this last part in $$$O(number of primes * number of results for floor(N/i))$$$.

Edit: whoops. I was too stupid to think and just mechanically solved the problem. As dino_merlin mentioned, X being greater than sqrt(N) means just counting primes, so we can ignore everything that I mentioned here for that case. The remaining part for primes under sqrt(N) still stands.

Maybe we can use the "Magic" tab in Codeforces?