[Math] Sum of all numbers less than equal to X relatively prime to all number less than Y

algorithmselementary-number-theoryprime factorization

Here's a programming question probably needing lots of math:

Given two integers X and Y, you need to find the sum of all positive
integers less than or equal to X, which have no divisor smaller than
or equal to Y, apart from 1. Find the most efficient way to do this.

I've been thinking about it since a long time, but the best I could do was something like $O(nlgn)$ but the interviewer told me it could be done better.

My solution was to simply find all prime factors and use a slightly modified sieve to store the lowest prime factor of the number. This would take $O(sqrt(n))$ time. Now we can compute prime factors of any number in $O(lgn)$ time easily. So iterate from 1 to n, check if number has any prime factor less than Y, if yes, dont add it, otherwise add it.

Any ideas? I think this will have some kind of a direct formula.

Best Answer

Seeing the code would help to understand the points where it could be (or not) better than it is now, but initially there is a basic point you mention that could be enhanced, in your last step:

"So iterate from 1 to n, check if number has any prime factor less than Y, if yes, dont add it, otherwise add it."

  1. You would not need to start from $1$ but from $Y+1$, because a number under or equal to $Y$ has all the divisors under or equal to $Y$, so:$$n \ge Y+1$$(only the special case $n=1$ will be in your addition by default).So any $n \in [2,Y]$ can be discarded.

Now supposing that in a first step you sieved all the primes, then:

  1. Now for the interval $[Y+1,Y^2]$ you would just need to add the prime numbers inside the interval that you already sieved, not the composite numbers. This is because any composite $n$ has at least a divisor under $\sqrt{n}$, so any composite number in the interval $[Y,Y^2]$ at least has a divisor in the interval $[2,Y]$. So if you had made in a first step the sieving of the primes, you will not need to verify again any number in $[Y,Y^2]$, just directly add the primes in that interval.

  2. And finally you would need to test all composite numbers in the interval $[(Y+1)^2,X]$, because some of them could have all the divisors (except $1$) over $Y$, and in the other hand you can directly add all the primes in that interval.

I hope it helps, if you add the code I could have a look, just let me know in the comments. Probably is fine as it is, specially if the interviewer did not explain any details about how to make it better.

Related Question