Prime test

[aamira_s]

this is a simple code to test whether a number is prime or not...i dont know y it is taking this much time to execute...can ne1 tell where m mistaking??

heres my code

#include<stdio.h>
#include<math.h>
int main()
{
    int a,n,prime,l=2;
    printf("Please enter a positive integer.\n");
    printf("To end the program enter a negetive integer.\n");
    while(l>1){
        scanf("%d",&n);
        prime=1;
        if(n<=1) printf("The number is not prime.\n");
        else if(n==2) printf("The number is prime.\n");
        else{
            for(a=2;a<=(int)sqrt(n);a++){
                if(!(n%a)) prime=0;
            }
        if(prime==0) printf("The number is not prime.\n");
        else printf("The number is prime.\n");
        }
        if(n<0){
            break;
        }
        printf("Please enter a positive integer.\n");
        printf("To end the program enter a negetive integer.\n");
    }

    return 0;
}

[rubberman]

Using (int)sqrt(n); as a divisor (for your modulus operation) is not a good idea, since it will cast away the fractional part, resulting in an invalid result. There are other issues as well, but this is a start. Myself, I do some short-cuts (anything ending in even number -> reject, anything ending in 5 -> reject, resulting in reducing your search space to 4 in 10). Anyway, check out the wikipedia article on the Sieve of Eratosthenes for some good information.

[Adak]

Since the number being tested is an integer, and the actual square root value (the floating point value), is meaningless in this context, using just the int value of sqrt(n) is fine - and smart.

However, you are now recalculating this value (the int square root of n), over and over, in your for loop. You should calculate that value BEFORE the for loop begins, and then use it throughout the looping, to test against -- never recalculating it. It's the same value, and getting the square root is an expensive bit of code, requiring MANY cycles.

Once you change this, and change the checks so only odd numbers are tested, you'll see your run time cut by about 2/3rds! ;)

I like your overall program design - very smart.

[aamira_s]

Since the number being tested is an integer, and the actual square root value (the floating point value), is meaningless in this context, using just the int value of sqrt(n) is fine - and smart.

However, you are now recalculating this value (the int square root of n), over and over, in your for loop. You should calculate that value BEFORE the for loop begins, and then use it throughout the looping, to test against -- never recalculating it. It's the same value, and getting the square root is an expensive bit of code, requiring MANY cycles.

Once you change this, and change the checks so only odd numbers are tested, you'll see your run time cut by about 2/3rds! ;)

I like your overall program design - very smart.

Thank you very much.I got your point.At first i checked only odd numbers using the if control statement but my programming trainer seemed to think it meaningless.Thank you again.

[Adak]

I wasn't too clear on that.

You don't want to use an if statement to process only odd numbers - that's still doing SOMETHING with even numbers. You don't want that.

What you want to do is, instead of simply incrementing the number to be tested next by one with number++, use number += 2. That means 2 and 3 have to be done before the final loop through the rest of the numbers.

Try that, you'll like it. ;)