How do I get this to compile in Visual Studio 2005?

I am taking my first programming course at my university this semester and I wrote my first C program, a prime number finder, using Visual Studio 2005. Unfortunately, it compiles only in GCC and not in Visual Studio 2005, but GCC is used by the grader to compile assignments so I guess the fact that it compiles in GCC is a good thing. I am using things that have not been mentioned in lecture, but writing it was fun. Anyway, I would like to get it to compile in Visual Studio 2005, so I can run it on Windows. Here is the program:

// prime.c
// Sept 26, 2007.
// <Identifying Information Removed>
// Program to find prime numbers

#include <stdio.h>

int main (void)
{

    int len, i, j;

    printf ("Find prime numbers smaller than \n");
    scanf("%i", &len);

    //Prime Array
    short arr [len];

    //Initialize Prime Array
    for ( i = 0; i < len; i++ )
    {

        arr[i] = 0;

    }

    //Set 2 to prime
    arr[1] = 1;

    //Check each number for primiality, starting with 3
    //Skip every other number in array
    //Also, set all composites to 0
    for ( i = 3 ; i < len; i+=2 )
    {
        //Set Number to Prime
        arr[i - 1] = 1;

        //Loop through all known prime numbers less than
        //the square root of the number being considered
        for ( j = 3; j < i / j; j+=2 )
        {
            if (i % j == 0 && arr[j - 1] == 1)
            {
                //Set position in array to composite
                arr[i - 1] = 0;
            }
        }

    }

    //Loop through Prime Array and Output Primes
    for ( i = 0; i < len; i++ )
    {

        if (arr[i] == 1)
        {

            printf("Number %i is a prime number\n", i + 1);

        }

    }

    return 0;

}

I think that Visual Studio does not like the variable array and for some reason thinks that the variables are out of scope. Here is what Visual Studio is telling me:

1>------ Build started: Project: prime, Configuration: Release Win32 ------
1>Compiling...
1>prime.c
1>.\prime.c(14) : warning C4996: 'scanf': This function or variable may be unsafe. Consider using scanf_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
1>        C:\Program Files\Microsoft Visual Studio 8\VC\include\stdio.h(295) : see declaration of 'scanf'
1>.\prime.c(17) : error C2143: syntax error : missing ';' before 'type'
1>.\prime.c(23) : error C2065: 'arr' : undeclared identifier
1>.\prime.c(23) : error C2109: subscript requires array or pointer type
1>.\prime.c(28) : error C2109: subscript requires array or pointer type
1>.\prime.c(36) : error C2109: subscript requires array or pointer type
1>.\prime.c(42) : error C2109: subscript requires array or pointer type
1>.\prime.c(45) : error C2109: subscript requires array or pointer type
1>.\prime.c(55) : error C2109: subscript requires array or pointer type
1>Build log was saved at "file://c:\Documents and Settings\Richard\My Documents\Visual Studio 2005\Projects\prime\prime\Release\BuildLog.htm"
1>prime - 8 error(s), 1 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

Does anyone have any ideas?

If you are compiling this program as c and not c++ the problem is that c requires all variable declarations to occur at the beginning (prior to the first statement (executable code)) of any stack frame, and local variables that are an array must be of a constant size as they are allocated from the stack at compile/link time.

So change the code to the following

// The following define will supress the warning
#define _CRT_SECURE_NO_DEPRECATE

#include <stdio.h>

int main (void)
{

    int len, i, j;
    short* arr = NULL;
    printf ("Find prime numbers smaller than \n");
    scanf("%i", &len);

    //Prime Array
    arr = (short*)malloc(len * sizeof(short));

    ........


    free(arr);
    return 0;
}



Chris

Shining Arcanine wrote:

short arr [len];

There's your problem line.  You can't declare an array with a variable size.  'len' must be a constant.  Obviously, that's not what you want to do here, so your other option is to allocate the array on the heap (malloc/new/whatever).

