Crivello di Sundaram
# Crivello di Sundaram

Il crivello di Sundaram è un semplice algoritmo deterministico per trovare tutti i numeri primi fino a uno specifico valore intero. È stato sviluppato nel 1934 da S. P. Sundaram, uno studente indiano da Sathyamangalam.

## Algoritmo

Dalla lista degli interi fra 1 ed n vengono rimossi tutti i numeri della forma i + j + 2ij, dove:

* $i,j\in \mathbb {N} ,\ 1\leq i\leq j$
* $i+j+2ij\leq n$

I numeri rimasti vengono moltiplicati per due e ai risultati viene addizionato uno; si ottiene così la lista dei numeri primi dispari inferiori a 2n + 2.

## Spiegazione

La lista risultante contiene solo numeri dispari ed è necessario dimostrare che l'insieme dei numeri esclusi corrisponde esattamente all'insieme dei numeri dispari composti.

Un numero intero dispari viene escluso dalla lista risultante se e solo se il numero ha la forma 2(i + j + 2ij) + 1. Abbiamo:

    2(i + j + 2ij) + 1
    = 2i + 2j + 4ij + 1
    = (2i + 1)(2j + 1).

Così un intero dispari viene escluso se e solo se ha la forma (2i + 1)(2j + 1), cioè ha un fattore dispari. Perciò, la lista resultante deve essere composta solo da tutti i numeri primi dispari inferiori a 2n + 2.

