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

I passi dell'algoritmo per n = 100.

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\le i\le j$
• $i+j+2ij\le 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.

Bibliografia

• Template:Cita libro
• Template:Cita libro
• Template:Cita pubblicazione
• Template:Cita conferenza
• Template:Cita pubblicazione

Voci correlate

• Crivello di Eratostene
• Crivello di Atkin
• Teoria dei crivelli