Tag: sourceedit |
No edit summary Tag: sourceedit |
||
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== |
==How to Use the Sieve== |
Revision as of 12:35, 25 January 2017
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
- 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.