Manually obtainining a list of primes $\leq n$, by using the root of n? In my abstract math class I learned that if we want to get a list of primes $\leq n$ manually, we have to calculate the root of n, and the floor of that result will be the greatest number for which to calculate divisibility.
Ex:
If we want the primes $\leq$ 50.
We write all of them, and remove every value divisible by each of the numbers $\leq$ than $\sqrt{n}$. After doing this, we will have a list of primes.
But why does this root of n work as a 'stop now' designator? I proved that for every composite number n, there is a prime factor $\leq \sqrt{n}$, but I still can't explain the first thing using this fact.
 A: As you say, we take the numbers from $1$ to $n$, and remove all the multiples of each $k$ from $2$ through $\sqrt n$.  This removes all the composite numbers. Why?
Suppose $c$ is any composite number less than or equal to $n$.  We want to show that $c$ is removed.  Then by the second fact you observed, $c$ has a prime factor at most $\sqrt c$.  Since $c\le n$, $\sqrt c \le \sqrt n$.  So $c$ has a prime factor $p$ of not more than $\sqrt n$, and is therefore a multiple of $p$.  When we remove all the multiples of $p$ from our list, we will remove $c$.
But this holds for every composite number $c$ that is not more than $n$, so removing all the multiples of numbers up to $\sqrt n$ removes all the composite numbers.
On the other hand, it is clear that we cannot stop sooner.  If $n = p^2$ then $n$ is composite and must be removed.  But we will not remove $n$ itself until we remove the multiples of $p = \sqrt n$.
A: Any composite number $n$ has the factors $m\times k$. Lets assume $k>m$. If both of these factors are greater than $\sqrt{n}$ then we have $k, m>\sqrt n$, and $k\times m > n$, which is absurd. Thus at least one of the factors must be less than $\sqrt{n}$, in this case $m$. If we have found such one factor, it will be enough to prove that $n$ is composite.
We also know that the factors are integers, so we can use the floor function $\lfloor\sqrt n\rfloor$ because $m$ is by definition an integer.
A: Designate $p$ as the smallest prime which we don't assess our candidate number $c$ for divisibility. So if we check $c$ against all the primes up to (and less than) $p$, and none of them divide $c$, then either:


*

*$c \geq p^2$, or

*$c$ is prime.


If $c < p^2$ and composite, it must have a prime factor less than $p$. Suppose instead that $c$ has two prime factors $q_1,q_2 \geq p$. However then $c\geq q_1q_2 \geq p^2$, contradicting $c < p^2$.
If you actually undertake the sieve exercise, eliminate multiples of the primes in succession, you'll see that the first new number removed with a new prime is the square of that prime.
A: Every composite number $n$ is divisible by a prime that is less than or equal to $\sqrt{n}$.
So if $n$ is not divisible by any prime up to $\sqrt{n}$, then $n$ must itself be prime.
Thus if, as in your example you want primes up to $50$, once you've eliminated nontrivial multiples of $2,3,5$, and $7$, any remaining numbers will be prime.  (Of course $1$ should also be eliminated.)
A: You've already done it. "I proved that for every composite number $n$, there is a prime factor $\leq \sqrt{n}$." If you have indeed proved this, then you already have the explanation.
Let's say $m = \lceil \sqrt{n} \rceil + 1$. Do you know if $m$ is prime or composite? If $m$ is composite, then it has a prime factor less than $\sqrt{n}$. But if $m$ is prime, it does not have a prime factor less than $\sqrt{n}$, for it is its own prime factor!
With your example of $n = 50$, we have $m = 8$. Obviously $8$ is composite, but if we were unsure, we'd only have to test its divisibility by four primes, namely $2, 3, 5, 7$.
Perhaps the sieve of Eratosthenes can clarify this for you. Write the numbers from $1$ to $50$ in a rectangular array. Circle $2$ and cross off all higher even numbers. Circle $3$ and cross off all higher multiples of $3$. But $6$ has already been crossed off on account of being even. Likewise you don't have to worry about $12$ or $18$, or $24$ etc., they should already be taken care of.
Do the same with $5$. The next number you need to cross off at this point is $25$. And when you get to $7$, the next number you need to cross off is $49$. If for some strange reason you neglected to cross $50$ off for being even, you should have crossed it off for being a multiple of $5$.
