# Sieve of Eratosthenes : why $\sqrt n$ work?

I have a question about Sieve of Eratosthenes,

I refer at the "simply version" :

If I have an $\boldsymbol{n}$ and I want the prime numbers up to n, I search and delete multiply up to $\leqslant \sqrt n$ .

For example: $n = 28; \sqrt n = 5,29$ After 5 I'm sure that I haven't delete multiply but I will find only prime numbers.

Now my question isn't how does it work, and why it is work.. But my question is why $\sqrt n$ ? and for example why not $\log n$ (is an example for trying to pass my question) How do you get to think that the $\sqrt n$ has the power in this context?

How do you get to think that the $\sqrt n$ assures me that there aren't more multiples to be erased?

Is there an explanation? graphic, numerical, of any kind? Thanks!

• If $p$ is the smallest prime that divides $n$ then $n=pq$ with $q\geq p$. Therefore $n=pq\geq p^2$, i.e. $\sqrt{n}\geq p$.
– user539964
Mar 15, 2018 at 15:15
• @AOlov this. you pulled the rabbit out of the cylinder with $p*q>= p^2$ ... $p^2$ is the key. how did you do?? knowing the solution(I mean knowing that we had to find $\sqrt n$ ) ???? :P great job ! Mar 15, 2018 at 16:55
• @Z1pp3d I had seen it before. It was just memory.
– user539964
Mar 15, 2018 at 17:30
• there is no trial division in the sieve of Eratosthenes, only addition and comparison. Mar 17, 2018 at 19:26

For $$n$$ not to be prime, it needs at least two prime factors. The square root of $$n$$ provides a 'pivot': if $$x$$ is less than the square root of $$n$$, then $$y=\frac{n}{x}$$ is greater than the square root of $$n$$.

So, if no prime factors are found by the square root of $$n$$ and $$n$$ is composite, at least two factors of $$n$$ must be greater than the square root of $$n$$, which is an obvious contradiction.

Let $n = ab$.

Either $a \le \sqrt n$ or $a \ge \sqrt n$ (or both).

If $a \le \sqrt n$ then $b = \frac na \ge \frac n{\sqrt n} = \sqrt n$.

If $a \ge \sqrt n$ then $b = \frac na \le \frac n{\sqrt n} = \sqrt n$.

So either $a \le \sqrt n$ or $b \le \sqrt n$ (or both).

So if $n$ has any factors other than $1$ and itself then some of them will be less than or equal to $\sqrt n$. (And some of them will be greater than or equal to $\sqrt n$.)

So if you get all the way up to the $\sqrt n$ and you haven't found any factors yet, then you aren't going to find any because if there were any, some of them would have been found by then. So you might as well quit looking.

You could, just to be perverse, do a backwards sieve and start looking at $n-1$ and work your way down to $\sqrt n$ and then quit. If $n$ has any factors some of them will be greater or equal to $\sqrt{n}$ so if you don't find any by then, then there aren't any.

But 1) Big numbers are harder to calculate than small numbers and 2) Going up we can rule out multiples (e.g. If $2 \not \mid n$ we don't need to check $4,6,8$ or any even number. If going down we get that $30 \not \mid n$ we can't rule out any factors of $30$).

Let $x$ be an integer such that $\sqrt n \lt x \le n$ which is not divisible by any integer $\le \sqrt n$. Then it is to be proved that $x$ is prime. Let assume on contrary that $x$ is composite. Then $x=ab$, where $a\gt \sqrt n,b\gt \sqrt n$ $\implies ab\gt n\implies x\gt n$ which is a contradiction. Hence $x$ is prime.

Assume that there exist a composite number $$q$$ between $$sqrt(n)$$ and $$n$$ which can be written as multiple of two number $$x$$ and $$y$$ both $$\ge$$ $$sqrt(n)$$. Where one of them is a prime number greater than $$sqrt(n)$$.

$$q \lt n$$ ----(1)

$$sqrt(n) \lt x \lt n$$ ----(2)

$$sqrt(n) \lt y \lt n$$ ----(3)

