Prime Number Function

This is a discussion on Prime Number Function within the C Programming forums, part of the General Programming Boards category; I am having a bit of trouble creating a function that will determine if a number is a prime number ...

  1. #1
    Registered User
    Join Date
    Sep 2010
    Posts
    46

    Prime Number Function

    I am having a bit of trouble creating a function that will determine if a number is a prime number or not. I have attempted various ways to do this, and have read up on the Seive of Eratosthenes. Here is my program to find the 1001st prime number. Tell me if I have a glaring mistake.

    Code:
    #include <math.h>
    #include <stdlib.h>
    #include <stdio.h>
    
    bool isPrime(int);
    
    int main()
    {
        int num = 3;
        int counter = 1;
        
        while (counter < 1001)
        {
            if(isPrime(num) == true)
            {
               counter++;
               num++;
            }
            else
               num++;
        }
        
        printf("%d is the 1001st prime number", num);
        system("PAUSE");
        return 0;
    }
    
    bool isPrime(int num)
    {
         int x;
         
         if(num % 2 == 0)
             return false;
            
         for(int x = 3; x < sqrt(num) + 1; x++)
         {
             if(num % x == 0)
             {
                 return false;  //when I return false, will this break from the function and just immediately return false?
                 break;  //I assume this can break the loop, but how do you also break the for loop if you know its false?
             }
         }
         
         if(x == num - 1)  //it got through the loop without returning false so it must be true
              return true;
    }
    Thanks all!
    Last edited by askinne2; 10-29-2010 at 10:24 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,157
    Yes, the glaring mistake is that isPrime does not always return true if its argument is prime, and it does not always return false if its argument is not prime. For example, it will declare that 121 is prime, but 11 is a factor of 121. It will also declare that 2 is not prime, but 2 is prime.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Sep 2010
    Posts
    46
    Quote Originally Posted by laserlight View Post
    Yes, the glaring mistake is that isPrime does not always return true if its argument is prime, and it does not always return false if its argument is not prime. For example, it will declare that 121 is prime, but 11 is a factor of 121. It will also declare that 2 is not prime, but 2 is prime.
    Take a look at my new code, it has some comments where I ask questions in it. Do you minding answering those for me?

  4. #4
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    Yes the return false will return immediately.
    The check at the end is incorrect. x will not get to num - 1 as it is stopped before it reaches sqrt(num) + 1

  5. #5
    Registered User
    Join Date
    Sep 2010
    Posts
    46
    I forgot to post the code where I corrected that. Anyways, my answer isn't coming out correct still. Anyone know what's wrong with this code for finding the 1001st prime number?

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <math.h>
    bool isPrime(int);
    
    int main()
    {
        int x = 3;
        int counter = 0;
        while(counter<1001)
        {
            if(isPrime(x) == true)
              counter++;
            x = x + 2;
        }
        printf("\n");
        counter++; //this accounts for 2 being prime and not evaulating true in isPrime
        printf("%d is the %dth prime number\n", x, counter);
        system("PAUSE");
    }
    
    bool isPrime(int x)
    {
         int y = 2;
         while(y <= sqrt(x))
         {
             if(x % y == 0)
             {
                return false;
             }
             else
                y++;
         }
         return true;
    }

  6. #6
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    There is no such thing as "bool" in C unless you include stdbool.h. I find it is much simpler to just use ints 1 and 0 when I need something to indicate true or false.

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <math.h>
    int isPrime(int x);
    
    int main()
    {
        int x = 3;
        int counter = 1;
        while(counter<1001)
        {
            counter+=isPrime(x);
            x = x + 2;
        }
        x-=2;
        printf("\n");
        printf("%d is the %dth prime number\n", x, counter);
        system("PAUSE");
    }
    
    int isPrime(int x)
    {
         int y = 2;
         while(y <= sqrt(x))
         {
             if(x % y == 0)
             {
                return 0;
             }
             else
                y++;
         }
         return 1;
    }
    Try that. I haven't run it myself, but it should put you on the right track. Be careful - I think need to subtract 2 from x after the loop, I am not sure just from looking at it. I put it in above, I'll leave it to you to check.
    Last edited by KBriggs; 10-29-2010 at 04:01 PM.

  7. #7
    Registered User
    Join Date
    Jun 2005
    Posts
    6,529
    Quote Originally Posted by askinne2 View Post
    I have attempted various ways to do this, and have read up on the Seive of Eratosthenes.
    Out of curiosity, why haven't you actually used the sieve of Eratosthenes?

    Given that your loops in main() are seeking to find primes in increasing order - which is also what the Sieve of Eratosthenes generally seeks to do - not using the sieve strikes me as rather ineffective.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy in reply to you, it is likely you deserve it. Suck it up, sunshine, and read this, this, and this before posting again.

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Originally Posted by askinne2
    I have attempted various ways to do this, and have read up on the Seive of Eratosthenes.
    Out of curiosity, why haven't you actually used the sieve of Eratosthenes?

    << ROFL!! >>

  9. #9
    Registered User
    Join Date
    Sep 2010
    Posts
    46
    Thanks KBriggs. That works perfectly
    Last edited by askinne2; 10-30-2010 at 01:24 AM.

  10. #10
    Registered User
    Join Date
    Sep 2010
    Posts
    46
    Quote Originally Posted by Adak View Post
    Out of curiosity, why haven't you actually used the sieve of Eratosthenes?

    << ROFL!! >>
    I just was trying to make a simple program that did what it had to do, and then I will go and try to make it efficient.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    7927 is a prime number, so either Project Euler is mistaken, or your program missed a number, somewhere.

    Did you remember to include 2 and 3 in your list of primes?

    Edit: That's the problem I see. It doesn't show 2 is a prime.

    I do like your program - it's straight forward and clear.

    Once you get it working accurately (always a first priority), it will gain a nice speed up by assigning a value to the sqrt(x), before the while() loop. Then in the while loop test, there will be no repeating finding the sqrt() of x, with every loop.

    Code:
    int rootx = sqrt(x);
    while(y<rootx) {
    Last edited by Adak; 10-30-2010 at 05:20 AM.

  12. #12
    Registered User
    Join Date
    Sep 2010
    Posts
    46

    Talking

    Quote Originally Posted by Adak View Post
    7927 is a prime number, so either Project Euler is mistaken, or your program missed a number, somewhere.

    Did you remember to include 2 and 3 in your list of primes?

    Edit: That's the problem I see. It doesn't show 2 is a prime.

    I do like your program - it's straight forward and clear.

    Once you get it working accurately (always a first priority), it will gain a nice speed up by assigning a value to the sqrt(x), before the while() loop. Then in the while loop test, there will be no repeating finding the sqrt() of x, with every loop.

    Code:
    int rootx = sqrt(x);
    while(y<rootx) {
    I didn't realize that Euler's problem was to find the 10,001st prime and not the 1,001st prime, lol. That is the 1,001st prime number. Thanks again

  13. #13
    Registered User
    Join Date
    Oct 2010
    Posts
    3
    I wrote a very similer program a while back; the difference is that I take user input to give all prime numbers on an interval (so if you say 1 to 100 then it'll list all he prime's from 1 to 100).

    I use a different way to "test" if it's prime or not; I set up a loop and user the modulus operator, %, to check if numbers divide into a given number...works really well. Here's the code for the program I wrote for it:

    Code:
    #include<stdio.h>
    
    /*
    Programmer: Matt Lane
    Date: 10/18/10
    
    *The purpose of this program is to determine all the prime numbers between to
     numbers input by the user
     
    *For example, if one would like to find all the prime numbers between 1 and 50,
     the program should outprint this: 
         2
         3
         5
         7
         11
         13
         17
         19
         23
         29
         31
         37
         41
         43
         47
         
         
    *Note: the program can only display the last 291 prime's on a given interval.
    */
    
    int main ()
    {
        /*Function prototype*/
        int testprime(int);
        
        /*variable to store the return from testprime*/
        int resultprime;
        
        /*variable to store the interval to test for prime numbers*/
        int a, b;
        
        printf("This program will take an interval [a, b] where a is > b and \n");
        printf("all intergers inside the open interval to be prime. \n\n");
        printf("All the intergers that are prime will be outprinted at the end \n");
        printf("of the program. \n\n");
        
        
        printf("Please input a value for 'a' in the interval: ");
        scanf("%d", &a);
        printf("\n\n");
        printf("Please input a value for 'b' that is > than 'a' in the interval: ");
        scanf("%d", &b);
        
        
        
        printf("The following numbers are prime on the interval [%d, %d]: \n",a,b);
        
        while (a <= b)
        {
            resultprime = testprime(a);
            
            if (resultprime == 0)
            printf("\n%d", a);
            
            a++;
        }
        
        
        /*Initilize hold variable*/
        char holdprogram;
        
        /*This is to stop the program so that the user can read what
          is being displayed*/
        fflush(stdin);
        printf("\n\n\n\nThe program is completed. \n\n\n");
        printf("Press enter to continue. \n\n");
        scanf("%c", &holdprogram);
        
        
        /*Return a value for the int main ()*/
        return 0;
        
    }
    
    /*function header*/
    int testprime(int inputvalue)
    {
        
        /*The variable that will be the counter-control for the loop*/
        int i;
        
        /*The variable that will be used to test if a given number divides evenly
          into the inputvalue*/
        int testforfactor;
        
             /*Set i = inputvalue to ensure the loop runs the proper number of 
               times but doesn't change the inputvalue's value*/
             i = inputvalue;
             
             /*Initilize testforfactor to 0; this is important because if the user
               inputs a number < 1 the while loop will never start; so initilizing
               this variable to 0 will make the program declare the input is NOT
               a prime number since the lowest prime number is > 1 - which will go
               through the loop*/
             testforfactor = 0;
             
             /*2 is a special prime number because the definition of a prime number
               is that the prime number is only divisble by itself and 1; well, do
               to the proedure used to calculate that property - 2 will be 
               considered not prime because it will return a "1" in the while loop
               while testforfactor is still = 0*/
             if (inputvalue != 2)
             { /*if 1 statement*/
                  
                  /*This if statment redirects what will be output if the user
                    inputs a negative number*/        
                  if (inputvalue >= 0)
                  { /*if 2 statement*/
                        
                        /*Inilialize the while loop; i = inputvalue...to test if 
                          a number is prime one must check if numbers BETWEEN the 
                          value itself and 1 (not including itself and 1) will 
                          divide evenly into it*/
                        while (i > 1)
                        { /*while 1 statement*/
                              
                              /*As previously stated, the program must test all 
                              values between itself and 1; so the loop needs to
                              lower i so that it is =/= inputvalue but still test
                              if the new "i" will divide evenly into inputvalue*/
                              i--;
                              
                              /*This if statement forces the program out of the loop
                              once it comes back the final time; because it doesn't
                              decrease the value of i until AFTER the test for the 
                              while loop occurs...meaning that when i = 2 at the end
                              of one loop it goes through again but will = 1 and 
                              will ALWAYS divide evenly*/
                              if (i == 1)
                                  
                                  /*So we break out of the while loop before we test
                                  if i = 1*/
                                  break;
    
                              /*This is the test for factors of the inputvalue; if
                                a certain number between inputvalue and 1 divides
                                evenly, then testforfactor will = 0; if no values
                                divide evenly then testforfactor will always be
                                > 0*/
                              testforfactor = inputvalue % i;  
                              
                              /*If testforfactor = 0, then the number is not prime,
                                so the program needs to break out of the loop at 
                                this point if that is true*/
                              if (testforfactor == 0)
                          
                                  /*And the break statement brings it out of the
                                    loop*/
                                  break;
                              
                              
                        } /*while 2 statemnt*/
                        
                  /*If the while loop successfully goes through then that
                    means that testforfactor will never = 0 - which means the
                    inputvalue is a prime number*/
                  if (testforfactor != 0)
                            
                  /*Output that the inputvalue is a prime number because 
                    it passed all the tests to qualify as such*/
                    inputvalue = 0;
                        
                  /*If testforfactor DOES = 0, it means that the while loop
                    hit it's break statment and that the inputvalue is not
                    a prime number */    
                  
                  else
                        
                    /*Output that the inputvalue is not a prime number
                      because it did not pass all the test*/
                      inputvalue = 1;
    
    
                  } /*if 2 statement*/
                  
                  /*This else statement corosponds with input value being < 0 */      
                  else
                  
                      /*Output that the inputvalue was negative and, therefore, 
                        can not be a prime number*/
                      inputvalue = 1;
                        
                            
             } /*if 1 statement*/
             
             /*This else corosponds with input vlaue being = 2; */
             else
             
                 /*Output that the inputvalue was 2 and, be the definition of a
                   prime number, it is a prime number*/
                 inputvalue = 0;
                 
                 
                 
        return inputvalue;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 03:39 PM
  2. Change this program so it uses function??
    By stormfront in forum C Programming
    Replies: 8
    Last Post: 11-01-2005, 08:55 AM
  3. help with a source code..
    By venom424 in forum C++ Programming
    Replies: 8
    Last Post: 05-21-2004, 01:42 PM
  4. Creating a student grade book-how?
    By Hopelessly confused in forum C Programming
    Replies: 5
    Last Post: 10-03-2002, 09:43 PM
  5. qt help
    By Unregistered in forum Linux Programming
    Replies: 1
    Last Post: 04-20-2002, 10:51 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21