Find Prime Numbers in C Program | Quick and Easy Method

[Dili]

Ive wrote a C program to find out whether a number is prime. But it doesn't work on some numbers, eg 25
Any help, ideas are most welcome

#include<stdio.h>
#include<math.h>
int main()
{
int j,number;
scanf("%d",&number);
if(number<=1)
return 0;
else if(number==2)
return 1;
else
for(j=3;j<(int)sqrt(number);j+=2)
{
if(number%j==0)
printf("not prime\n");
else
printf("prime\n");
return 1;
}
return 0;
}

 

[arunbg]

Again problem with loops. Within the for loop note that if the no. is not divisible by any j, then it prints prime, which is wrong. Instead you should use a flag of some sort to indicate that within the loop at least one instance of j has divided the no. There are other errors like j+=2, which should be done only if you have checked that the no. is not even earlier.
Can you make the corrections and post the revised code?

 

[CRGreathouse]

You need to check for divisibility by 2, and you need to include the square root of the number.

if (number%2 == 0)
  return n == 2;
if (number <= 1)
  return false;
for (j = 3; j <= (int)sqrt(number); j += 2)
  if (number % j == 0)
    return false;
return true;

Faster:

int root;
if ((number&1) == 0)
  return n == 2;
if (number < 9)
  return number > 1;
root = (int)sqrt(number);
for (j = 3; j <= root; j += 2)
  if (number % j == 0)
    return false;
return true;

 

[Dili]

prime

i modified the code. but there is an error.
After 55 every number incremented by 10 is said as prime\
(eg; the program says that 55,65,75... are primes)
can anyone have any idea?
furthur how do you modify the code so that when 2 is given it is returned prime??

here is the code
#include<stdio.h>
#include<math.h>
int main()
{
int a,j,number;
scanf("%d",&number);
if(number<=1)
return 0;
if(number%2==0)
return 0;
for(j=3;j<=(int)sqrt(number);j+=2)
{
a=number%j;
}
if(a==0)
return 0;
else
printf("prime\n");

return 0;
}

 

[CRGreathouse]

Your braces are wrong (the problem is not just with multiples of 5, if you go higher you'll find other composites are declared prime). If you want to handle 2 properly you'll have to replace the "return false" after your divisibility by 2 test with braces including an if statement checking if the number is two, and only then returning.

 

[Dili]

i managed to correct 2 by putting anf if statement in the beginning
if(number==2);
printf("prime\n")

but can you tell where i should put the braces??

Thank you for all the help anyway. you posted a lot of replies to the questions

 

[out of whack]

You will find it enormously useful to learn how to trace the execution of your programs with a debugger. I don't know what you are currently using but integrated development tools like Visual Studio or Code::Blocks make this very easy to do (these two are free, by the way). Tracing your code will show you when the logic of your program goes wrong.

For this particular program the "for" loop does not contain any check for primality, which you put after the loop when it is too late. The braces are wrong is another way of saying that your prime check is not included within the loop (the check will also need to be corrected). Situations like this will be obvious when you execute your code line by line with a debugger, and their solution will also become more apparent.