help needed understanding Sieve of Eratosthenes

deecarney4

New member
Joined
Jun 21, 2007
Messages
20
Does anyone understand this Sieve of Eratosthenes

Example: find all prime numbers of 100
Largest prime number needed to check to solve the problem
 
deecarney4 said:
Does anyone understand this Sieve of Eratosthenes
The Sieve is a fairly simple-minded "cross out the numbers and see what's left" sort of thing. A quick search should turn up loads of links explaining what it is and showing how to use it.

deecarney4 said:
Example: find all prime numbers of 100
I'm sorry, but I'm not familiar with any meaning for the above. I've heard of finding prime "factors" of a number, or of finding all primes "less than" a number. But how does your book define the primes "of" a number? :shock:

Please provide the word-for-word definition, exactly as given in your text. Thank you.

deecarney4 said:
Largest prime number needed to check to solve the problem
I'm sorry, but I have no idea what this means...? :oops:

Please reply with clarification, including the exact text of and instructions for this exercise. Thank you! :D

Eliz.
 
deecarney4 said:
Does anyone understand this Sieve of Eratosthenes

Example: find all prime numbers of 100
Largest prime number needed to check to solve the problem
The Sieve of Eratosthenes

Lets find the primes between 1 and 100.

Write down the sequence of numbers from 1 to 100.

Cross out the 1.

Beginning with the 2, strike out every second number beyond the 2, i.e., 4, 6, 8, 10, etc.

Starting from the first remaining number, 3, cross out every third number beyond the 3, i.e., 3, 6, 9, 12, etc.

Starting from the first remaining number, 5, cross out every fifth number beyond the 5, i.e., 5, 10, 15, 20, etc.

Continue with the 7, crossing out every seventh number beyond the 7, i.e., 7, 14, 21, 28, etc.

Continue the process until you have reached N or 100.

The numbers remaining are the primes between 1 and 100, namely 2, 3, 5, 7, 11, 13,17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97. By definition, all the others are composite numbers.

The Sieve of Sundaram

Given the infinite table of p rows and q columns.

.4....7....10...13...16...19...22...25....28....52...57...etc.. constant 3 difference
.7...12...17...22...27...32...37...42....47....52...57...etc constant 5 difference
10..17...24...31...38...45...52...59....66....73...80...etc. constant 7 difference
13..22...31...40...49...58...67...76....85....94..103..etc. constant 9 difference
16..27...38...49...60...71...82...93...104..115..126..etc. constant 11 difference
19..32...45...58...71...84...97..110..123..136..149..etc constant 13 difference

Required to determine if the number N is prime or composite.

Let k = (N - 1)/2

If the value of k is found in the table, N is composite.

If the value of k is not found in the table, N is prime.

The 1st number in the pth row is given by 3p + 1

The successive difference in each row is given by 2q + 1

The qth number in the pth row is there defined as (2q + 1)p + q

Therefore, if values of p and q can be found to make (2q + 1)p + q = k, N is not a prime.
 
Hello, deecarney4!

Does anyone understand this Sieve of Eratosthenes ?

Example: find all prime numbers less than 100.
Largest prime number needed to check to solve the problem?

As TchrWill suggested, write out the numbers from 1 to 100:

. . \(\displaystyle \begin{array}{cccccccccc}1&2&3&4&5&6&7&8&9&10\\11&12&13&14&15&16&17&18&19&20\\21&22&23&24&25&26&27&28&29&30\\31&32&33&34&35&36&37&38&39&49\\41&42&43&44&45&46&47&48&49&50\\51&52&53&54&55&56&57&58&59&60\\ 61&62&63&64&65&66&67&68&69&70\\71&72&73&74&75&76&77&78&79&80\\81&82&83&84&85&86&87&88&89&90\\91&92&93&94&95&96&97&98&99&100 \end{array}\)


Cross out 1.
Then circle 2 and cross out every multiple of 2:

. . \(\displaystyle \begin{array}{cccccccccc}\not{1}&\fbox{2}&3&\not{4}&5&\not{6}&7&\not{8}&9&\not{10}\\11&\not{12}&13&\not{14}&15&\not{16}&17&\not{18}&19&\not{20}\\21&\not{22}&23&\not{24}&25&\not{26}&27&\not{28}&29&\not{30}\\31&\not{32}&33&\not{34}&35&\not{36}&37&\not{38}&39&\not{40}\\41&\not{42}&43&\not{44}&45&\not{46}&47&\not{48}&49&\not{50}\\51&\not{52}&53&\not{54}&55&\not{56}&57&\not{58}&59&\not{60}\\61&\not{62}&63&\not{64}&65&\not{66}&67&\not{68}&69&\not{70}\\71&\not{72}&73&\not{74}&75&\not{76}&77&\not{78} & 79 &\not{80} \\ 81&\not{82} & 83 &\not{84}&85&\not{86}&87&\not{88}&89&\not{90}\\91&\not{92}&93&\not{94}&95&\not{96}&97&\not{98}&99&\not{100} \end{array}\)


Circle the next number (3) and cross out every multiple of 3:

