Learn to Code
John F. Dumas

Feedback Examples: 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
```

► 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.

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