Crivello di Sundaram

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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]

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 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]

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

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica