10
$\begingroup$

Why in Sieve of Erastothenes of $N$ number you need to check and cross out numbers up to $\sqrt{N}$? How it's proved?

For example if $N = 20$:

with $2$ we cross out:

2 4 6 8 10 12 14 16 18 20

with $3$:

3 9 15

and with $5$ we don't need to check because $10$, $15$ and $20$ are already crossed out and same with others biggers.

$\endgroup$
4
  • 4
    $\begingroup$ Because if N is composite, one of its factors is at most sqrt(N) hence one already encountered this decomposition of N when all the multiples of integers at most sqrt(N) have been crossed out. $\endgroup$
    – Did
    Aug 21 '11 at 11:19
  • 2
    $\begingroup$ You mean "square root of $N$", not "square of $N$" but everyone seems to realise that. Notice that if $N = p^2$ for a prime $p$, then the sieve method won't cross out $N$ until you try the prime $\sqrt{N}$. $\endgroup$
    – Geoff Robinson
    Aug 21 '11 at 11:56
  • $\begingroup$ Are you asking why you need to go all the way up to the square root? or are you asking why you don't have to go any farther than the square root? $\endgroup$
    – Gerry Myerson
    Aug 21 '11 at 13:10
  • $\begingroup$ @GerryMyerson any farther than the square root $\endgroup$
    – Templar
    Aug 21 '11 at 17:23
11
$\begingroup$

Suppose $xy=N=\sqrt{N}\sqrt{N}$. If $x\ge\sqrt{N}$, then $y\le\sqrt{N}$ and vice-versa. Thus, if $xy=N$, then one of $x$ or $y$ must be less than or equal to $\sqrt{N}$. This means that if $N$ can be factored, one of the factors must be less than or equal to $\sqrt{N}$.

This is the contrapositive of what Gadi A said, but sometimes, if a statement doesn't make sense to you, its contrapositive might.

To answer the question asked: if you've crossed out the multiples of all the numbers less than or equal to $\sqrt{N}$, all multiples of numbers greater than $\sqrt{N}$ will already be crossed out. This is because any number which is less than or equal to $N$ and is a multiple of a number greater than $\sqrt{N}$, will have a factor that is less than or equal to $\sqrt{N}$ and therefore will already be crossed out. (Of course, when we are speaking of multiples here we mean multiples of $2\times$ or more, as in the Sieve.)

$\endgroup$
1
  • $\begingroup$ ok, finally I got it, thanks $\endgroup$
    – Templar
    Aug 22 '11 at 13:32
6
$\begingroup$

Quite simple: Denote the root of N by a, so $a\cdot a\ge N$.Now, if a number $c$ factors $c=xy$ such that $x,y> a$ we have $c=xy> a\cdot a\ge N$.

In words: if a numbers has only factors bigger than the square root of N, it must be larger than N (and in other words - if a number smaller than N has a factor larger than the square root of N, it must also have a small factor).

$\endgroup$
2
  • $\begingroup$ I don't really understand :/ if c=xy why c>xy and how xy >= aa if x and y are bigger than a? it should be xy>aa? $\endgroup$
    – Templar
    Aug 21 '11 at 11:34
  • $\begingroup$ You are right, this was a typo. Fixed. $\endgroup$
    – Gadi A
    Aug 21 '11 at 11:44
3
$\begingroup$

HINT $\rm\ \ N = ab,\ a\le b\ \Rightarrow\ a^2 \le ab\ \Rightarrow\ a\le \sqrt{ab} = \sqrt{N}\:.$

$\endgroup$
3
$\begingroup$

If a number $N$ has a prime factor greater than $\sqrt{N}$ (but not equal to $N$ itself), then it also has a prime factor less than $\sqrt{N}$.

To see why, suppose $N$ has a prime factor $A$ not equal to $N$ itself. Then it has another factor $B$, so that $AB = N$. But it is impossible that $A>\sqrt{N}$ and $B \ge \sqrt{N}$, because then $AB > N$, so $N>N$.

So we must have $B < \sqrt{N}$.

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