Reducing memory usage when designing a sieve of eratosthenes in C

Question

I'm trying to design a sieve of eratosthenes in C but I've run into two strange problems which I can't figure out. Here's my basic program outline. Ask users to set a range to display primes from. If the range minimum is below 9, set the minimum as 9. Fill an array with all odd numbers in the range.

1) I'm trying to reduce memory usage by declaring variable size arrays like so:

    if (max<=UINT_MAX)
       unsigned int range[(max-min)/2];
    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];

Why doesn't this compile? Variables min and max are declared as ints earlier and limits.h is included. I've commented out the selection structure and just declared unsigned long long int range[(max-min)/2]; for now which compiles and works for now.

2) My code runs but it sometimes marks small primes as non primes.

#include<stdio.h>
#include<limits.h>

void prime(int min, int max)
{
    int i, f=0;
    //declare variable size array
    /*if (max<=(int)UINT_MAX)
       unsigned int range[(max-min)/2];
   else if (max<=(int)ULONG_MAX)
         unsigned long int range[(max-min)/2];
    else if (max<=(int)ULLONG_MAX)*/
         unsigned long long int range[(max-min)/2];
    //fill array with all odd numbers
    if (min%2==0)
    {
        for (i=min+1;i<=max;i+=2)
        {
            range[f]=i;
            f+=1;
        }
    }
    else
    {
        for (i=min;i<=max;i+=2)
        {
            range[f]=i;
            f+=1;
        }
    }
    //assign 0 to cell if divisible by any number other than itself
    for (i=3;i<=sqrt(max);++i)
    {
        for (f=0;f<=((max-min)/2);f++)
        {
            if (range[f]%i==0 && f!=i)
                range[f]=0;
        }
    }
    //troubleshoot only: print full range
    for (f=0;f<=((max-min)/2);f++)
    {
            printf("ALL: %d / %d\n", f, range[f]);
    }    
    //display all primes
    if (min==9) /*print primes lower than 9 for ranges where min<9*/
            printf("2\n3\n5\n7\n");
    for (f=0;f<=((max-min)/2);f++) /*print non 0 numbers in array*/
    {
        if (range[f]!=0)
            printf("%d\n", range[f]);
    }
}
int main(void)
{
    int digits1, digits2;
    printf("\n\n\nCalculate Prime Numbers\n");
    printf("This program will display all prime numbers in a given range. \nPlease set the range.\n");
    printf("Minimum: ");
    scanf("%d", &digits1);
    if (digits1<9)
       digits1=9;
    printf("Maximum: ");
    scanf("%d", &digits2);
    printf("Calculating...");
    printf("All prime numbers between %d and %d are:\n", digits1, digits2);
    prime(digits1, digits2);
    getchar();
    getchar();
}

For example, if digits=1 and digits2=200 my program outputs all primes between 1 and 200 except 11 and 13. 11 and 13 are sieved out and I can't figure out why this happens to more and more low numbers as digits2 is increased.

3) Finally, is my sieve a proper sieve of eratosthenes? It kind of works but I feel like there is a more efficient way of sieving out non primes but I can't figure out how to implement it. One of my goals for this program is to be as efficient as possible. Again, what I have right now is:

    //assign 0 to cell if divisible by any number other than itself
    for (i=3;i<=sqrt(max);++i)
    {
        for (f=0;f<=((max-min)/2);f++)
        {
            if (range[f]%i==0 && f!=i)
                range[f]=0;
        }
    }

Thanks for reading all of that! I'm sorry for posting yet another sieve of eratosthenes related question and thank you in advance for the help!

Answer 1

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 p²:

  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 INTs; 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 } ).

Answer 2

Q1: you can not declare a symbol (here: range) twice in the same scope. It is not exactly your problem but you are trying to do this: you declare range within the if scope and it is not visible outside.