Walter Bright wrote:
> bearophile wrote:
>> Walter Bright:
>>> Are you sure? What's the mistake in the code?
>>
>> This is the code in the Overview, it prints 1899:
>> http://codepad.org/lzRtggEL
>>
>> This is the code I have suggested in bugzilla, it prints 1027:
>> http://ideone.com/D9ZqQ
>>
>> Wolfram Alpha says they are 1027 (I have left out the last number because Alpha uses a closed interval)
>> http://www.wolframalpha.com/input/?i=primes+in+2+..+8190
> 
> 
> It's been printing 1899 primes since the 80's. Just for fun, google [sieve of eratosthenes 1899 primes]

A small observation: count +=1 is performed for i = 0, hmmm...

Walter Bright:
> It's been printing 1899 primes since the 80's. Just for fun, google [sieve of eratosthenes 1899 primes]

You are right, isn't life fun? :-)
But there is little double the result is:

>>> pr = (x for x in xrange(2,8191) if all(x % i for i in xrange(2,x)))
>>> len(list(pr))
1027

Bye,
bearophile

Walter Bright <newshound1@digitalmars.com> wrote:

> bearophile wrote:
>> Walter Bright:
>>> Are you sure? What's the mistake in the code?
>>  This is the code in the Overview, it prints 1899:
>> http://codepad.org/lzRtggEL
>>  This is the code I have suggested in bugzilla, it prints 1027:
>> http://ideone.com/D9ZqQ
>>  Wolfram Alpha says they are 1027 (I have left out the last number because Alpha uses a closed interval)
>> http://www.wolframalpha.com/input/?i=primes+in+2+..+8190
>
>
> It's been printing 1899 primes since the 80's. Just for fun, google [sieve of eratosthenes 1899 primes]

I wonder if that has to with there being 1899 primes in 3..16384.
http://www.wolframalpha.com/input/?i=primes+in+2+..+16384

An implementation of just that is what I found most of the time,
owing back to "A High-Level Language Benchmark" by Jim Gilbreath,
in BYTE Magazine, september 1981, pages 180-198.

Sadly, I cannot seem to find a version of the original article
online. Anyone know of one, that we may get to the bottom of this?

-- 
Simen

Ary Borenszweig:
> A small observation: count +=1 is performed for i = 0, hmmm...

It lacks unit tests. A basic unit testing can catch that bug.
Recently I have ready a quote: "If it has no unit tests then it's broken". Experience shows me that this is more often true than false.

Bye,
bearophile

On Fri, 14 May 2010 19:37:58 -0400, Walter Bright <newshound1@digitalmars.com> wrote:

> R.Tenton wrote:
>> At the very bottom of http://digitalmars.com/d/2.0/overview.html
>> there is an example implementation of the Eratosthenes' sieve.
>> That code is broken! It counts 1899 prime numbers, while there are only 1028
>> primes in the interval [1,8191]!
>
> Are you sure? What's the mistake in the code?

I think the issue is that the expectation is that array index x represents the number x.  But it doesn't seem that way.

the i + i + 3 is very odd indeed.

If we consider each index, it means the first element represents 0 + 0 + 3 = 3;
The second element represents 1 + 1 + 3 = 5;
The third element represents 2 + 2 + 3 = 7;

So it looks like the numbers represented by the array actually go from 3 to (8190 + 8190 + 3) or 16383.

According to Wolfram Alpha, the number of primes in that list is 1899

http://www.wolframalpha.com/input/?i=primes+in+3+..+16383

A comment to explain the representation of the array may be good.

-Steve

Steven Schveighoffer wrote:
> A comment to explain the representation of the array may be good.

Well, I did add your explanation to the bugzilla report! Thanks.