Wednesday, July 11, 2018

The Sieve of Eratosthenes

Definition 1. A prime is an integer greater than 1 that is only divisible by 1 and itself.

Example. The integers 2, 3, 5, 7, 11 are prime integers. Note that any integer greater than 1 that is not prime is said to be a composite number. We now present the sieve of Eratosthenes.

The Sieve of Eratosthenes is an ancient method of finding prime numbers up to a specified integer. This method was invented by the ancient Greek mathematician Eratosthenes. There are several other methods used to determine whether a number is prime or composite. We first present a lemma that will be needed in the proof of several theorems.

Lemma 1. Every integer greater than one has a prime divisor.

Proof. We present the proof of this Lemma by contradiction. Suppose that there is an integer greater than one that has no prime divisors. Since the set of integers with elements greater than one with no prime divisors is nonempty, then by the well ordering principle there is a least positive integer n greater than one that has no prime divisors. Thus n is composite since n divides n. Hence $n = ab$ with $1 < a < n$ and $1 < b < n$. Notice that $a < n$ and as a result since n is minimal, a must have a prime divisor which will also be a divisor of n.

Theorem 1. If n is a composite integer, then n has a prime factor not exceeding $\sqrt{n}$.

Proof. Since n is composite, then $n = ab$, where a and b are integers with $1 <a \le b < n $. Suppose now that $a > \sqrt{n} $, then $\sqrt{n} <a \le b $  and as a result $ab > \sqrt{n} \sqrt{n}= n$. Therefore $a \le \sqrt{n}$. Also, by Lemma 1, a must have a prime divisor $a_1$ which is also a prime divisor of n and thus this divisor is less than $a_1 \le  a \le \sqrt{n} $.

We now present the algorithm of the Sieve of Eratosthenes that is used to determine prime numbers up to a given integer.
  1. Write a list of numbers from 2 to the largest number n you want to test. Note that every composite integer less than n must have a prime factor less than $\sqrt{n}$. Hence you need to strike off the multiples of the primes that are less than $\sqrt{n}$
  2. Strike off all multiples of 2 greater than 2 from the list . The first remaining number in the list is a prime number.
  3. Strike off all multiples of this number from the list.
  4. Repeat the above steps until no more multiples are found of the prime integers that are less than $\sqrt{n}$

CLOSE to read The Sieve of Eratosthenes !

0 komentar

Post a Comment

Equation Calculator Site