Crivo de Legendre

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa
Question book.svg
Este artigo ou secção não cita fontes confiáveis e independentes (desde maio de 2014). Ajude a inserir referências.
O conteúdo não verificável pode ser removido.—Encontre fontes: Google (notícias, livros e acadêmico)
Translation Latin Alphabet.svg
Este artigo ou seção está a ser traduzido de «Criba de Legendre» na Wikipédia em castelhano. Ajude e colabore com a tradução.

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[editar | editar código-fonte]

A ideia central do método é expressada pela seguinte identidade, algumas vezes referida como Identidade de Legendre:

Onde A é um conjunto de inteiros, P é um produto de primos distintos, é a função de Möbius, é o conjunto de inteiros em A divisível por d, e S(A, P) é definido como:

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:

(onde é 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 (onde é 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 nestes casos especiais, podem ser usado para limitar usando a expressão

a qual é uma implicação clara da definição de .

Problemas[editar | editar código-fonte]

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[editar | editar código-fonte]

Portal A Wikipédia tem o portal:
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.