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.