Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C program-prime

  1. Dec 10, 2007 #1
    Ive wrote a C program to find out whether a number is prime. But it doesnt 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;
    }
     
  2. jcsd
  3. Dec 10, 2007 #2
    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?
     
  4. Dec 10, 2007 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

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

    Code (Text):
    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:

    Code (Text):
    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;
     
  5. Dec 10, 2007 #4
    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;
    }
     
  6. Dec 10, 2007 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  7. Dec 10, 2007 #6
    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
     
  8. Dec 10, 2007 #7
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: C program-prime
  1. C Program (Replies: 3)

  2. C program (Replies: 0)

  3. C programming (Replies: 9)

Loading...