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
[modifica | modifica wikitesto]
Dalla lista degli interi fra 1 ed n vengono rimossi tutti i numeri della forma i + j + 2ij, dove:
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
[modifica | modifica wikitesto]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
[modifica | modifica wikitesto]- ^ V. Ramaswami Aiyar, Sundaram's Sieve for Prime Numbers, in The Mathematics Student, vol. 2, n. 2, 1934, p. 73, ISSN 0025-5742.
- ^ G., Curiosa 81. A New Sieve for Prime Numbers, in Scripta Mathematica, vol. 8, n. 3, 1941, p. 164.
Bibliografia
[modifica | modifica wikitesto]- (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).