$$x*y = q$$

But from 2 & 3 we get that

$$x*y \gt n$$ i.e $$q \gt n$$ which contradicts 1. So we can't have a prime number greater than $$sqrt(n)$$ and have its multiple greater than $$sqrt(n)$$ producing a composite number less than $$n$$.

Since $$(\sqrt{n})^2=n$$ , it's the geometric mean of any product of two numbers that multiply to $$n$$ . Means generally, are a central tendency marker, and so need at least 1 input below them. Similarly, the only way a number $$n$$ can have more than $$k$$ prime factors, is if one is below $$\sqrt[k+1]{n}$$ . So you know all numbers that are semiprime or prime by $$\sqrt[3]{n}$$ .

If you list the factors of $$n$$, notice that $$\lfloor\sqrt n \rfloor$$ is in the middle. And once you pass $$\sqrt n$$, the pairs of factors just repeat, since every factor less than it has to be paired with one greater than it.

The best explanation for this that I found was in David M. Burton's Elementary Number Theory textbook, section 3.2 The Sieve of Erastothenes, page 57. It goes like this (reworded/reinterpreted by me). fleadblood's answer is the closest that I could find to this.

Suppose that $$a > 1$$ is known to be a composite integer. Then we know there must exist some integers $$b$$ and $$c$$ such that $$1 < b,c < a$$ and $$a = bc$$. That is the definition of a composite integer.

There are three discrete cases to consider with regard to the relationship between $$b$$ and $$c$$:

1. $$b = c$$
2. $$b > c$$
3. $$b < c$$

Consider what each case implies:

1. $$b = c \implies b^2 = bc = a \implies b = c = \sqrt{a}$$. That is, $$a$$ is a perfect square.
2. $$b > c \implies bc > c^2 \implies a > c^2 \implies c < \sqrt{a}$$
3. $$b < c \implies b^2 < bc = a \implies b < \sqrt{a}$$

Cases 2 and 3 can be thought of as mirrors of each other, so it suffices to consider just one of them without loss of generality. If one factor is strictly smaller than $$\sqrt{a}$$, the other must be strictly greater than $$\sqrt{a}$$.

Case 1: By the fundamental theorem of arithmetic, there exists a prime number $$p$$ such that $$1 < p \leq b = c$$ such that $$p|b$$ (and, by equivalence, $$p|c$$). Since $$p|b$$ and $$b|a$$, we have that $$p|a$$. Moreover, $$1 < p \leq b \leq \sqrt{a}$$. Therefore, if $$a$$ is composite, it must have a prime factor less than or equal to $$\sqrt{a}$$.

Case 2 and 3: By similar reasoning, and without loss of generality, consider $$b < \sqrt{a}$$. Once again, there exists a prime number $$q$$ such that $$1 < q \leq b < \sqrt{a}$$. And again, $$q|a$$. Therefore, if $$a$$ is composite, it must have a prime factor less than $$\sqrt{a}$$.

Putting all these cases together, $$a$$ being composite implies that there must exist some prime factor $$p$$, $$1 < p \leq \sqrt{a}$$, such that $$p|a$$. So to test if $$a$$ is prime, all we need to do is check if any integers in $$2, 3, ..., \sqrt{a}$$ divide $$a$$. If any of them do, then $$a$$ must be composite. Otherwise, $$a$$ must be prime.

• When you answer an old question that already has good answers you bump it to the head of the active queue, which costs time for folks who follow that queue. In this case the answer from @JMP makes essentially the same argument as yours, in just a few lines. Apr 8, 2023 at 2:03
• @EthanBolker My apologies, but I actually did read through all of the answers here and none of them satisfactorily clarified this for me. They either omitted relevant details or assumed too much knowledge. As a beginner in number theory, I find it easier to understand new concepts of all of the intermediate steps and reasoning are explained to me. Hence why I offered my own answer, in case someone like me is similarly unsatisfied by existing answers. Apr 8, 2023 at 2:05
• OK - that's a good enough reason Apr 8, 2023 at 2:06