I'm surprised GCC accepts this.

pacman31, thanks. I will try that in Visual Studio when I get home.

wkempf wrote:



Shining Arcanine wrote: short arr [len];

There's your problem line.  You can't declare an array with a variable size.  'len' must be a constant.  Obviously, that's not what you want to do here, so your other option is to allocate the array on the heap (malloc/new/whatever).

I'm surprised GCC accepts this.

The book assigned for the course, Programming in C by Stephen G. Kochan (ISBN 0-672-32666-3), says on page 116 that it is possible. I have not gotten to the chapter on dynamic memory yet so I assumed that the book knew best.

Shining Arcanine wrote:

pacman31, thanks. I will try that in Visual Studio when I get home.

wkempf wrote:  Shining Arcanine wrote: short arr [len]; There's your problem line.  You can't declare an array with a variable size.  'len' must be a constant.  Obviously, that's not what you want to do here, so your other option is to allocate the array on the heap (malloc/new/whatever). I'm surprised GCC accepts this.

The book assigned for the course, Programming in C by Stephen G. Kochan (ISBN 0-672-32666-3), says on page 116 that it is possible. I have not gotten to the chapter on dynamic memory yet so I assumed that the book knew best.

wow, ok i have not used my book on ANSI C for a long while but I think that behavior depends on the compiler and the way it generates the code.

in general I'd say that if the book told you to code that way then the book is wrong.

not a recomemnded practice for C.

the OOP type languges allow for "on the fly" creation of objects.

C is a static language, to create data on the fly you have to allocate storage.


for the construct you described to work the compiler would have to
see the variable use and generate the maloc call for you...
that does not sound like ANSI C to me.
how long has the book author been coding for ?

I have written a more complex version of the above program (to use individual bits to represent numbers rather than short integers) and I am banging my head over what is happening. It compiles in GCC, but does not give any output. It compiles in Visual Studio 2005 and executing it in Visual Studio causes Visual Studio to report that it detected heap corruption. When debugging, I see the break statement on line 103 cause the program to go to line 98 when n = 33 instead of breaking the parent loop. I noticed that m needs to be incremented by 2 with each iteration of the loop and that should not happen thanks to the break statement, so I added line 102, which caused the conditional on line 98 to evaluate as false causing the parent loop to terminate in that instance. I commented it out for purposes of demonstrating that the break on line 103 is acting as a goto statement. If I let the program run with line 102 uncommented (or commented for that matter), I get heap corruption, even through everything should be working without a problem.

Here is the code:

// prime.c
// Sept 27, 2007.
// <personal information removed>
// Program to find prime numbers

#include <stdio.h>

int main (void)
{

    int len, b_num, num;

    unsigned int i, j;

    unsigned short * arr = NULL;

    printf ("Find prime numbers smaller than \n");
    scanf("%i", &len);

    b_num = len / sizeof(short) / 8;

    arr = (unsigned short*)malloc(b_num);

    bin_arr_prime_fill(arr, b_num);

    //Loop through Prime Array and Output Primes
    for ( i = 0, num = 1; i < b_num ; i++ )
    {

        for ( j = 0x8000; j > 0; j >>= 1, num++ )
        {

            if (arr[i] & j == j)
            {

                printf("Number %i is a prime number\n", num);

            }

         }

    }

    free(arr);

    return 0;

}

int bin_init_array (unsigned short arr[], int len)
{
             
    int i;
         
    for ( i = 0; i < len; i++ )
    {

        arr[i] = 0;

    }

    return 0;

}
 
