Learn to Code
John F. Dumas
contact me | resume | how it works | example programs | testimonials | main page

Feedback Examples: Five

one | two | three | four | five


► PROGRAMMING LANGUAGE:: C

► ASSIGNMENT: You are to implement the function 'isPrime' that accepts a single argument and returns back true if the argument is a prime number, false otherwise.

Test your function by using it to output all the prime numbers that are less than 10,000. There should be a total of 1,229 of them. Here are the first and last ten:

   2
   3
   5
   7
   11
   13
   17
   19
   23
   29

   ...

   9887
   9901
   9907
   9923
   9929
   9931
   9941
   9949
   9967
   9973

View the Student's Code


► FEEDBACK: The program correctly outputs all prime numbers that are less than 10,000. This was solid work and there's nothing at all wrong with it, however, I'm going to show you some ways it can be made a bit faster. Firstly, there's little point in talking about software performance if you can't measure it (after all, without that ability how will you know if your changes are actually improvements or not?).

Here's the same code but with some timing information added:

   #include <stdio.h>
   #include <time.h>

   int isPrime(int value)
   {
      int returnValue = 1;

      if(value < 2)
      {
         returnValue = 0;
      }
      else
      {
         int i = 2;

         while(i < value)
         {
            if(value % i == 0)
               returnValue = 0;

            i++;
         }
      }

      return(returnValue);
   }

   int main()
   {
      clock_t start, end;

      double elapsed = 0.0;
      int    i       = 0;

      start = clock();

      while(i < 10000)
      {
         if(isPrime(i))
            printf("%d\n", i);

         i++;
      }

      end = clock();

      elapsed = ((double)(end - start)) / CLOCKS_PER_SEC;

      printf("Elapsed: %f\n", elapsed);

      return(0);
   }

And when executed, it prints out the 1,229 primes less than 10,000 but also tells us how many seconds it took the program to execute:

   2
   3
   5
   7
   11

   ...

   9931
   9941
   9949
   9967
   9973

   Elapsed: 0.197000

For our first optimization, consider this bit of code:

   int i = 2;

   while(i < value)
   {
      if(value % i == 0)
         returnValue = 0;

      i++;
   }

Now, suppose that 'value' is 20, what will happen on each pass through our 'while' loop?

   value of 'i'    results
   ==========      =======
      2               Since 20 % 2 is zero, returnValue will be set to 0
      3               Since 20 % 3 is non-zero, nothing will change
      4               Since 20 % 4 is zero, returnValue will be set to 0
      5               Since 20 % 5 is zero, returnValue will be set to 0
      ...             ...
      10              Since 20 % 10 is zero, returnValue will be set to 0

Notice that we really get all the information we need when 'i' is 2 since once we set 'returnValue' to 0, it doesn't ever get set back to 1.

While it might be interesting that 20 is evenly divisible by: 10, 5, 4 and 2, we only need the one divisor to determine that 20 is not a prime.

So, how can we fix this? By reworking our loop so that it terminates as soon as we find the very first divisor. Here's some code that exits the loop as soon as it can, via 'break':

      int i = 2;

      while(i < value)
      {
         if(value % i == 0)
         {
            returnValue = 0;
            break;
         }

         i++;
      }

Here's the complete program with the change above applied:

   #include <stdio.h>
   #include <time.h>

   int isPrime(int value)
   {
      int returnValue = 1;

      if(value < 2)
      {
         returnValue = 0;
      }
      else
      {
         int i = 2;

         while(i < value)
         {
            if(value % i == 0)
            {
               returnValue = 0;
               break;
            }

            i++;
         }
      }

      return(returnValue);
   }

   int main()
   {
      clock_t start, end;

      double elapsed = 0.0;
      int    i       = 0;

      start = clock();

      while(i < 10000)
      {
         if(isPrime(i))
            printf("%d\n", i);

         i++;
      }

      end = clock();

      elapsed = ((double)(end - start)) / CLOCKS_PER_SEC;

      printf("Elapsed: %f\n", elapsed);

      return(0);
   }

