A problem I made but don't know how to solve

A problem I made but don't know how to solve

3 hours ago, # | 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).

• 2 hours ago, # ^ | For n <= 1e7, one possible solution is to find all primes larger than x and find all the numbers which have only them in their factorisation using sieve of erashosthens. This would yield a solution of O(n log log n).

• 2 hours ago, # ^ | You can find the number of primes up until N in something like O(N^(2/3)), so you this by itself isn't a reason to discard the possibility of having big N. https://codeforces.com/problemset/problem/665/F This is a related problem, there's some discussion about other approaches in the editorial and this is well known if you've wandered around project euler for long enough. That being said, I don't know how to solve the problem proposed here in lower than O(N).

  • 70 minutes ago, # ^ | Thank you for the insight, I was not aware of this.