The number of positive integers in [1,1e18] that cannot be separated by any integers in [2,10]

Question

I am having difficulty resolving the following problem:

For Q queries, Q <= 1e6, where each query is a positive integer N, N <= 1e18, find the number of integers in [1, N], which cannot be separated by integers in [2,10] for each request.

I was thinking about using the sieve method to filter numbers in [1,1e18] for each request (similar to the sieve of eratosthenes). However, the value of N can be very large. Therefore, I cannot use this method. The most useful observation I could make is that numbers ending in 0,2,4,5,6,8 are invalid. But that does not help me with this problem.

I saw a solution for a similar problem that uses fewer queries (Q <= 200). But this does not work for this problem (and I do not understand this solution).

Can someone please advise me how to solve this problem?

Answer 1

The only numbers of matter in [2,10] are those prime numbers that are 2, 3, 5, 7

So, let them say that a number cannot be divided by integers in [2,10] , this number cannot be divided by {2,3,5,7}

Which is also equal to the total number between [1,n] minus the whole number that is divisible by any combination {2,3,5,7} .

So, this is the interesting part: from [1,n] , how many numbers are divisible by 2? Answer: n/2 (why? Just because every 2 number has one number divided by 2)

Similarly, how many numbers are divisible by 5? Answer: n/5 ...

So do we have an answer? No, since we found out that we doubled the count of numbers separated by both {2, 5} and {2, 7} ..., so now we need their minus.

But wait, it looks like we're half as much as those divided by {2,5,7} ... so we need to add it back

...

Keep doing this until all the combinations are taken care of, so there should be a 2 ^ 4 combination, which is 16 in total, quite a bit to deal with.

Take a look at the inclusion-exclusion principle for a good understanding.

Good luck

Answer 2

Here's an approach to how to handle this.

A place to start is to think about how you can split it into pieces. With such a problem, the place to start is the smallest common denominator (LCD) - in this case, 2.520 (the smallest number divisible by all numbers less than 10).

The idea is that if x is not divisible by any number from 2-10, then x + 2,520 is also not divisible.

Therefore, you can divide the problem into two parts:

• How many numbers between 1 and 2,520 are “relatively simple” with numbers from 2-10?
• How many times is 2,520 included in your target number? You should also consider the rest.