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!
 A: 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.
A: 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. 
A: 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$).
A: 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$.
A: 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}$ .
A: 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.
