[Math] Finding the number of primes numbers using exclusion/inclusion principle: What am I doing wrong

combinatoricsprime numbers

I want to find the number of primes numbers between 1 and 30 using the exclusion and inclusion principle. This is what I got:

enter image description here

The numbers in sky-blue are the ones I have to subtract. The others are the ones I have to add.

I got $1$ which gives me $11$ primes number below $30$, but are just $10$.

I don't know what I'm doing wrong.

Thanks!!

Best Answer

First, note that (for example) $2$ is divisible by $2$, but is prime. So in your first zone, all the composite count numbers should be one lower.

Using all primes like that in the first zone seems like you already need to know the answer before you start calculating. But you can get the answer without scanning all primes - just those up to $\sqrt {30}$ and their cross-products.

If you adjust for the prime overcount, then only use the lines corresponding to $2,3,5$, then $6,10,15$, then $30$, you get $30-(14+9+5)+(5+3+2)-(1)=11$ non-composite numbers less than or equal to $30$, which includes non-prime $1$.

Related Question