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.^[1]^[2]

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.

Note

^ V. Ramaswami Aiyar, Sundaram's Sieve for Prime Numbers, in The Mathematics Student, vol. 2, n. 2, 1934, p. 73, ISSN 0025-5742 (WC · ACNP).
^ G., Curiosa 81. A New Sieve for Prime Numbers, in Scripta Mathematica, vol. 8, n. 3, 1941, p. 164.

Bibliografia

(EN) C. Stanley Ogilvy e John T. Anderson, Excursions in Number Theory, Dover Publications, 1988, pp. 98–100, 158, ISBN 0-486-25778-9.
(EN) Ross Honsberger, Ingenuity in Mathematics, New Mathematical Library #23, Mathematical Association of America, 1970, pp. 75, ISBN 0-394-70923-3.
(EN) N. Movshovitz-Hadar, Stimulating Presentations of Theorems Followed by Responsive Proofs, in For the Learning of Mathematics, vol. 8, n. 2, 1988, pp. 12-19.
(EN) Elisabetta Ferrando, Ph.D. theses (PDF), Abductive processes in conjecturing and proving, Purdue University, 2005, pp. 70-72. URL consultato il 27 aprile 2014 (archiviato dall'url originale il 7 maggio 2016).
(EN) Andrew Baxter, Sundaram’s Sieve, in Topics from the History of Cryptography, MU Department of Mathematics. URL consultato il 27 aprile 2014 (archiviato dall'url originale il 12 agosto 2011).