int bin_arr_prime_fill (unsigned short arr[], int len)
{

    unsigned int i, j, k, l, n, m;
     
    bin_init_array(arr, len);
       
    //Set 2 to prime
    arr[0] = 0x6A28;

    for ( i = 1; i < len; i++ )
    {
   
        //j has a binary 1 where the number is in the array
        //n is the number in an int
        for ( j = 0x8000, n = 16 * i + 1; j > 0; j >>= 2, n+=2)
        {
   
            //Set Number to Prime
            arr[i] += j;

            //k is the word whose numbers are being considered
            //by the inside loop
            //m is the divisor, starting with 3
            for (k = 0, m = 3, l = 0x2000; k < i / 2 + 1; k++)
            {
   
                //Checks if any number in the word is a factor
                // of the number being tested
                for (  ; m <= n / m; l >>= 2, m += 2 )
                {
       
                    if ((arr[k] & l) == l && (n % m) == 0)
                    {
         
                        arr[i] -= j;
                        //m += 2;
                        break;
             
                    }
               
                }

                l = 0x8000;
         
            }
     
        }
   
    }

    return 0;

}

Does anyone have any idea what is happening?

Pacman1, I tried what you suggested and the program now compiles and executes without a program in Visual Studio 2005. Thankyou.

figuerres wrote:



Shining Arcanine wrote: pacman31, thanks. I will try that in Visual Studio when I get home. wkempf wrote:  Shining Arcanine wrote: short arr [len]; There's your problem line.  You can't declare an array with a variable size.  'len' must be a constant.  Obviously, that's not what you want to do here, so your other option is to allocate the array on the heap (malloc/new/whatever). I'm surprised GCC accepts this. The book assigned for the course, Programming in C by Stephen G. Kochan (ISBN 0-672-32666-3), says on page 116 that it is possible. I have not gotten to the chapter on dynamic memory yet so I assumed that the book knew best.

wow, ok i have not used my book on ANSI C for a long while but I think that behavior depends on the compiler and the way it generates the code.

in general I'd say that if the book told you to code that way then the book is wrong.

not a recomemnded practice for C.

the OOP type languges allow for "on the fly" creation of objects.

C is a static language, to create data on the fly you have to allocate storage.


for the construct you described to work the compiler would have to
see the variable use and generate the maloc call for you...
that does not sound like ANSI C to me.
how long has the book author been coding for ?

I have no idea, but my professor made the author's book the class textbook.

Edit: I did a google search and found the following on the barnes and noble website; apparently he is a fairly prolific writer:

http://search.barnesandnoble.com/booksearch/results.asp?z=y&ATH=Stephen+G.+Kochan

Quite frankly, the program is a bit of a mess.

• Add #include <stdlib.h> at the top because it complains malloc is undefined (which still compiles in C but isn't exactly a good idea).
• Your invocation to malloc is wrong. You seem to want to create an array of b_num elements but you're creating one of b_num bytes, which is only b_num / 2 shorts (heap corruption cause 1).
• The function bin_init_array is not necessary, you can use calloc to allocate and initialize to zero in one go (also helps preventing the previous problem):
  arr = (unsigned short*)calloc(b_num, sizeof(unsigned short));
• b_num = len / sizeof(short) / 8;
  I'm not entirely sure how you got to this calculation (I can't really tell what half of the algorithm is doing), but that will yield 0 for any value of len lower than 16. Since you are always accessing the first element (arr[0] = 0x6A28;) that's heap corruption cause number 2.
• if( arr[i] & j == j )
  That line needs extra () because of operator precedence: if( (arr[i] & j) == j )
• You've got a lot of signed/unsigned mismatches in the code.

When I correct all those problems (and use a value of len >= 16) it doesn't crash anymore. It doesn't compute the prime numbers correctly either though (it returns numerous non-primes). Since I have no idea how this algorithm is trying to achieve what it's supposed to be doing I can't really help any further.

Sven Groot wrote:

Quite frankly, the program is a bit of a mess.

• Add #include <stdlib.h> at the top because it complains malloc is undefined (which still compiles in C but isn't exactly a good idea).
• Your invocation to malloc is wrong. You seem to want to create an array of b_num elements but you're creating one of b_num bytes, which is only b_num / 2 shorts (heap corruption cause 1).
• The function bin_init_array is not necessary, you can use calloc to allocate and initialize to zero in one go (also helps preventing the previous problem):
  arr = (unsigned short*)calloc(b_num, sizeof(unsigned short));
