At what rate are composites removed in a set after each prime multiple is cancelled out?

Question

I was looking at sieves today, mainly sieving for primes and I noticed a pattern type thing. As I crossed out primes in a small set, the number of composites that were crossed out decreased. I haven't tested this for larger sets but I reckon it won't be as quick. So I had the following question:

Given a set of numbers, at what rate do the number of composites decrease after each prime is cancelled out?

So for example, I have the following sieve

$$\begin{array}{ccccccccc} 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &10 \\ 11 & 12 & 13 & 14 & 15& 16& 17 & 18 & 19 \\ 20 & 21 & 22 & 23 & 24 & 25 &26 & 27& 28 \\ \end{array}$$

Now when I begin to sieve out the primes, by cancelling out multiples of $2$ $$\begin{array}{ccccccccc} \require{cancel} 2 & 3 & \cancel{4} & 5 & \cancel{6} & 7 & \cancel{8} & 9 & \cancel{10} \\ 11 & \cancel{12} & 13 & \cancel{14} & 15& \cancel{16}& 17 & \cancel{18} & 19 \\ \cancel{20} & 21 & \cancel{22} & 23 & \cancel{24} & 25 &\cancel{26} & 27& \cancel{28} \\ \end{array}$$

So you can see that $46$% of the numbers are already gone (of course) and then we continue with $3$. The number of multiples that are cancelled out are only $4$ and then when we continue to $5$, it is only $1$. So you can see that the number of numbers that are crossed out decreases rapidly after each prime, which makes sense but is there a general rate at which this happens? Like some number or some formula that one can apply to find that rate given a set?

Thanks!

Answer 1

The first prime removes $\frac{1}{2}$ of the composite numbers.

The second prime removes $\frac{1}{3}$ of the remaining composite numbers. In other words, it removes $\frac{1}{2}$*$\frac{1}{3}$ of all the composite numbers.

The third prime removes $\frac{1}{5}$ of the remaining composite numbers. In other words, it removes $\frac{1}{2} \frac{2}{3} \frac{1}{5}$ of the composite numbers.

Answer 2

I am not sure about what you wanted to mean by 'rate'...I am trying to give a possible answer.

Suppose you have the set $A=\{n\le x:n\in\mathbb{N}\}$ and you want to execute a sieving process on this set. Define $$T(n):=\#A_{p_n},\text{where$A_{p_n}$ is derived set after sifting by prime $p_n$}.$$Assume $T(0)=\#A$, recursively we can have, $$T(n)=T(n-1)-\#\{m\in A_{p_{n-1}}:p_n|m\}.$$ Let, $z>x$ and define $P(z):=\prod\limits_{p<z}p$. Now by simple inclusion-exclusion principle (as Legendre did) we have, $$\#\{m\in A_{p_{n-1}}:p_n|m\}=\sum_{d|P(z)\ \ {p_n|d}}\mu(d)\lfloor{x\over d}\rfloor=-\sum_{d|{p(z)\over p_n}}\mu(d)\lfloor{x\over dp_n}\rfloor$$$$=-{x\over p_n}\prod_{p_n\neq p<z}\left(1-{1\over p}\right)+\sum_{d|{p(z)\over p_n}}\mu(d)\{{x\over dp_n}\}.$$ Now using Merten's estimate above product $O\left({1\over\log z}\right)$. So you want to define rate of decrease of composite as $T(n-1)-T(n)$ that will be roughly $O\left({x\over\log z}\right)$. Choose $z$ as you wish.