No, it is not a proper sieve of Eratosthenes. No testing of remainders is involved in the sieve of Eratosthenes algorithm, Wikipedia is real clear on this I think. :) The whole point to it is to avoid the trial divisions, to get the primes for free, without testing.
How? By generating their multiples, from every prime that we identify, in ascending order one after another.
The multiples of a prime p are: 2p, 2p + p, 2p + p + p, ...
The odd multiples of a prime p are: 3p, 3p + 2p, 3p + 2p + 2p, ...
As we enumerate them, we mark them in the sieve array. Some will be marked twice or more, e.g. 15 will be marked for 3 and for 5 (because 3 * 5 == 5 * 3). Thus, we can start enumerating and marking from p2:
for( i=3; i*i < n; i += 2 )
if( !sieve[i] ) // if `i` is not marked as composite
for( j = i*i; j < n; j += 2*i )
{
sieve[j] = 1; // 1 for composite, initially all are 0s
}
The key to the sieve is this: we don't store the numbers in the array. It is not an array of INT
s; it is an array of 1-bit flags, 0 or 1 in value. The index of an entry in the sieve array signifies the number for which the sieve holds its status: marked, i.e. composite, or not yet marked, i.e. potentially prime.
So in the end, all the non-marked entries signify the primes. You will need to devise an addressing scheme of course, e.g. an entry at index i
might correspond to the number a + 2*i
where a
is the odd start of the range. Since your range starts at some offset, this scheme is known as offset sieve of Eratosthenes. A skeleton C implementation is here.
To minimize the memory use, we need to treat our array as a bit array. In C++ e.g. it is easy: we declare it as vector<bool>
and it is automatically bit-packed for us. In C we'll have to do some bit packing and unpacking ourselves.
A word of advice: don't go skimpy on interim variables. Name every meaningful entity in your program. There shouldn't be any (max-min)/2
in your code; but instead define width = max - min
and use that name. Leave optimizations in the small to the compiler. :)
To your first question: it's a scope thing. Your code is equivalent to
if (max<=UINT_MAX)
{ unsigned int range[(max-min)/2]; } // note the curly braces!
else if (max<=ULONG_MAX)
{ unsigned long int range[(max-min)/2]; }
else if (max<=ULLONG_MAX)
{ unsigned long long int range[(max-min)/2]; }
so there's three range
array declarations here, each in its own scope, inside the corresponding block. Each is created on entry to its enclosing block ({
) and is destroyed on exit from it (}
). In other words, it doesn't exist for the rest of your prime
function anymore. Practically it means that if you declare your variable inside an if
block, you can only use it inside that block (between the corresponding braces {
and }
).