Incorrect algorithm in the prime numbers calculation benchmarks

[t-w]

If I understand correctly what the sieve.pas benchmarks tests are supposed to do (count primes up to a certain number, 8192 in the tests) - the algorithm used to calculate primes:

    fillchar(flags, sizeof(flags), true);
    count := 0;
    for i:=0 to size do
         if flags[i] then begin
             prime := i*2 + 3;
             k := prime + i;
             while (k <= size) do begin
                 flags[k] := false;
                 inc(k, prime);
             end;
             inc(count);
         end;

is not correct - it counts 1899 primes while up to 8192 (what is calculated), there are only 1028.

The corrected algorithm would be:

    fillchar(flags, sizeof(flags), true);
    flags[0] := false;
    flags[1] := false;
    count := 0;
    for i:=2 to size do
	if flags[i] then 
        { mark all multiplications of i as non-primes }
        begin
	    k := i + i;
	    while (k <= size) do
	    begin
		flags[k] := false;
		inc(k,i);
	    end;
	    inc(count);
	end;

as the inner part has to mark all multiplications of the current prime.
The other algorithm just does not mark many non-primes (it seems like an optimization to faster find the next prime - but it does not seem to be used correctly here...).

Also, in consequence, this cheats a bit on the result of the benchmark (by more than a 100 'ticks')...

[zbyti]

@t-w https://archive.org/details/byte-magazine-1981-09/page/n183/mode/2up

https://github.com/zbyti/a8-mad-pascal-bench-suite/blob/master/benchmarks/sieve1028.pas

https://github.com/zbyti/a8-mad-pascal-bench-suite/blob/master/benchmarks/sieve1899.pas

[t-w]

OK. I see. That algorithm does indeed something a bit different than it seemed at first glance - it does not store information about primes it finds (what could be easily added, eg in a second array), it just counts them, using the array in a more packed way.

Interesting, thanks for checking.