[obm-l] Re: [obm-l] N�meros primos em um intervalo

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

On Wed, May 28, 2003 at 08:42:16PM -0300, Victor Luiz wrote:
> Ol� pessoal, eu gostaria de saber se existe alguma "f�rmula m�gica" mesmo
> que seja complicada pra calcular o n�mero de n�meros primos em um intervalo.
> Esses dias eu vi um exerc�cio que dizia mais ou menos "Quantos n�meros
> primos naturais existem no intervaldo de 1 a 500?" e por isso eu quis saber
> se existe alguma maneira mais pr�tica de calcular do que ficar tentando
> n�mero por n�mero.

Seja f(n) o n�mero de primos at� n; assim f(10) = 4, f(11) = 5.
O teorema dos n�meros primos d� o valor *aproximado* para f(n):

f(n) ~= n/log(n)

onde o logaritmo � na base e, claro; log na base 10 s� existe
em tabelas de logaritmos de h� 100 anos atr�s e em alguns livros
de ensino m�dio.

O valor certo de f(500) � 95; a f�rmula d� 80.45559625.
Temos f(50000) = 5133 e a f�rmula d� 4621.166784.

Uma aproxima��o bem melhor � dada por

Li(x) = integral_0^x dt/log(t)

onde devemos tomar o valor principal desta integral:

Li(500) = 101.7938725
Li(50000) = 5166.546764

Para calcular f(500) *exatamente* voc� n�o precisa calcular
todos os primos at� 500 mas sempre d� um certo trabalho...
 
> PS: N�o sei se isso acontece com voc�s mas comigo os e-mails chegam na lista
> com um atraso bem grande, por exemplo esse �ltimo que eu mandei sobre o
> delta foi enviado �s 11:35 mas s� chegou �s 13:25... N�o � nada demais eu s�
> quero saber se aqui no meu computador est� com problema ou � assim mesmo.

O majordomo pode demorar um pouco para processar o que deve
mas 2 horas parece um pouco demais. Para entrar no arquivo
na minha home page demora bem mais, ele s� � refrescado de noite.
Por falar em arquivo, usem mais o que fica em

http://www.mail-archive.com/obm-l@mat.puc-rio.br

que funciona melhor do que o meu.

[]s, N.
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================