• b_num = len / sizeof(short) / 8;
  I'm not entirely sure how you got to this calculation (I can't really tell what half of the algorithm is doing), but that will yield 0 for any value of len lower than 16. Since you are always accessing the first element (arr[0] = 0x6A28;) that's heap corruption cause number 2.
• if( arr[i] & j == j )
  That line needs extra () because of operator precedence: if( (arr[i] & j) == j )
• You've got a lot of signed/unsigned mismatches in the code.

When I correct all those problems (and use a value of len >= 16) it doesn't crash anymore. It doesn't compute the prime numbers correctly either though (it returns numerous non-primes). Since I have no idea how this algorithm is trying to achieve what it's supposed to be doing I can't really help any further.

Thanks. I make the changes you suggested and I did a bit of debugging. When I had written this, it was supposed to be an a version of the first program that I had posted above that used bits instead of individual array values, which required that I break each loop into two loops. Because of that, there was a bug involving the break statement, as while it broke out of the inner loop in the first program, it broke out of a loop in the second program that would be analogous to half the inner loop in the first program.

// prime.c
// Sept 27, 2007.
// <insert name here>
// Program to find prime numbers

#include <stdio.h>
#include <stdlib.h>

int main (void)
{

    int len, b_num, num;

    unsigned int i, j;

    unsigned short * arr = NULL;

    printf ("Find prime numbers smaller than \n");
    scanf("%i", &len);

    b_num = (len + 1) / 8;

    arr = (unsigned short*)calloc (b_num,sizeof(int));

    bin_arr_prime_fill(arr, b_num);

    //Loop through Prime Array and Output Primes
    for ( i = 0, num = 1; num <= len ; i++ )
    {

        for ( j = 0x8000; j > 0 && num <= len; j >>= 1, num++ )
        {

            if ((arr[i] & j) == j)
            {

                printf("Number %i is a prime number\n", num);

            }

         }

    }

    free(arr);

    return 0;

}
 
int bin_arr_prime_fill (unsigned short arr[], int len)
{

    unsigned int i, j, k, l, n, m;
       
    //Set 2 to prime
    arr[0] = 0x6A28;

    for ( i = 1; i < len; i++ )
    {
   
        //j has a binary 1 where the number is in the array
        //n is the number in an int
        j = 0x8000;
        n = 16 * i + 1;
        while (j > 0)
        {
   
            //Set Number to Prime
            arr[i] += j;

            //Here we check if the number is prime by iterating
            //through each block, checking to see if the prime
            //elements divide the number
            //k is the block whose numbers are being considered
            //by the loop
            //m is the divisor, starting with 3
            //Set l = 0x2000 so it corresponds to m = 3
            //for the initial loop
            for (k = 0, m = 3, l = 0x2000; k < i / 2 + 1; k++)
            {
   
                //Checks if any number in the word is a factor
                // of the number being tested
                for (  ; m <= (n / m) ; l >>= 2, m += 2 )
                {
       
                    if ((arr[k] & l) == l && (n % m) == 0)
                    {
         
                        arr[i] -= j;
                        goto label;
             
                    }
               
                }

                l = 0x8000;
         
            }

label:
            j >>= 2;
            n+=2;
     
        }
   
    }

    return 0;

}

I will try to clean up the code later, but as far as I am concerned, it works beautifully.

arr = (unsigned short*)calloc (b_num,sizeof(int));

That makes no sense. You're telling calloc to allocate space for b_num ints and then cast it to an array of shorts? Why not use sizeof(unsigned short) since that's what your array actually holds? You're allocate twice the amount of memory you actually need.

Sven Groot wrote:

arr = (unsigned short*)calloc (b_num,sizeof(int));

