3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ There was an almost exact copy of this question asked recently, you can see my answer here. $\endgroup$ – Eff Jan 22 '15 at 22:44
  • 1
    $\begingroup$ This also triggers deja vu for me, but I can't find the one that I answered. $\endgroup$ – Robert Soupe Jan 23 '15 at 5:08
2
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.