anyone take a shot at this

I've known about the Sieve of Eratosthenes for many years now. In fact I was inspired to try to work out a probablistic estimator of it's success a couple of months ago.

The simplest predictor is that the chance of an individual application of the sieve will find a non-prime in a collection of n numbers is

This doesn't work, because the population of numbers being sieved is progressively depleted of smaller primes as the test progresses. To improve it, you have to know (or guess) the number of primes - p_a - below the first number in the sample being tested - think Legendre Conjecture - and guess the number of primes in the sample being tested p_b.

As you work your way through p(a) the chance of finding a number divisible by a known prime goes up at the "k"th step by

(p_a + p_b)/(p_a + p_b - k)

It seemed to work fairly well when I tried it out in Excel, but I couldn't be bothered getting into my Linux partition and testing it in a respectable programming language over a respectable number of samples.

It generated a slightly conservative estimate for p_b when I tried it, but I'd need to run a lot more trials to say anything persuasive.

ote:

ote:

ial.math

be interested in what he posts - he wants to work it out for himself, which would probably need a brain transplant, or at least an implant, granting t hat nature seems to have drastically short-changed him in that department.

henes. Quite fun. There's a sample sieve code with the FreeBasic compiler . After some modification (it only finds the first million primes) it took my computer just 7.5 seconds to find the first 25 million primes. I'd for gotten how much fun such things could be. Of course, to find these primes, about 2 gigabytes of RAM for array space are needed... I'm sure the algori thm could be refined further by avoiding storage of multiples of two...

Oops. That obviously should be 1/p.

The population you have left goes down by the factor 1/(1-1/p).

b.

ote:

ote:

ial.math

be interested in what he posts - he wants to work it out for himself, which would probably need a brain transplant, or at least an implant, granting t hat nature seems to have drastically short-changed him in that department.

henes. Quite fun. There's a sample sieve code with the FreeBasic compiler . After some modification (it only finds the first million primes) it took my computer just 7.5 seconds to find the first 25 million primes. I'd for gotten how much fun such things could be. Of course, to find these primes, about 2 gigabytes of RAM for array space are needed... I'm sure the algori thm could be refined further by avoiding storage of multiples of two...

b.

I'm trying to understand your p_a and p_b.

From this list,

Considering the first primes less than 100, would p_b be 100? And p_a woul d be 25?

MingW C++ on Win32/64 seems useful. I use Borland's free command line tool s sometimes mostly because I grew up with Borland's Turbo Pascal and Turbo C++ as a kid (and I kind of miss the IDE editor's blue screen). Otherwise, on Linux, sudo apt-get install g++ would get you pretty much everything yo u need, right?

Cheers,

Michael

edial.math

t be interested in what he posts - he wants to work it out for himself, whi ch would probably need a brain transplant, or at least an implant, granting that nature seems to have drastically short-changed him in that department .

sthenes. Quite fun. There's a sample sieve code with the FreeBasic compil er. After some modification (it only finds the first million primes) it to ok my computer just 7.5 seconds to find the first 25 million primes. I'd f orgotten how much fun such things could be. Of course, to find these prime s, about 2 gigabytes of RAM for array space are needed... I'm sure the algo rithm could be refined further by avoiding storage of multiples of two...

p_b.

uld be 25?

Consider testing the Legendre Hypothesis that there's always at least one p rime between n^2 and (n+1)^2.

You only need to test for primes equal to or less than to n+2.

If n is 100 there are only 26 prime less that 102, which is p_a in this con text.

p_b is the number of primes between 10,000 and 10,201 (which is what you ar e trying to find out). It's 23. The roughest estimate is 202/ln(10100) whic h is 21.8.

ols sometimes mostly because I grew up with Borland's Turbo Pascal and Turb o C++ as a kid (and I kind of miss the IDE editor's blue screen). Otherwis e, on Linux, sudo apt-get install g++ would get you pretty much everything you need, right?

I'd be more likely to install a Fortran compiler - I got quite good with th at in the late 1960's.

MinGW is GCC, it'll do fortran too,