Prime numbers

[Skorpion]

HI
can some one figure out my mistakes in this program?

#include<stdio.h>
#include<conio.h>
void main ()
{
int num,i;
clrscr();
printf("\nprint any number:");
scanf("%d",&num);
for (i=2; i==num; i++)
{
if (num%i==0)
printf("\nprime number");
else
printf("\nnot a prime number");
}
getch();
}

i want that it tell the user whether the given number is a prime number or not.

[Luckychap]

In line no 9: for (i=2; i==num; i++)
It should be: for (i=2; i<num; i++)

AND

your logic for prime number is absolutely wrong.

Should be like this:

#include<stdio.h>
#include<conio.h>
void main ()
{
    int num,i, isPrime=1;
    clrscr();
    printf("\nprint any number:");
    scanf("%d",&num);
    for (i=2; i<num; i++)
   {
       if (num%i==0) {
           isPrime = 0;
           break;
      }
   }
    if(isPrime)
        printf("\nThe number is PRIME");
    else
        printf("\nThe number is NOT PRIME");

   getch();
}

[csurfer]

A small addition to both the codes mentioned above.

The rule for being a Prime Number in maths states that a number is prime if it cannot be divided by any number (actually any prime number ) <= the square root of the number given.

that is:

for( i=2 ; i <= (int)sqrt(num) ; i++)

hence if you modify code as

#include<math.h>
//other includes

int main()
{
//your declarations

int sqr,prime=1;

//Accepting the number

sqr=(int)sqrt(num);

for(i=2;i<=sqr;i++)
{
                   if(num%i==0)
                   {
                                prime=0; 
                   }
}
if(prime)
                 printf("Prime number");
else
                 printf("Non prime");
return 0;
}

By applying the above mentioned rule you can reduce the number of comparison to nearly half and hence the efficiency increases highly in case of large numbers. Other mistakes have been rectified in post by "lucky chap".

[nucleon]

csurfer makes an important point about testing only up to the square root of num. It will actually reduce the number of comparisons to much less than half. For example, with the number 101 you only need to test up to the number 10 -- quite a savings!

To reduce that number of comparisons by half again, you can test 2 separately and then only test odd numbers (stepping by 2 in the for loop), something like this:

sqr = (int) sqrt (num);
if (num % 2 == 0)
    isPrime = 0;
else
    for (i = 3; i < sqr; i += 2)
    ...

[Skorpion]

thanks everyone i got it.