Question

How many prime numbers less than 100. Explain by the principle of inclusion and exclusion.?

Answer 1

Count non-primes and subtract from total number of integers. 

Let S_n represent the number of multiples of n in {1, ..., 99}. 

By principle of inclusion-exclusion, the number of primes is 99 + 4 - 1 - (S_2 + S_3 + S_5 + S_7) + (S_6 + S_10 + S_14 + S_15 + S_21 + S_35) - (S_30 + S_42 + S_70 + S_105) + (S_210). 

The 4 is there to account for the fact that 2, 3, 5, 7 are all primes. The -1 is to account for the fact that 1 is neither prime nor composite (being a unit). I left S_105 and S_210 in there even though they will of course be 0. Note that we only need to go to 7 because we can stop at floor(sqrt(99)). 

Note that S_n = floor(99 / n). 

So, if you do out the calculation, you will get 25, which you can verify through other methods is the correct answer.