Prime Number Program - Please critique!!!

[niehaoma]

The purpose of this is to obtain a genuine critique of my source code (based on a fairly simple concept). I realize I may not have the cleanest implementation for testing for prime, due to the fact I am not an aspiring mathematician. I am interested on critique of the code itself, the use of recursion, pointers, etc. Please post "better" implementations of sections, along with WHY it is better. This will allow me to learn, and possibly others, at the same time stimulating academic conversation. Thanks in advance.

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

/*========================================================
/                   GLOBAL VALUES
/ ========================================================*/
#define FALSE 0
#define TRUE (!FALSE)
#define TEST_EVEN 2.0      /* any integer evenly divisible by 2 is an even integer */
#define ZERO_REMAINDER 0   /* an even number has a zero remainder when divided by 2 */

/*========================================================
/                   FUNCTION PROTOTYPE(s)
/ ========================================================*/
void findPrime(unsigned int *isPrime, const unsigned int *num, unsigned int *div);

/*========================================================
/                      MAIN FUNCTION
/ ========================================================*/
int main(void)
{
  unsigned int baseDiv = 2;    /* Starting Divisor */
  unsigned int isPrime = TRUE; /* a number is considered prime, until proven !prime */
  unsigned int limit = 0;      /* max [possible] chosen prime */

  /* find primes from "limit" down to 2 */
  do
  {
    printf("Enter a value for \"limit\" to find primes from 2 to \"limit\"): ");
    scanf("%u", &limit);
  }
  while(limit <=2);

  /* Recursive semi-exhaustive search to determine if number is prime */
  while(limit > 1)  /* 1 is not a prime number, no need to test it */
  {
    findPrime(&isPrime, &limit, &baseDiv);

    if(isPrime == TRUE)
      printf("\n%u is a prime number.", limit);
    else
      isPrime = TRUE;  /* Number is !Prime. Reset isPrime for next iteration */

    limit = limit - 1;  /* Test the next consecutive integer to see if its prime */
    baseDiv = 2;        /* Reset */
  }

  return 0;
}

/*========================================================
/                   FUNCTION DEFINITION(s)
/ ========================================================*/

/* Function to determine if an integer is a prime number */
void findPrime(unsigned int *isPrime, const unsigned int *num, unsigned int *div)
{
  int rem = 0;
  float rootMod = fmod( sqrt(*num), TEST_EVEN);

  /* if the sqrt of num is an even number (remainder == 0), then it is not prime */
  if(rootMod > ZERO_REMAINDER)
  { /* Sqrt mod 2 not equal to zero, so num "may" be prime */

    /* Dont need to divide by 1, as any number !=0 is divisible by 1 and
     dont need to keep testing once non-prime is determined. Start at dividing by
     two, as any even number [other than 2] is not prime, and will be eliminated immediately */
    if( (*div < *num) && (*isPrime == TRUE) )
    {
      rem = *num % *div; /* Calculate the remainder */

      if(rem == 0)            /* If the remainder is 0, then num is not prime */
        *isPrime = FALSE;
      else                    /* else, we need to check the next subsequent number -1 */
      {
        *div = (*div + 1); /* increment the base divisor */
        findPrime(isPrime, num, div);
      }
    }
  }
  else /* number is not prime */
    *isPrime = FALSE;
}

[Adak]

I prefer where the numbers being tested are incremented by two, since no even number can be prime. Why test them at all? Only testing the odd numbers, cuts the work in half, straightaway.

Also, I prefer a more concise coding. Not

rem = *num % *div; /* Calculate the remainder */

if(rem == 0)            /* If the remainder is 0, then num is not prime */
   *isPrime = FALSE;
  
//but:
if(*num % *div)
  *isPrime=FALSE;
else
  *isPrime=TRUE;

The comments are too verbose - the obvious code we need no comments on, imo. It's distracting, actually.

Nothing wrong with doing the testing in another function, but it does slow things down when you have to work through a pointer, time after time. With a very large number to be tested (or several very large numbers), the run-time jumps considerably.

I realize you're not coding for some Cryptographic endeavor, but after accuracy, I start putting a lot of emphasis on clarity and faster run-time/efficiency. Your code is easy to read, which is good.

I didn't catch the reason for TEST_EVEN being a test for even integers, when it's a floating point number.

[niehaoma]

Thanks for the comments. I realize for some the code is not considered as concise, however I tend to write safety-critical SW for avionics SW certification (DO-178B), which requires some strict coding guidelines. Some of those rules are intermixed in this example. They are too long to list here, but in a nutshell it tends to be "long-winded".

