Thread: Calculating the nth prime number

Hey guys,

I am taking a Intro to C programming class and I am doing an assignment that will calculate the nth prime number. I think, since its earlier on in the class, it should be sort of basic, where efficiency isn't the most important factor at this moment.

I am having issues figuring out the layout of the coding. Does anyone have a good layout that I could run off of? For example, this is what I have so far:

1. start

2. ask for nth prime number

3. begin loop one for test_int

4. is test_int prime?
if no, go back to 3
if yes, add to a counter

As you can see, I really have no idea on the layout I need for this. Any help is appreciated, thanks!

How much have you done, because that sounds like something that will work and it's also basic.

You seem to be using C99 (or higher), which is good, but you use _Bool and define your own TRUE and FALSE, which you then don't use, trying to use true and false instead (which you haven't defined). The proper thing to do is to include <stdbool.h>, which defines bool, true, and false. You should also ensure you are actually compiling as C (and not C++), which requires changing a setting somewhere in MSVC (if that's what you're using).

Your if (isPrime) test needs to be after the inner loop. You've also accidentally used = true instead of == true, but really you should just say if (isPrime).

You can increase the efficiency dramatically by only testing divisors up to and including the square root of test_int. In a quick test for finding the 20000th prime, it took 7.4 seconds the way you have it and 0.04 seconds by only testing up to the square root. That's 185 times faster. The millionth took 12.8 seconds the fast way, and I-have-no-idea-how-long the slow way.

You can double the efficiency yet again by testing 2 separately and then only testing odd numbers using odd divisors after that. Making that change finds the millionth prime in 6.4 seconds on my little laptop.

Originally Posted by whiteflags

Personally, I wouldn't promise that trial division produces results that fast. On my Intel Core i5 machine, even doing all of that, finding the millionth prime takes about a minute.

Your results are so fast that I'm inclined to think you found a different number. The millionth prime, for the sake of checking, is 15,485,863.

Good point. But just to make sure, I've PM'ed you some code to try. And make sure you're not watching a movie, downloading something, etc., at the same time.

Yes, that's the number I found.

To clarify, whiteflags had a small error in his code that slowed it down. Fixing that gave a time of around 6 seconds.

Furthermore, it's pretty simple to modify the code so that instead of stepping the divisors by 2, you can step them by 6 and do two modulus calculations in the inner loop. This reduces the time (for me at least!) from 6.5 to 4.5 seconds to find the millionth prime.

That's probably about as good as you can do for the trial divisor method. A very simple sieve algorithm (that takes no more code than the divisor method) reduces the time to find the millionth prime to about a quarter second. It finds the 50 millionth prime (982451653) in about 21 seconds.

Okay, so I did some more work on my code. I am starting to get down the layout of a basic system. I am trying to figure out whats going on because the code will only give out test_int to be (nth_prime + 1).

I set nth_prime to 10 temporarily to more quickly debug the system. I can't seem to figure out where I went wrong with this layout and why its not outputting the right test_int.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TRUE 1
#define FALSE 0


int main()
{
    int nth_prime, number_of_primes, test_int, divisor;
    _Bool isPrime;




    nth_prime = 10;
    /*printf("Enter the nth prime number:");
    scanf("%i", &nth_prime);*/


    number_of_primes = 0;
    test_int = 1;




    do
    {




        test_int++;
        divisor = 2;


        while( divisor < test_int )
        {


            isPrime = TRUE;
            if(test_int%divisor == 0)
            {
                isPrime = FALSE;
                break;
            }
            divisor++;


        }
        if (isPrime = TRUE)
        {
            number_of_primes++;
        }


    }
    while (number_of_primes < nth_prime);


    printf("Prime number %i is equal to %i", nth_prime, test_int);


    return 0;
}

Originally Posted by algorism

You're not understanding what I said about stdbool.h. When you include it, you use bool instead of _Bool. You also get rid of your TRUE and FALSE declarations and just use true and false instead (which are defined, along with bool, in stdbool.h).

Also, you ignored my point about = vs ==. You're using the wrong one when testing isPrime after the loop.

Anyway, the 10th prime is 29. Your code (as is) returns 11, the 5th prime. So it's off by way more than 1.

Also, a timing update for anyone who's interested (probably nobody ). Due to an error in my sieve code, it was slower than it should have been. Now it finds the millionth prime in 0.065 seconds, the 50 millionth in about 15 seconds, and the 100 millionth in about 32 seconds.

