Bugs in an is_prime() implementation

[Richard Heathfield]

Harald van D?k said:

So factor * factor > num, so the loop is skipped.

Oh, good spot. My apologies to the OP.

 

[Kelly]

Hello experts,

The following is_prime function doesn't call a library function and it
works.

Does it have bugs like "integer overflow": int factor; factor * factor,
or it's not single entry/exit, or others... Thank you.

This will print primes,rest is just fine until u take care of the
limits that your particular compiler imposes on the limit
of int,check <limits.h>
so that factor*factor doesn't overflow the limit
or else just use unsigned long type


#include <stdio.h>
#define MAX 1000

int is_prime(int num)
{
int factor;
if (num < 2)
return 0;
for (factor = 2; factor * factor <= num; factor++)
if (num % factor == 0)
return 0;
return 1;
}

int main(void)
{
int i;
for (i=0;i<MAX;i++)
if (is_prime(i))
printf("%d\n",i);
return 0;
}

 

[Richard Heathfield]

Kelly said:

[...] take care of the
limits that your particular compiler imposes on the limit
of int,check <limits.h>
so that factor*factor doesn't overflow the limit

Or, knowing that factor >= 2, you can do this: factor <= num / factor

Or better still, you can do this:

max = sqrt(num);
for(factor = 2; factor <= max; factor++)

which removes the in-loop calculation completely and therefore removes the
possibility of overflow in that calculation (and yes, more optimisation
work remains to be done, but this thread isn't about optimisation).