#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2013
    Posts
    9
    Rep Power
    0

    Program to find "nth" prime number...


    I am writing a program in C that needs to take the user input:

    what prime number they want to find i.e. the 5th, etc. up to and including the 50,000th prime number.

    I think I'm probably over complicating this, as usual, but here is what I have. I know that I have to use bool to determine true/false on prime/not prime. I'm having trouble connecting the count (as in how many primes have been calculated in relation to the desired prime number) and it's prime value. Also, I'm not sure on the syntax to calculate whether or not a number is prime.

    Here is what I have so far:

    Code:
    #include <stdio.h>
    #include <math.h>
    #include <stdbool.h>
    int main(void)
    {
            unsigned long num;      // prime number to find
            unsigned long prime;    // number to be checked
            unsigned long div;      // potential divisors
            unsigned long count;    // what prime number
            bool isPrime;           // prime flag
    
            printf("For what prime number would you like to find the value?\n");
            scanf("%lu", &num);
    
    while (prime == 1)
    {
            for(prime = 0; count <= num; prime++)
            for(div = 2, isPrime= true; (div * div) <= prime; div++)
            {
                    if (prime % div == 0)
                    {
                            isPrime= false; // number is not prime
                    }
                    if (isPrime)
                    {
                            do
                            {
                                    count = 0, count++;
                            }
                            while (count <= num);
                            printf("That prime number is:\n%lu\n", prime);
                    }
            }
    }
            return 0;
    }
    Can anyone point out what is wrong and steer me in the right direction?

    Thanks!
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,413
    Rep Power
    1871
    Why don't you create a function called say 'isPrime(int n)', so you have a nice simple loop in main which calls it with all the odd numbers. Bump the count each time it returns true.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2013
    Posts
    9
    Rep Power
    0
    Originally Posted by salem
    Why don't you create a function called say 'isPrime(int n)', so you have a nice simple loop in main which calls it with all the odd numbers. Bump the count each time it returns true.
    I'm not 100% on how to go about this, this is what I have so far, but it doesn't work. :confused: Could you point out what is wrong?

    Code:
     #include <stdio.h>
    #include <math.h>
    #include <stdbool.h>
    int main(void)
    {
            unsigned long int nprime;       //the prime number to find
            printf("For what prime number would you like to get the value?\n");
            scanf("%lu", &nprime);
    
            if (nprime == 1)
            printf("That prime number is:\n2\n");
            if (nprime == 2)
            printf("That prime number is:\n3\n");
    
            unsigned long int n;    // number to be checked
            n = 1;
    
            unsigned long int count;
            count = 0;
    
            unsigned long int div;  // potential divisors
            bool isPrime;   // prime flag
    
            for (n = 3; n>= (div * div); n+=2)
            {
                    for (div = 2, isPrime= true; (div * div) <= n; div++)
                    for (count = 0, isPrime= true; count <= nprime; count++)
                    {
                            if (n % div == 0)
                            {
                                    isPrime= false; // not a prime number
                            }
                    }
            if (isPrime)
            if (count = nprime)
                    printf("That prime number is:\n%lu\n", n);
            }
    printf("Bye.\n");
    return 0;
    }
    Thank you!!
  6. #4
  7. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,413
    Rep Power
    1871
    What do you mean, you don't know how to create functions?

    Code:
    int isPrime ( int n ) {
      if ( n == 2 ) return 1;
      if ( n == 3 ) return 1;
      // add some stuff here
      return 0;
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2013
    Posts
    9
    Rep Power
    0
    Originally Posted by salem
    What do you mean, you don't know how to create functions?

    Code:
    int isPrime ( int n ) {
      if ( n == 2 ) return 1;
      if ( n == 3 ) return 1;
      // add some stuff here
      return 0;
    }
    No, I haven't created functions yet. Thank you for the help! ^_^
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2013
    Posts
    9
    Rep Power
    0

    Having trouble with the function...


    This is what I have so far:
    Code:
    #include <stdio.h>
    #include <math.h>
    #include <stdbool.h>
    #define TRUE 1
    #define FALSE 0
    int check_if_prime(int test_int);
    
    int main(void)
    {
    
            int nth_prime, number_of_primes = 1, test_int;
            _Bool isPrime;
    
            printf("Enter the nth_prime to find: ");
            scanf("%d", &nth_prime);
    if(nth_prime<=0)
    return 0;
    if(nth_prime==1)
    printf("The %d Prime Number = 2\n", nth_prime);
    
    int check_if_prime(int test_int)
    {
            int divisor=2;
            while(divisor<=sqrt(nth_prime))
            {
                    if(nth_prime%divisor==0)
                    {
                            isPrime = FALSE;
                            return 0;
                    }
                    else
                            divisor++;
            }
            return 1;
    }
    for(test_int=3; ;test_int+=2)
    {
            if(check_if_prime(test_int)==1)
            {
                    number_of_primes++;
            if(number_of_primes==nth_prime)
            break;
            }
    }
    printf("The %d Prime Number = %d\n", nth_prime, test_int);
    
    return 0;
    }
    It seems to work on small odd input numbers, but doesn't respond on even ones, for example it gives the correct answer for the 3rd prime number etc. but it doesn't print anything for the 4th. Can someone point out where I've gone wrong?
  12. #7
  13. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,413
    Rep Power
    1871
    Here is what your code looks like, when it's indented properly.
    You'll find code a hell of a lot easier if you exercise some discipline when it comes to code presentation.
    Code:
    #include <stdio.h>
    #include <math.h>
    #include <stdbool.h>
    #define TRUE 1
    #define FALSE 0
    int check_if_prime(int test_int);
    
    int main(void)
    {
      int nth_prime, number_of_primes = 1, test_int;
      _Bool isPrime;
    
      printf("Enter the nth_prime to find: ");
      scanf("%d", &nth_prime);
      if (nth_prime <= 0)
        return 0;
      if (nth_prime == 1)
        printf("The %d Prime Number = 2\n", nth_prime);
    
      int check_if_prime(int test_int) {
        int divisor = 2;
        while (divisor <= sqrt(nth_prime)) {
          if (nth_prime % divisor == 0) {
            isPrime = FALSE;
            return 0;
          } else
            divisor++;
        }
        return 1;
      }
      for (test_int = 3;; test_int += 2) {
        if (check_if_prime(test_int) == 1) {
          number_of_primes++;
          if (number_of_primes == nth_prime)
            break;
        }
      }
      printf("The %d Prime Number = %d\n", nth_prime, test_int);
    
      return 0;
    }
    The first big mistake is that check_if_prime() is a nested function. C doesn't have nested functions (though for some bizarre reason, gcc seems to accept it).
    Use these options
    Code:
    $ gcc -pedantic -std=c99 -Wall baz.c -lm
    baz.c: In function ‘main’:
    baz.c:20:3: warning: ISO C forbids nested functions [-pedantic]
    baz.c:11:9: warning: variable ‘isPrime’ set but not used [-Wunused-but-set-variable]
    Moving the function to where it should be, and recompiling...
    Code:
    #include <stdio.h>
    #include <math.h>
    #include <stdbool.h>
    #define TRUE 1
    #define FALSE 0
    int check_if_prime(int test_int);
    
    int main(void)
    {
      int nth_prime, number_of_primes = 1, test_int;
      _Bool isPrime;
    
      printf("Enter the nth_prime to find: ");
      scanf("%d", &nth_prime);
      if (nth_prime <= 0)
        return 0;
      if (nth_prime == 1)
        printf("The %d Prime Number = 2\n", nth_prime);
    
      for (test_int = 3;; test_int += 2) {
        if (check_if_prime(test_int) == 1) {
          number_of_primes++;
          if (number_of_primes == nth_prime)
            break;
        }
      }
      printf("The %d Prime Number = %d\n", nth_prime, test_int);
    
      return 0;
    }
    
    int check_if_prime(int test_int) {
      int divisor = 2;
      while (divisor <= sqrt(nth_prime)) {
        if (nth_prime % divisor == 0) {
          isPrime = FALSE;
          return 0;
        } else
          divisor++;
      }
      return 1;
    }
    
    
    $ gcc -pedantic -std=c99 -Wall baz.c -lm
    baz.c: In function ‘main’:
    baz.c:11:9: warning: unused variable ‘isPrime’ [-Wunused-variable]
    baz.c: In function ‘check_if_prime’:
    baz.c:34:26: error: ‘nth_prime’ undeclared (first use in this function)
    baz.c:34:26: note: each undeclared identifier is reported only once for each function it appears in
    baz.c:36:7: error: ‘isPrime’ undeclared (first use in this function)
    Now you should fix the check_if_prime() function to actually use the supplied parameter, rather than relying on accidental variable matching caused by using a nested function.

    Over to you.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2013
    Posts
    9
    Rep Power
    0

    Talking


    Originally Posted by salem
    Here is what your code looks like, when it's indented properly.
    You'll find code a hell of a lot easier if you exercise some discipline when it comes to code presentation.

    Now you should fix the check_if_prime() function to actually use the supplied parameter, rather than relying on accidental variable matching caused by using a nested function.

    Over to you.
    I typed it according to our instructor's example, but it makes more sense the way you have it presented. I really do appreciate all the help, for whatever reason, the way he explains it makes it more confusing for me. Thank you!

IMN logo majestic logo threadwatch logo seochat tools logo