That makes no sense. You're telling calloc to allocate space for b_num ints and then cast it to an array of shorts? Why not use sizeof(unsigned short) since that's what your array actually holds? You're allocate twice the amount of memory you actually need.

That is a typo. Thanks for catching it.

I cleaned up my program's source code a bit by introducing a new function, adding/changing comments and making minor changes here and there. It now compiles in GCC (the previous code did not) and I believe that it is valid C:

// prime.c
// Sept 28, 2007.
// <my name was here>
// Program to find prime numbers

#include <stdio.h>
#include <stdlib.h>

int main (void)
{

        int len, b_num, num;

        unsigned int i, j;

        unsigned short * arr = NULL;

        printf ("Find prime numbers smaller than \n");
        scanf("%i", &len);

        b_num = ( len % (8 * sizeof(unsigned short)) == 0 ) ?
                (len / (8 * sizeof(unsigned short))) :
                (len / (8 * sizeof(unsigned short)) + 1);

        arr = (unsigned short*)calloc (b_num, sizeof(unsigned short));

        bin_arr_prime_fill(arr, b_num);

        //Loop through Prime Array and Output Primes
        for ( i = 0, num = 1; num <= len ; i++ )
        {

                for ( j = 0x8000; j > 0 && num <= len; j >>= 1, num++ )
                {

                        if ((arr[i] & j) == j)
                        {

                                printf("Number %i is a prime number\n", num);

                        }
 
                 }
       
        }
       
        free(arr);
       
        return 0;
       
}

int bin_arr_prime_fill (unsigned short arr[], int len)
{
               
        unsigned int i, j, n;
       
        //Predefine first block
        arr[0] = 0x6A28;

        for ( i = 1; i < len; i++ )
        {
        
                //j has a binary 1 where the number is in the array
                //n is the number in an int
                for ( j = 0x8000, n = 16 * i + 1 ; j > 0 ; j >>= 2, n += 2 )
                {
                        
                        //arr is the prime array
                        //i is the block currently being built
                        //n is the number being tested
                        if (isPrime(arr, n) == 1)
                        {
                                arr[i] += j;
                        }
       
                }
       
        }
       
        return 0;
       
}

int isPrime(unsigned short arr[], unsigned int n)
{
               
        unsigned int k, l, m;
       
        //k is the block of the array whose numbers
        //are being considered by the loop
        //l is the position in k that corresponds to a number
        //m is the divisor, starting with 3
        //Set l = 0x2000 so it corresponds to m = 3 for the
        //first inner loop
        //Set l = 0x8000 so it corresponds to the first number
        //in the block in every suceeding loop
        //Loop through each block of the array
        for (k = 0, m = 3, l = 0x2000; m <= (n / m); k++, l = 0x8000)
        {               
                       
                //Check each number in the block for primiality,
                //skipping even numbers
                for (  ; m <= (n / m) ; l >>= 2, m += 2 )
                {
                               
                        //If the divisor is prime and it divides
                        //n evenly, return composite
                        if ((arr[k] & l) == l && (n % m) == 0)
                        {
        
                                return 0;
       
                        }
 
                }

        }
               
        //Return Prime
        return 1;
       
}

Please critique it. I am a PHP programmer by hobby so many concepts in C (e.g. predefining variables, defining variable types, functions being variable type sensitive, memory management, etcetera) are fairly new to me and I have been hacking my way along. I realize that someone more experienced would have written this much better than I have, so I am fairly eager to learn how it should have been done.

Shining Arcanine wrote:



Please critique it. I am a PHP programmer by hobby so many concepts in C (e.g. predefining variables, defining variable types, functions being variable type sensitive, memory management, etcetera) are fairly new to me and I have been hacking my way along. I realize that someone more experienced would have written this much better than I have, so I am fairly eager to learn how it should have been done.

well for any language some general things:

1) strive to make the code clean and simple. do not try to "optimise" the code untill you are 100% clear on correct function and know whre perfomance problems are.

