# Difference between revisions of "Sieve of Sundaram"

(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>...") |
m (→Optimization) |
||

Line 71: | Line 71: | ||

==Optimization== | ==Optimization== | ||

− | + | The equivalent in Step 2 above, of the [[Sieve of Eratosthenes]] starting the at the next prime squared, is starting at <math>2c^2+2c</math> for next index <math>c</math> | |

==Generalization== | ==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. | 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. |

## Revision as of 10:24, 27 February 2020

## 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.