(Update) Tag: rte-source |
m (Changed protection level for "Sieve of Eratosthenes" ([edit=autoconfirmed] (expires 16:03, January 15, 9617 (UTC)) [move=autoconfirmed] (expires 16:03, January 15, 9617 (UTC)))) |
||
| (5 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| − | In mathematics, the '''Sieve of Eratosthenes''' (Greek: κόσκινον Ἐρατοσθένους) is |
+ | In mathematics, the '''Sieve of Eratosthenes''' (Greek: κόσκινον Ἐρατοσθένους) is a way to obtain a list of all the prime numbers up until a given point. |
| − | The |
+ | The method works by methodically crossing out the composite numbers. The user will cross out the multiples of each prime, from 2 and up until the square root of the final number. The numbers that are not crossed off are prime numbers. |
| − | + | The algorithm is named after Eratosthenes of Cyrene, a Greek mathematician. |
|
| − | == |
+ | ==How to Use the Sieve== |
| − | + | [[File:Prime Numbers - The Sieve of Eratosthenes|thumb|right|335 px]] |
|
| − | # |
+ | #List all the numbers from 1 to a certain number. |
| + | #Cross out 1, since it is neither prime nor composite. |
||
#Circle 2 and cross out every other multiple of 2. |
#Circle 2 and cross out every other multiple of 2. |
||
| − | #Circle 3 and cross out every other multiple of 3.<br /> |
+ | #Circle 3 and cross out every other multiple of 3.<br />''Tip: Just add 6 to the first number, because all even numbers are crossed out.'' |
#Circle 5 and cross out every other multiple of 5. |
#Circle 5 and cross out every other multiple of 5. |
||
#Circle 7 and cross out every other multiple of 7. |
#Circle 7 and cross out every other multiple of 7. |
||
| + | #Circle the lowest number remaining after the previous step and cross out all its multiples. |
||
| − | #Keep going until every number has been either crossed out or circled and you basicly terrained all the composite numbers leaving just the prime numbers behind. |
||
| + | #Repeat Step 7 until every number has either been crossed out or circled. |
||
| − | This only works up to a certain point. If you find out on larger numbers, you may eventally run out of space to write. |
||
==References== |
==References== |
||
#https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes |
#https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes |
||
| + | |||
| + | {{Important Pages}} |
||
[[Category:Important Pages]] |
[[Category:Important Pages]] |
||
| + | [[Category:History of Prime Numbers]] |
||
Latest revision as of 11:36, 27 January 2018
In mathematics, the Sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους) is a way to obtain a list of all the prime numbers up until a given point.
The method works by methodically crossing out the composite numbers. The user will cross out the multiples of each prime, from 2 and up until the square root of the final number. The numbers that are not crossed off are prime numbers.
The algorithm is named after Eratosthenes of Cyrene, a Greek mathematician.
How to Use the Sieve
Prime Numbers - The Sieve of Eratosthenes
- List all the numbers from 1 to a certain number.
- Cross out 1, since it is neither prime nor composite.
- Circle 2 and cross out every other multiple of 2.
- Circle 3 and cross out every other multiple of 3.
Tip: Just add 6 to the first number, because all even numbers are crossed out. - Circle 5 and cross out every other multiple of 5.
- Circle 7 and cross out every other multiple of 7.
- Circle the lowest number remaining after the previous step and cross out all its multiples.
- Repeat Step 7 until every number has either been crossed out or circled.