2) think about the problem, write it down, then code.

3)  pattern #1 declare, Init, use, dispose.

in C you are going back to basics.
but even with C# it does not hurt to strive to organize the layout of code.

define variables in one section before you use them.

study how the stdio and other C things work.

while I am not sure that bits help in this if you do want to use them then check out unions in C
for example you can map 4 bytes to a 32 bit int
or 8 bits to a byte.

I thought I'd try to come up with how I'd do what you're trying to do, because some of your code feels like taking the long way around.

I started with the original program you posted (but with calloc) and immediately found a bug: it listed 25 as prime. The reason is this line:
for ( j = 3; j < i / j; j+=2 )
The condition j < i / j evaluates false for j == 5, which means that 5 itself is not checked, incorrectly marking 25 as prime. After changing the condition to i <= i / j it seems to work correctly.

I now had a working algorithm. My next step was to change the array to a char array; the only possible values of the array elements are 0 and 1 so why not use the smallest element possible? This already halves the storage requirement of the program.

Now to make it a bitfield. It's too bad it isn't C++; in C++ std::vector<bool> is optimized for this so we'd just use that and be done with it.

Instead of dealing with additional loops the way you did, I kept the original structure of the program. For every number I simply calculate the corresponding array element and bit index in that array element. Note that inside a single element I start at the least significant bit and work up, which is reverse from your code, but otherwise makes no difference. Note I made this as general as possible by using the CHAR_BIT constant which is the number of bits in a "char" so even on systems where this is not 8 my code should compile and run correctly.