For instance, some guidelines dictate you cannot even declare a loop variable within a for-loop:

// Not allowed:
for(int i=0; i<someVal;i++)

//Allowed
int i =0;
for(i; i<someVal;i++)

(These rules are not necessary for this example, again, it is just a habit from past work experience).

Smack me in the head for iterating through the even numbers. Again, that is a mathematical oversight in the code. In regards to TEST_EVEN, it just eliminates a magic number, and fmod() takes two float arguments [or double].

I am interested in more specific details about efficiency, related to stack usage, etc. For instance, yes a function call occurs, however the variables arent passed by value, so it should limit stack-bloat. Also, this could have easily be done in a for loop. I would like to get some feedback on the "computer-science" related details as to the differences in possible implementations and how it affects the compiled code, run-time statistics, etc. Thanks.

[Adak]

It is because the variable is passed by address, that the continued need to dereference the pointer, becomes a run-time anchor.

The great thing about your program, is that it's simple to test it for yourself. Google up and d/l a few other others, and time them with your own system. Give them a target that requires at least 1 minute or so of run-time on your program. Then test several other versions, as well. See how they all stack up in run-time.

I believe you'll be surprised at how much slower your program is.

[Adak]

I tested the program here, several more times, and it's much worse than I thought:

1) It crashes abruptly without an error message, if you request more than 2700 as the upper limit. This is a major bug for a prime number testing program.

2) I compared it's run time, using 2,500 as the upper limit, against a quick prime number tester I wrote. (also only in standard C, no assembly here, no bit tricks, etc.). With minor differences, the logic is the same. My program is iterative though, not recursive.

My program also calls another function to test each number, returns that result, and gets the next number to be tested.

My program ran 488% faster, testing 12,200 numbers, in the same amount of time (0.055 seconds), that the OP's program tested 2,500 numbers.

This is only an estimate of the true performance of both programs, because the OP's program wouldn't work with any higher numbers.

Each program also printed out what number it had found, as it found it - just a short few words, and the number, and a newline.

Please test this program, on your system and with your compiler, and report what you find - maybe that dreadful upper limit bug is not happening on other compilers.

The OP should know if it is a common bug, so he can look into fixing it.

[niehaoma]

Revised:

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

/*========================================================
/                   GLOBAL VALUES
/ ========================================================*/
#define FALSE 0
#define TRUE (!FALSE)

/*========================================================
/                   FUNCTION PROTOTYPE(s)
/ ========================================================*/
void findPrime(unsigned int upperBound);

/*========================================================
/                      MAIN FUNCTION
/ ========================================================*/
int main(void)
{
  unsigned int upperBound = 0;      /* max [possible] chosen prime */

  do
  {
    printf("Enter a value for \"upperBound\" to find primes from 2 to \"upperBound\"): ");
    scanf("%u", &upperBound);
  }
  while(upperBound <= 2);

  findPrime(upperBound);

  return 0;
}

/*========================================================
/                   FUNCTION DEFINITION(s)
/ ========================================================*/

/* Function to determine if an integer is a prime number */
void findPrime(unsigned int upperBound)
{
  unsigned int testNum;
  unsigned int isPrime = TRUE;

  for(testNum = upperBound; testNum > 1; testNum--)
  {
    if( ((testNum % 2) > 0) || (fmod( sqrt(testNum), 2.0) > 0) )
    {
      unsigned int div = 3;

      while( (isPrime == TRUE) && (div <= (testNum / 2)) )
      {
        if( (testNum%div) == 0 )
          isPrime = FALSE;
        else
          div += 2;
      }

      if(isPrime)
      {
        printf("\n%u is a prime number.", testNum);
      }

      isPrime = TRUE;
    }
  }
}

[Adak]

When someone takes the time to test and find a bug in your program, it seems the least you could do when posting a revised version, is to point out:

1) Whether the bug is now fixed, and

2) What the new testing you did, reveals for the limits of the program.

This is NOT a criticism of this program, since this is a general student type algorithm,

*BUT*

Looking at the problem, it might seem that we need to test every odd number, from the square root of the number, right on down to a very low number (say, 3).

But do we??

Wait a dang minute! Because every compound number (the non-prime numbers), are factors of prime numbers - so ONLY the prime numbers from the square root of the number being tested, down to 3, need to be tested!.

Aha! ;)

This change in the algorithm won't help in finding any of the lower prime numbers, (because of the added overhead), but definitely it will help, when the numbers being checked, get really large.

[hsetaknev]

#include

void main()

{int n,j,i;
n=j=i=0;
scanf("%d",&n);

for( i=1;i2)
{
printf("\nthe number is not prime\n");
}
}