With this improvement, our running time is now much better:

      Elapsed: 0.039000

There is another improvement we can make that's not too difficult to implement. It's based around the observation that if we've already failed to divide 2 into our number to see if it is a prime, there's no point in ever trying to divide another even number into it. Here's the full program with that optimization applied:

   #include <stdio.h>
   #include <time.h>

   int isPrime(int value)
   {
      int returnValue = 1;

      if(value < 2)
      {
         returnValue = 0;
      }
      else if(value % 2 == 0)
      {
         if(value != 2)
            returnValue = 0;
      }
      else
      {
         int i = 3;

         while(i < value)
         {
            if(value % i == 0)
            {
               returnValue = 0;
               break;
            }

            i += 2;
         }
      }

      return(returnValue);
   }

   int main()
   {
      clock_t start, end;

      double elapsed = 0.0;
      int    i       = 0;

      start = clock();

      while(i < 10000)
      {
         if(isPrime(i))
            printf("%d\n", i);

         i++;
      }

      end = clock();

      elapsed = ((double)(end - start)) / CLOCKS_PER_SEC;

      printf("Elapsed: %f\n", elapsed);

      return(0);
   }

And when executed (as expected) the change above reduces our running time by about 50%.

      Elapsed: 0.020000

The final optimization we will make has to do with when we can stop trying to find divisors. Currently, we start 'i' at 2 and only stop just before the number we are analyzing. Consider a room that is 36 square feet. One possible configuration would be a 6 x 6 room, something like this:

      X X X X X X
      X X X X X X
      X X X X X X
      X X X X X X
      X X X X X X
      X X X X X X

How else might the room be laid out to be 36 square feet? Here are some other possibilities, first: 2 x 18:

      X X X X X X X X X X X X X X X X X X
      X X X X X X X X X X X X X X X X X X

And then 3 x 12:

      X X X X X X X X X X X X
      X X X X X X X X X X X X
      X X X X X X X X X X X X

Now, when our room is a square, the size of each side is 6 feet. Notice that if we want a side to be larger than 6 feet (like 18 or 12), then the corresponding other side will have to be less than 6 for the area to be 36 square feet.

In terms of factors, this observation is very useful. It tells us that if we have not found a factor of a number by the time we hit that number's square root, we won't ever find one.

The reason being that when we have two factors that are not the square root of our number, one of them will have to be larger than the square root and one smaller. We won't find a large factor (bigger than the square root) without having already run into its corresponding small factor (less than the square root).

Here's the code with that change applied:

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

   int isPrime(int value)
   {
      int returnValue = 1;

      if(value < 2)
      {
         returnValue = 0;
      }
      else if(value % 2 == 0)
      {
         if(value != 2)
            returnValue = 0;
      }
      else
      {
         int stop = (int)sqrt(value);
         int i = 3;

         while(i <= stop)
         {
            if(value % i == 0)
            {
               returnValue = 0;
               break;
            }

            i += 2;
         }
      }

      return(returnValue);
   }

   int main()
   {
      clock_t start, end;

      double elapsed = 0.0;
      int    i       = 0;

      start = clock();

      while(i < 10000)
      {
         if(isPrime(i))
            printf("%d\n", i);

         i++;
      }

      end = clock();

      elapsed = ((double)(end - start)) / CLOCKS_PER_SEC;

      printf("Elapsed: %f\n", elapsed);

      return(0);
   }

And when executed, the performance improvement is massive:

      Elapsed: 0.001000

So, to summarize, here are our results:

      Program Version    Elapsed Time   Speed Improvement
      ---------------    ------------   -----------------
      original           0.197000          N/A
      with break         0.039000          5.05 times
      step by two        0.020000          9.85 times
      square root        0.001000        197.00 times

While the initial code was perfectly correct with respect to the output, it is worth noting that our optimized version of the code runs nearly *200* times as fast as that initial version.


Reference Files


© John F. Dumas | johnfdumas@gmail.com | main page | top of page