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

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

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$).

Answer 4

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$.

Answer 5

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.

Answer 6

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}$ .

Answer 7

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.