. . \(\displaystyle \begin{array}{cccccccccc}* & \fbox{2}& \fbox{3} & * & 5 & * & 7 & * & \not{9} & * \\11 & * & 13 & * & \not{15} & * & 17 & * & 19 & * \\\not{21} & * & 23 & * & 25 & * & \not{27} & * & 29 & * \\ 31 & * & \not{33} & * & 35 & * & 37 & * & \not{39} & * \\41 & * & 43 & * & \not{45} & * & 47 & * & 49 & * \\\not{51} & * & 53 & * & 55 & *& \not{57} & * & 59 & * \\61 & * & \not{63} & * & 65 & * & 67 & * & \not{69} & * \\71 & * & 73 & * & \not{75} & * & 77 & * & 79 & * \\ \not{81} & * & 83 & * & 85 & * & \not{87} & * & 89 & *\\91 & * & \not{93} & *& 95 & *& 97 & * & \not{99} & *\end{array}\)


Circle the next number (5), then cross out every mutliple of 5:

. . \(\displaystyle \begin{array}{cccccccccc}* & \fbox{2}& \fbox{3} & * & \fbox{5} & * & 7 & * & * & * \\11 & * & 13 & * & * & * & 17 & * & 19 & * \\\ * & * & 23 & * & \not{25} & * & * & * & 29 & * \\ 31 & * & * & * & \not{35} & * & 37 & * & * & * \\41 & * & 43 & * & * & * & 47 & * & 49 & * \\ * & * & 53 & * & \not{55} & *& * & * & 59 & * \\61 & * & * & * & \not{65} & * & 67 & * & * & * \\71 & * & 73 & * & * & * & 77 & * & 79 & * \\ * & * & 83 & * & \not{85} & * & * & * & 89 & *\\91 & * & * & *& \not{95} & *& 97 & * & * & *\end{array}\)


Circle the next number (7), then cross out every multiple of7:

. . \(\displaystyle \begin{array}{cccccccccc}* & \fbox{2}& \fbox{3} & * & \fbox{5} & * & \fbox{7} & * & * & * \\11 & * & 13 & * & * & * & 17 & * & 19 & * \\\ * & * & 23 & * & * & * & * & * & 29 & * \\ 31 & * & * & * & * & * & 37 & * & * & * \\41 & * & 43 & * & * & * & 47 & * & \not{49} & * \\ * & * & 53 & * & * & *& * & * & 59 & * \\61 & * & * & * & * & * & 67 & * & * & * \\71 & * & 73 & * & * & * & \not{77} & * & 79 & * \\ * & * & 83 & * & * & * & * & * & 89 & *\\\not{91} & * & * & *& * & *& 97 & * & * & *\end{array}\)


Circle the next number (11), then cross out every multiple of 11:

. . \(\displaystyle \begin{array}{cccccccccc}* & \fbox{2}& \fbox{3} & * & \fbox{5} & * & \fbox{7} & * & * & * \\\fbox{11} & * & 13 & * & * & * & 17 & * & 19 & * \\\ * & * & 23 & * & * & * & * & * & 29 & * \\ 31 & * & * & * & * & * & 37 & * & * & * \\41 & * & 43 & * & * & * & 47 & * & * & * \\ * & * & 53 & * & * & *& * & * & 59 & * \\61 & * & * & * & * & * & 67 & * & * & * \\71 & * & 73 & * & * & * & * & * & 79 & * \\ * & * & 83 & * & * & * & * & * & 89 & *\\ * & * & * & *& * & *& 97 & * & * & *\end{array}\)

We find that this point that there are no mutliples of 11 to cross out.
And we would circle 13 and find that there no multiples of 13 to cross out.
And so on . . .
. . Hence, we can stop.

The remaining numbers are ALL the primes less than 100.

. . \(\displaystyle \begin{array}{cccccccccc}* & \fbox{\;2}& \fbox{\;3} & * & \fbox{\;5} & * & \fbox{\;7} & * & * & * \\\fbox{11} & * & \fbox{13} & * & * & * & \fbox{17} & * & \fbox{19} & * \\\ * & * & \fbox{23} & * & * & * & * & * & \fbox{29} & * \\ \fbox{31} & * & * & * & * & * & \fbox{37} & * & * & * \\ \fbox{41} & * & \fbox{43} & * & * & * & \fbox{47} & * & * & * \\ * & * & \fbox{53} & * & * & *& * & * & \fbox{59} & * \\ \fbox{61} & * & * & * & * & * & \fbox{67} & * & * & * \\ \fbox{71} & * & \fbox{73} & * & * & * & * & * & \fbox{79} & * \\ * & * & \fbox{83} & * & * & * & * & * & \fbox{89}\\ *& * & * & * & *& * & * & \fbox{97} & * & * \end{array}\)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

How do we know when we can stop?

To find the primes less than \(\displaystyle N\):

Circle the first occurence of every prime
. . then cross out every multiple of that prime.

We continue as long as the prime \(\displaystyle p\) is such that: \(\displaystyle \,p\:<\:\sqrt{N}\)


In our example, \(\displaystyle N\,=\,100\)
. . So we need to check the primes less than \(\displaystyle \sqrt{100}\,=\,10\)
. . That is: \(\displaystyle \:2,\:3,\;5,\;7\)

For primes less than 1000, we would check primes less than \(\displaystyle \sqrt{1000} \:\approx\:31.6\)
. . That is: \(\displaystyle \:2,\:3,\:5,\:7,\:11,\:13,\:17,\:19,\:23,\:29,\:31.\)

 
Soroban ol' buddy, you certainly go above and beyond. I wonder if you'll even get a thank you. I would hope so.
 
Top