I wasn't ignoring you. I was given partial code from my teacher that was written that way, which is the only reason I am even using isPrime(I assume my teacher put it in there for a reason). I am using CodeBlock to write my code right now because the code that has to be submitted is written in Putty, which might be slightly different. That is what got me confused, but now I think I understand it better in terms of using it in coding.

You have to understand that I literally started learning about C roughly 3 weeks ago, so I only know the very basic things. I am trying to figure out to even get a functioning code to do what I wanted it to do.

The code I made just gives the a (nth_prime + 1) output. If you take out the printf and scanf comment, you can test it out.

Your isPrime = true line should probably be before the while, although it doesn't really matter. Actually, you don't really need isPrime at all since you could just test your break condition again. Believe it or not, a goto is probably the best solution ... but don't do it! It's evil! (apparently)

How do I test the break condition?

Also, you ignored my point about = vs ==. You're using the wrong one when testing isPrime after the loop.

So this helped a lot, sorry I didn't notice this before. After updating it, I am getting the (n+1)th answer. It isn't counting 2 as a prime number, which I think I understand why now.

EDIT: Here is my updated code. After so much thinking and your help, I finally figured it out! PHEW! Now, I am going to try to see if I can clean it up a bit and make it run a bit faster.

Code:

#include <stdio.h>#include <stdlib.h>
#include <stdbool.h>
#define TRUE 1
#define FALSE 0


int main()
{
    int nth_prime, number_of_primes, test_int, divisor;
    bool isPrime;




    //nth_prime = 10;  //use for testing
    printf("Enter the nth prime number:");
    scanf("%i", &nth_prime);


    number_of_primes = 1;
    test_int = 1;


    if (nth_prime == 1)
    {
        printf("Prime number 1 is equal to 2\n");
        return 0;
    }




    do
    {




        test_int++;
        divisor = 2;




        while( divisor < test_int )
        {


            isPrime = true;
            if(test_int%divisor == 0)
            {
                isPrime = false;
                break;
            }
            divisor++;


        }
        if (isPrime == true)
        {
            number_of_primes++;
        }


    }
    while (number_of_primes < nth_prime);


    printf("Prime number %i is equal to %i", nth_prime, test_int);


    return 0;
}

I didn't know your teacher said you had to use TRUE and FALSE and _Bool and isPrime, but if that's the case then that's okay. It's not really wrong. Get rid of stdbool.h, then. Remember to use _Bool, TRUE and FALSE, not bool, true and false. (And forget about testing the break condition again; that's just a way of getting rid of the isPrime variable, which is not important.)

Since you're testing the 1st prime (2) separately, that means you want to start your test_int and divisor at 3 and increment them by 2. (That's the whole point of testing the first prime separately, so that now you can make the rest of the program go twice as fast by going up by 2's.) Since you increment test_int as the first instruction in the loop, you want to start it at 1 (like you do) but increment it by 2. Start divisor at 3 and increment it by 2 as well, at the end of its loop.

If you really want to speed it up, though, you need to only test divisors up to and including the square root of test_int. The easiest way to do that is make your test while (divisor * divisor <= test_int).

Absolutely solid advice, thanks so much for your help. I sort of redid my entire coding after some classes learning about this assignment more. I also included functions to the code as well. Here is my updated code if anyone is interesting.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define TRUE 1
#define FALSE 0


_Bool check_if_prime(unsigned int);


int main()
{
    unsigned int nth_prime, number_of_primes, test_int;
    _Bool isPrime;


    printf("Enter the nth prime number: ");
    scanf("%u", &nth_prime);


    if(nth_prime == 1)
    {
        printf("Prime number 1 is equal to \"2\"");
        return 0;
    }


    number_of_primes = 1;
    test_int = 1;


    do
    {
        test_int+= 2;
        isPrime = check_if_prime(test_int);


        if(isPrime == TRUE)
            number_of_primes++;
    }
    while( number_of_primes < nth_prime);


    printf("Prime number %u is equal to \"%u\"\n\n", nth_prime, test_int);


    return 0;
}


_Bool check_if_prime(unsigned int test_int)
{
    unsigned int divisor;
    _Bool isPrime;
    isPrime=TRUE;


    for (divisor = 3; (divisor * divisor) <= test_int; divisor+= 2)
    {
        if(test_int%divisor == 0)
        {
            isPrime = FALSE;
            break;
        }
    }
    return isPrime;
}