Bugs in an is_prime() implementation

K

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;
}
 
R

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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top