Sieve of Sundaram
Revision as of 10:23, 27 February 2020 by Science man 88 (talk | contribs) (Created page with "==Description== The '''Sieve of Sundaram''' is a sieve for a range of '''odd''' prime numbers.The sieve starts out listing the natural numbers <math>1</math>...")
Description
The Sieve of Sundaram is a sieve for a range of odd prime numbers.The sieve starts out listing the natural numbers to
like the following example (
)
Step 2
Then it finds all numbers of form ( fancy way of saying start at
and increase by
, for each not already eliminated
) and eliminates them (empty cells):
Step 3
Double each number and add one:
Optimization
- The equivalent in Step 2 above, of the Sieve of Eratosthenes starting the at the next prime squared, is starting at
for next index
Generalization
Looking close, if you know modular arithmetic, you'll note the remainder 1 forms the modular multiplicative group modulo 2. This generalizes to the modular multiplicative group mod any natural number.