Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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. –  Did Aug 21 '11 at 11:19
2  
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}$. –  Geoff Robinson Aug 21 '11 at 11:56
    
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? –  Gerry Myerson Aug 21 '11 at 13:10
    
@GerryMyerson any farther than the square root –  Templar Aug 21 '11 at 17:23
add comment

4 Answers 4

up vote 3 down vote accepted

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

share|improve this answer
    
ok, finally I got it, thanks –  Templar Aug 22 '11 at 13:32
add comment

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

share|improve this answer
    
I don't really understand :/ if c=xy why c>xy and how xy >= a*a if x and y are bigger than a? it should be xy>a*a? –  Templar Aug 21 '11 at 11:34
    
You are right, this was a typo. Fixed. –  Gadi A Aug 21 '11 at 11:44
add comment

If a number $N$ has a prime factor greater than $\sqrt{N}$ (but not equal to $N$ itslef), 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}$.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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