From: Mathieu Bouchard <matju@...>
Date: 2002-01-28T10:19:52+09:00
Subject: Re: looking for an example problem to demonstrate TaskMaster


On Fri, 25 Jan 2002, Chr. Rippel wrote:
> "Mathieu Bouchard" <matju@sympatico.ca> wrote in
> ....
> > finding primes from m to n, using the simplest non-stupid algorithm,
> > requires knowing all primes up to sqrt(n); that's primecount(sqrt(n)).
> > this is approx:
> > (0..sqrt(n)).integral {|x| 1/log(x) }
> > which is close to:
> > 1.1*sqrt(n)/log(n)
> Following this OT - a slightly better value in the long run is
>    sqrt(x) / (log(sqrt(x)) - 1 )  == sqrt(x) /(log(x)/log(2) -1)

Sorry, a typo of mine. I wanted to write 1.1*sqrt(n)/log(sqrt(n)).

You wanted to write /2, not /log(2).

The -1 may improve a bit, but is asymptotically irrelevant, and this is
already a very rough approximation; the true logarithmic integral is a
bigger and much more precise formula, but it includes an infinite series.

________________________________________________________________
Mathieu Bouchard                   http://hostname.2y.net/~matju