|
In [[matematica]], il '''crivello di Legendre''' è il metodo più semplice nella moderna [[teoria dei crivelli]]. Applica il concetto del [[Crivellocrivello di Eratostene]] per trovare limiti inferiori e superiori alla stima della quantità di [[numero primo|numeri primi]] entro un dato intervallo di interi. Poiché è una semplice estensione dell'idea di Eratostene, è a volte citato come '''crivello di Legendre-Eratostene'''.
==L'identità di Legendre==
:<math>S(A,P)= \sum_{a\in A}\sum_{d|a;d|P} \mu(d) =\sum_{d|P}\mu(d)|A_d|</math>
dove ''<math>A''</math> è un intervallo di interi, ''<math>P''</math> è il prodotto di numeri primi distinti, <math>\mu</math> è la [[funzione di Möbius]], <math>A_d</math> è l'insieme degli interi ''<math>A''</math> divisibili per ''<math>d''</math>, e ''<math>S(A, P)''</math> è definito come:
:<math>S(A, P) = |\{n: n \in A, (n, P) = 1\}|,</math>
ossia il numero degli interi in ''<math>A''</math> che non hanno fattori comuni con ''<math>P''</math>.
Nella maggior parte dei casi ''<math>A''</math> sono tutti gli interi minori o uguali di qualche numero ''<math>X''</math>, ''<math>P''</math> è il prodotto di tutti i primi minori o uguali a qualche intero ''<math>z < <X''</math>, per cui l'identità di Legendre diviene:
{|
|}
(dove <math>\lfloor x \rfloor</math> denota la [[parte intera]] di ''<math>x''</math>). In questo esempio il fatto che l'identità di Legendre sia derivata dal crivello di Eratostene è chiaro: il primo termine è il numero di interi minore di ''<math>X''</math>, il secondo rimuove i multipli di tutti i primi, il terzo recupera i prodotti di due primi (che sono stati scartati per errore) e così via finché tutte le <math>2^{\pi(z)}</math> (dove <math>\pi(z)</math> denota il numero di primi minori di ''<math>z''</math>) combinazioni di primi sono state coperte.
Una volta che <math>S(A,P)</math> è stato calcolato per questo caso particolare, può essere usato per ottenere un limite superiore per <math>\pi(X)</math> usando l'espressione
:<math>S(A,P) \geq \pi(X) - \pi(z) - 1,</math>
che segue immediatamente dalla definizione di <math>S(A,P)</math>.
| 