Two Sieves for Prime Numbers (UMAP)

In this module two algorithms for allocating prime natural numbers are presented: 1) Sundaram's Sieve based upon a table of arithmetic progressions; 2) Mann's-and-Shank's Sieve based upon Pascal's triangle. Through an inductive study of particular cases it leads to the generalizations followed by complete proofs. Students learn: 1) to distinguish between prime and composite natural numbers; 2) to apply various algorithms for determining primeness; 3) to reconstruct Sundaram's Sieve and Mann's-and-Shank's Sieve; 4) to understand the logic underlying these two sieves.

Table of Contents:

SUNDARAM'S SIEVE
Introduction
Sundaram's Sieve
Ingenuity Indeed
Definition of a Prime Number
An Algorithm for Allocating Primes
Back to Sundaram's Sieve
Validity of Sundaram's Sieve
Some Pedagogical Comments

MANN'S AND SHANK'S SIEVE
Introduction
A Special Matrix
The General Form of the nth Row
Elements Divisible by n in the nth Row
Distinction Between Two Types of Matrix-Columns
An Algorithm for Allocating Primes
Validating the Algorithm

REFERENCES

TEST

SOLUTIONS TO TEST ITEMS