Manually obtainining a list of primes $\leq n$, by using the root of n?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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:

1. $c \geq p^2$, or
2. $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.