[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
=========================================================================