Sieve of Eratosthenes - Maple Help

Home : Support : Online Help : Math Apps : Discrete Mathematics : Sieve of Eratosthenes

Sieve of Eratosthenes

Main Concept

 • A prime number is a natural number greater than $1$ that has no positive factor other than $1$ and itself.
 • A composite number is a natural number greater than $1$ that has at least one factor other than 1 and itself, in other words, is not prime.

Eratosthenes' Method of Finding Prime Numbers:

 1 Consider a grid of consecutive integers ranging from $2$ to $n$; we exclude $1$ from the grid because it is neither a prime nor composite number.
 2 Let $p$ be the first prime number, $2$.
 3 Mark off its multiples () ranging from ${p}^{2}$ to $n$ as composite numbers (mark $p$ itself as prime).
 4 Take $p$ to be the next unmarked number on the grid, mark it as prime and mark all of its multiples ranging from ${p}^{2}$ to $n$ as composite numbers.**
 5 Repeat step 4 until there are no more unmarked numbers in the grid less than or equal to $\sqrt{n}$.  For example, while  .
 6 Mark the remaining unmarked numbers in the grid greater than $\sqrt{n}$ as prime numbers.

**Note : Multiples less than ${p}^{2}$ can be disregarded because these numbers will have been marked off as multiples of lower primes. For example, when marking off the multiples of $5$, the numbers  and $20$ will already have been marked off as multiples of  and $2$ respectively. We thus starting marking with .

 Explore by changing the number of rows and columns. A grid of consecutive integers ranging from $2$ to $n$, where $n$ equals the the number of rows multiplied by the number of columns, will be generated.             Number of Rows          :  5678910111213141516171819202122232425                 Number of Columns     : 5678910111213141516171819202122232425                  Speed                          : SlowestSlowMediumFastFastest

 More MathApps