Crivo de Legendre
# Crivo de Legendre

Em Matemática, o crivo de Legendre é o mais simples método na teoria dos crivos. Este aplica o conceito do crivo de Eratóstenes para encontrar estimativas superiores e inferiores ao número de primos dado um conjunto de inteiros. Como é uma simples extensão da ideia usada no crivo de Eratostenes, este método de crivo é também chamado por vezes crivo de Eratóstenes-Legendre.

## Identidade de Legendre

A ideia central do método é expressada pela seguinte identidade, algumas vezes referida como Identidade de Legendre:
    $S(A,P)=\sum _{a\in A}\sum _{d|a;d|P}\mu (d)=\sum _{d|P}\mu (d)|A_{d}|$
Onde A é um conjunto de inteiros, P é um produto de primos distintos, $\mu$ é a função de Möbius, $A_{d}$ é o conjunto de inteiros em A divisível por d, e S(A, P) é definido como:
    $S(A,P)=|\{n:n\in A,(n,P)=1\}|$
Portanto S(A,P) é a quantidade de números em A sem fatores comuns a P.
Nota-se que em o caso mais típico, A é o conjunto de todos os inteiros menores ou iguais a um número real X, P é o produto de todos os primos menores ou iguais a algum inteiro z < X, assumindo isto, a identidade de Legendre ficaria desta forma:
| $S(A,P)$ | $=\sum _{d|P}\mu (d)\left\lfloor {\frac {X}{p_{1}}}\right\rfloor$ |
| | $=[X]-\sum _{p_{1}<z}\left\lfloor {\frac {X}{p_{1}}}\right\rfloor +\sum _{p_{1}<p_{2}<z}\left\lfloor {\frac {X}{p_{1}p_{2}}}\right\rfloor -\sum _{p_{1}<p_{2}<p_{3}<z}\left\lfloor {\frac {X}{p_{1}p_{2}p_{3}}}\right\rfloor +\cdots$ |
(onde $\lfloor X\rfloor$ é a função parte inteira). Neste exemplo, o fato de que o crivo de Legendre se derive do crivo de Eratostenes é evidenciado: a primeira parcial é o número de inteiros menores que X, a segunda parcial remove os múltiplos de todos os primos, a terceira acrescenta os múltiplos de dois primos (os quais estão sendo "descontados" porque foram "riscados duas vezes"), e assim sucessivamente todas as $2^{\pi (z)}$ (onde $\pi (z)$ é o número de primos menores que z) combinações de primos são consideradas pelo crivo de Legendre. Entende-se ainda que dado um limite no conjunto, a última parcial será a final.
Uma vez tendo sido calculados $S(A,P)$ nestes casos especiais, podem ser usado para limitar $\pi (X)$ usando a expressão
    $S(A,P)\geq \pi (X)-\pi (z)+1$
a qual é uma implicação clara da definição de $S(A,P)$.

## Problemas

Desafortunadamente, o crivo de Legendre possui um problema com a parte fracionária das diferentes parciais, as quais acumulam-se em uma parcial de erro (isto é, parciais em notação O) demasiado grande, a qual diz que o crivo de Legendre dá limites ruins em muitos casos. Por esta razão, este crivo nunca é usado na prática, sendo sempre melhorado por outras técnicas de crivagem tais como a do crivo de Brun e a do crivo de Selberg. Contudo, dado que estes crivos mais poderosos são extensões das ideias básicas do crivo de Legendre, este método de crivagem torna-se útil para entender como funcionam os crivos.

## Veja também

* Crivo de Eratóstenes
* Crivo de Selberg
* Número primo
* Teoria dos crivos
* Portal da matemática