Does this behavior of simple sieves have a name?

45 Views Asked by At

The sieve of Eratosthanes sequentially identifies primes by using smaller known primes to discard numbers from a list, eventually leaving behind only other primes. At the nth step, we use $p_n$ and remove from the list all multiples of $p_n$ larger than $p_n$. At this point there will remain many numbers larger than $p_n$ that have not been discarded. They are of two types: Primes, and composites that are destined to be removed in subsequent sieving steps. We can ask, What is the smallest composite (call it $c_m$) that has not yet been discarded?

Since it is composite, it has prime factors. But since every number with prime factors $\le p_n$ has been sieved out, the prime factors of $c_m$ must all be larger than $p_n$. Hence, $c_m>p_n^2$. Any number $<p_n^2$ not removed prior to sieving with $p_n$ must be a prime. In other words, $p_n$ only exerts a (distinct) sieving effect on numbers larger than $p_n^2$

It might be the case that for other simple sieves, the effect of each particular sieving element (i.e. what corresponds to $p_n$ in the sieve of Eratosthanes) also might not begin to exert its distinct effect in a range close to that element. In order to read and learn about this (assuming it is an appreciated behavior), I first have to know what it is called.

Simple question: Does this behavior (or property) have a name?

Added by edit: In the comments I was asked what other sieves I might have in mind. Not being proficient in sieve theory, I demurred. But there is one analogous sieving process that bears mentioning. With regard to the sieve of Eratosthanes, we sieve by discarding multiples of primes, $kp$, with the following constraints: I. $k>1$; II. There is no (necessary) upper bound on the list being sieved; III. Every prime is used; IV. We identify (as primes) the numbers that are not discarded.

We can sieve by discarding $kp$ using slightly modified constraints, viz: I. $k\ge 1$; II. The upper bound on the list is an integer $m$; III. We only use primes that divide $m$; IV. We count the numbers that are not discarded. In this case, what we obtain is the totient function, $\phi(m)$.