Number of positive integers in [1,1e18] that cannot be divided by any integers in [2,10]


I am having difficulty trying to solve 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] that cannot be divided by integers in [2,10] for each query.


I thought of using using a sieve method to filter out numbers in [1,1e18] for each query (similar to sieve of eratosthenes). However, the value of N could be very large. Hence, there is no way I could use this method. The most useful observation that I could make is that numbers ending with 0,2,4,5,6,8 are invalid. But that does not help me with this problem.

I saw a solution for a similar <a href="http://www.programmingwithbasics.com/2017/04/geeksforgeeks-solution-for-number-that.html" rel="nofollow">problem</a> that uses a smaller number of queries (Q <= 200). But it doesn't work for this problem (and I don't understand that solution).

Could someone please advise me on how to solve this problem?


The only matter numbers in [2,10] are those primes which are 2, 3, 5, 7

So, Let say, the number cannot be divided by integers in [2,10] is the number cannot be divided by {2,3,5,7}

Which is also equalled to the total number between [1,n] minus all number that is divided by any combination of {2,3,5,7}.

So, this is the fun part: from [1,n] how many numbers that is divided by 2? The answer is n/2 (why? simple, because every 2 number, there is one number divided by 2)

Similarly, how many numbers that is divided by 5? The answer is n/5 ...

So, do we have our answer yet? No, as we found out that we have doubled count those numbers that divided by both {2, 5} or {2, 7} ..., so now, we need to minus them.

But wait, seems like we are double minus those that divided by {2,5,7} ... so we need to add it back


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

Take a look at <a href="https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle" rel="nofollow">Inclusion-Exclusion principle</a> for some good understanding.

Good luck!


Here is an approach on how to handle this.

The place to start is to think about how you can split this into pieces. With such a problem, a place to start is the least common denominator (LCD) -- in this case 2,520 (the smallest number divisible by all the 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.

Hence, you can divide the problem into two pieces:

<ol><li>How many numbers between 1 and 2,520 are "relatively prime" to the numbers from 2-10?</li> <li>How many times does 2,520 go into your target number? You need to take the remainder into account as well.</li> </ol>


  • The error `Error: unexpected '}' in “}”` [closed]
  • How does this prime number generation method work?
  • How to Aggregate Relational Data in Stata?
  • How to find F(x,0) when F(x,i) = F(x-1,i) xor F(x-1, i+1) xor … F(x-1,n) in less than linear time
  • Subsetting DataFrame in R by duplicate values for Year by lowest value for Rating
  • Generating prime numbers between m and n [duplicate]
  • Is this prime generator inefficient C++?
  • Wrong Range Rate with Pyephem
  • branch out of range compile error
  • Why are views not counted if you embed a youtube iframe dynamically using jquery?
  • Get or convert Week of year to ISO week
  • Cassandra: What is a subcolumn
  • C++ Armadillo Access Triangular Matrix Elements
  • Is it possible to “shrink” a PdfPtable?
  • Binary Tree Traversal Sum Of Each Depth
  • Small video playback
  • Selecting a subset of data in ServiceStack.OrmLite
  • Efficient & Pythonic way of finding all possible sublists of a list in given range and the minim
  • CakePHP ACL tutorial initDB function warnings
  • how to avoid repetitive constructor in children
  • Installing Apache MyFaces 2 on WildFly 8.2.0
  • Spark fat jar to run multiple versions on YARN
  • Exception “firebase.functions() takes … no argument …” when specifying a region for a Cloud Function
  • Ajax Loaded meta Tags
  • Using variable in a value field in jMeter
  • Using jQuery closest() method with class selector
  • What is Eclipse's Declaration View used for?
  • Array.prototype.includes - not transformed with babel
  • Excel - Autoshape get it's name from cell (value)
  • Check if a string to interpolate provides expected placeholders
  • ActionScript 2 vs ActionScript 3 performance
  • R: gsub and capture
  • RestKit - RKRequestDelegate does not exist
  • Numpy divide by zero. Why?
  • jqPlot EnhancedLegendRenderer plugin does not toggle series for Pie charts
  • Traverse Array and Display in markup
  • Comma separated Values
  • json Serialization in asp
  • Why can't I rebase on to an ancestor of source changesets if on a different branch?
  • How to load view controller without button in storyboard?