CODEWITHSUNDEEP
c
galois
galois

Reputation: 857

Why is this check for prime numbers returning true on some non-prime numbers?

I'm having trouble with a function to check if a number is prime - it's returning that a number is prime when it isn't sometimes (even numbers sometimes, too!). Any idea why?

int isPrime(long x){
    int i;

    if(x==2||x==3)      return 1;   //if i = 2 or 3, return true
    if(!(x&1))          return 0;   //if x is even  return false

    for(i=3;i<=sqrt(x);i+=2) if (x%i == 0) return 0;        //if x is divisible by i return false

    return 1;
}

To everyone, thanks so much for the answers, I'd +1 them all if my rep was high enough :D

Sadly, my idiocy has reached new heights, and I found the error was within logic elsewhere in my program.

Upvotes: 0

Views: 198

Answers (3)

SHASHIDHAR MANCHUKONDA
SHASHIDHAR MANCHUKONDA

Reputation: 3322

You are not checking whether x is divisble by 2.

Before that for loop add a return 0 if its is divisble by 2.

Upvotes: -1

akristmann
akristmann

Reputation: 444

I edited the for-loop to:

for(i=3;i<=x/2;i+=1) if (x%i == 0) return 0;

In the main i go through the first 100 Numbers.

int main()
{
    long test=0;
    int i = 2;
    for( ; i < 100; i++)
    {
        test = isPrime(i);
        if(test == 1) printf("%d ",i);
    }

       getchar();
       return 0;
}

This is the ouput: and this ist the ouput for the first 100 primes:

2 3 5 7 11  13  17 19 23 29  31 37 41 43 47  53 59 61 67 71  73 79 83 89 97

I changed the i+=2 to i+=1, because in your code the skip every second number.

Upvotes: 0

Alex
Alex

Reputation: 10126

Possibly it because of the rounding of the sqrt(x) as result of this function call is floating point value. So it can be a little less than rounded to the closest integer.

In this case e.g. sqrt(25) could be rounded to 4 instead of 5.

EDIT

The fault number on 104730 tells that

 if(!(x&1)) return 0;   //if x is even  return false

doesn't seem to work correctly... So, can you try the x&1L?

I am not sure, but id the size of the int and long is different, and (probably) 1 is implicitly caste to a shorter one type, so possibly it checks incorrect bit...

Also try just

if(!(x%2)) return 0;   //if x is even  return false

in order to avoid bit patterns usage and platform dependence.

Upvotes: 3

Related Questions