Having tested this and confirming it worked I set out ot make sure it's valid C. This meant changing all the // comments to /* */ comments; although 99% of compilers allow this, it's strictly not part of ANSI C89. The code now compiles with the Comeau compiler (the world's most standards-compliant compiler) in strict C89 mode.

The end result:

This version still wastes space, since it has bit positions for even numbers as well, which are obviously never prime. I leave that optimization as an exercise for the reader.

There are still other opportunities for optimizations left in this code as well, such as incremental calculation of arrayIndex and bitValue instead of dividing all the time.

figurres, thanks for the list.

Sven Groot wrote:



I thought I'd try to come up with how I'd do what you're trying to do, because some of your code feels like taking the long way around.

I started with the original program you posted (but with calloc) and immediately found a bug: it listed 25 as prime. The reason is this line:
for ( j = 3; j < i / j; j+=2 )
The condition j < i / j evaluates false for j == 5, which means that 5 itself is not checked, incorrectly marking 25 as prime. After changing the condition to i <= i / j it seems to work correctly.

I now had a working algorithm. My next step was to change the array to a char array; the only possible values of the array elements are 0 and 1 so why not use the smallest element possible? This already halves the storage requirement of the program.

Now to make it a bitfield. It's too bad it isn't C++; in C++ std::vector<bool> is optimized for this so we'd just use that and be done with it.

Instead of dealing with additional loops the way you did, I kept the original structure of the program. For every number I simply calculate the corresponding array element and bit index in that array element. Note that inside a single element I start at the least significant bit and work up, which is reverse from your code, but otherwise makes no difference. Note I made this as general as possible by using the CHAR_BIT constant which is the number of bits in a "char" so even on systems where this is not 8 my code should compile and run correctly.

Having tested this and confirming it worked I set out ot make sure it's valid C. This meant changing all the // comments to /* */ comments; although 99% of compilers allow this, it's strictly not part of ANSI C89. The code now compiles with the Comeau compiler (the world's most standards-compliant compiler) in strict C89 mode.

The end result:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h> /* for CHAR_BIT */

int main(void)
{
   int maxNumber, arrayLength, arrayIndex, checkArrayIndex, number, checkNumber;
   unsigned char bitValue, checkBitValue;
   unsigned char *bitMask;

   printf("Find prime numbers smaller than \n");
   scanf("%i", &maxNumber);

   arrayLength = (maxNumber / CHAR_BIT) + 1;
   /* Prime Array */
   bitMask = (unsigned char*)calloc(arrayLength, sizeof(unsigned char));

   /* Set 2 as prime. */
   bitMask[0] = 1 << 2;

   /* Check each number for primiality, starting with 3
    * Skip every other number in array
    * Also, set all composites to 0 */
   for( number = 3; number < maxNumber; number += 2 )
   {
      /* Get the array element for this number */
      arrayIndex = number / CHAR_BIT;
      /* Get the array element value for this number */
      bitValue = 1 << (number % CHAR_BIT);
      /* Set Number to Prime */
      bitMask[arrayIndex] |= bitValue;

      /* Loop through all known prime numbers less than
       * the square root of the number being considered */
      for( checkNumber = 3; checkNumber <= number / checkNumber; checkNumber += 2 )
      {
         checkArrayIndex = checkNumber / CHAR_BIT;
         checkBitValue = 1 << (checkNumber % CHAR_BIT);
         if( number % checkNumber == 0 && 
             (bitMask[checkArrayIndex] & checkBitValue) != 0 )
         {
            /* Set position in array to composite by clearing the bit
             * We know the bit is set when we get here so we can use xor to do this */
            bitMask[arrayIndex] ^= bitValue;
            /* No need to check further once we've found a divisor */
            break;
         }
      }
   }

   /* Loop through Prime Array and Output Primes */
   for( number = 1; number <= maxNumber; number++ )
   {
      arrayIndex = number / CHAR_BIT;
      bitValue = 1 << (number % CHAR_BIT);
      if( (bitMask[arrayIndex] & bitValue) != 0 )
      {
         printf("Number %i is a prime number\n", number);
      }
   }

   free(bitMask);

   return 0;
}

This version still wastes space, since it has bit positions for even numbers as well, which are obviously never prime. I leave that optimization as an exercise for the reader.

There are still other opportunities for optimizations left in this code as well, such as incremental calculation of arrayIndex and bitValue instead of dividing all the time.

Wow, thanks for showing me how you would have done it. I had no idea that // comments were not valid in C and I really like how you used the bitwise | and ^ operators rather than the arithmetic operators + and - like I did. I had thought about excluding positive numbers in the array, but until today, I did not like the idea of having an array of prime numbers that does not include 2.

I have since rewritten my program to exclude even numbers and I have written a hack in the main program block to get it to output 2. Thanks to that optimization (another involving using int instead of short and any increase in performance that using bitwise operators instead of arithmetic operators might bring), my program can now find all primes between 1 and 750 million in about three hours on my PC (before it could only get to about 300 to 400 million in that timespan).

crud!  I had a nice long reply and C9 just ate it!!

fast:  Sven's sample is very nice.


Pointers and arrays are two sides of the same coin, most of the time you can swap them for each other.

but often an array is more readable code:

(char)*x+1 = 'a'
vs

x[1] = 'a'

for an off the cuff example.

thomas plum / plumb hall publising has some very good books on C from the mid 80's

I still have the book:

Reliable Data Structures in C
ISBN: 0-911537-04-X

get his books if you can, very good text books.

Lists, for the primes no.

for many other things yes.

a list means you need to add a pointer to each data item for a list
and more than one pointer for a double linked list or a tree.

for sorting a bunch of data a list is good as you can change the pointers and not copy / move the data.

figuerres wrote:

Lists, for the primes no.

for many other things yes.

a list means you need to add a pointer to each data item for a list
and more than one pointer for a double linked list or a tree.

for sorting a bunch of data a list is good as you can change the pointers and not copy / move the data.

Thanks. I read about lists in my C book and I was wondering what they were good for doing.

By the way, I realize that multithreading, assembly language and programming GPUs to do general processing tasks is too advanced for me at this point in time, but I am wondering, is it possible to do that stuff in C? I am asking as looking at the table of contents, my C book makes no mention of them.

I have made some improvements to my code. I have lowered the number of variables defined in my program's functions by 1 in total by using pointers, changed the variable names to be more descriptive, used muti-line comments to conform to the C specification, replaced arithmitic operators with binary operators, modified comments, made the program call itself so it need not be executed multiple times, made arr store only odd numbers to lower the memory needed for it by a factor of 2, made arr an unsigned int array rather than an unsigned short array to reduce the number of iterations the outer loops make, made all variables unsigned to facilitate scaling, etcetera. Here it is:

/*  prime.c */
/*  Sept 29, 2007. */
/*  <my name was here> */
/*  Program to find prime numbers */
#include <stdlib.h>

int main (void)
{

    unsigned int len, b_num, num, bitVal, *arr = NULL, *arrEnd = NULL;

    printf ("\nFind prime numbers smaller than \n");
    scanf("%i", &len);

    if (len < 1)
    {

        return 0;

    }

    b_num = ( len % (16 * sizeof(unsigned int)) == 0 ) ?
        (len / (16 * sizeof(unsigned int))) :
        (len / (16 * sizeof(unsigned int)) + 1);

    arr = (unsigned int*)calloc (b_num, sizeof(unsigned int));

    arrEnd = arr + b_num;

    bin_arr_prime_fill(arr, b_num);

    if (len >= 2)
    {
        
        printf("Number 2 is a prime number\n");

    }

    /* Loop through Prime Array and Output Primes */
    for ( num = 1; arr < arrEnd ; ++arr )
    {

        for ( bitVal = 0x80000000; bitVal > 0 && num <= len; bitVal >>= 1, num += 2 )
        {

            if ((*arr & bitVal) == bitVal)
            {

                printf("Number %i is a prime number\n", num);

            }

        }

    }

    free(arr - b_num);

    main();

    return 0;

}

int bin_arr_prime_fill (const unsigned int * const arr, const unsigned int len)
{

    unsigned int b, num, *a = arr, *aEnd = arr + len;
    
    /* b has a binary 1 where the number is in the array */
    /* num is the number being checked for primiality */
    /* a is used to seek to the appropriate position in the array * /
    /* aEnd is used to determine when to stop */
    for ( num = 3, b = 0x40000000; a < aEnd; ++a, b = 0x80000000 )
    {
        for (  ; b > 0 ; b >>= 1, num += 2 )
        {
            
            /* arr is the prime array */
            /* a points to the block currently being built */
            /* num is the number being tested */
            if (isPrime(arr, num) == 1)
            {
                *a |= b;
            }

        }

    }

    return 0;

}

int isPrime(const unsigned int * arr, const unsigned int num)
{

    unsigned int bitVal = 0x40000000, div = 3;

    /* arr points to an array; it is used to seek to the correct block */
    /* num is the number being checked for primiality */
    /* bitVal is the bit position */
    /* div is the divisor, starting with 3 */
    /* Set bitVal = 0x2000 so it corresponds to m = 3 for the */
    /* first inner loop */
    /* Set bitVal = 0x8000 so it corresponds to the first number */
    /* in the block in every suceeding loop */
    /* The outer loop loops through each block of the array */
    for (  ; div <= (num / div); ++arr, bitVal = 0x80000000)
    {

        /* The inner loop checks each number in the block for\ */
        /* primality, skipping even numbers */
        for (  ; div <= (num / div) ; bitVal >>= 1, div += 2 )
        {

            /* If the divisor is prime and it divides */
            /* n evenly, return composite */  
            if ((*arr & bitVal) == bitVal && (num % div) == 0)
            {

                return 0;

            }
 
        }

    }

    /* Return Prime */
    return 1;

}

Is there a better way to make use of pointers? I am using three in bin_arr_prime_fill() and two in main() and that seems a bit messy in comparsion to isPrime() where I am only using one. Also, are linked lists useful and could they be of any use in this program?