36505

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

Question:

I am having difficulty trying to solve the following problem:

<blockquote>

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.

</blockquote>

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?

Answer1:

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!

Answer2:

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>

Recommend

  • 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?