# Robson ▸ Little Red Book ▸ The N'th prime number

## Chapter 7 - Question 8

Given as input a positive integer, of not too high a value, say below 1000, calculate the N'th prime number.

### Solution 1

Finding the 1000th prime takes about 0.35 seconds on a P4-2.2GHz. I've limited the maximum number to 250 to reduce the amount of processing the server has to do.

`<?` `    // generate a random number` `    \$n = mt_rand(1, 250);` `    // start off the primes array` `    \$primes = array(2);` `    ` `    // set test to 1 to begin with` `    \$test = 1;` `    while (count(\$primes) < \$n)` `    {` `        // only test odd numbers` `        // because all even numbers aren't primes` `        \$test+=2;` `        // assume it's prime unless we can prove otherwise` `        \$is_prime = true;` `        // loop through all the current primes` `        foreach(\$primes as \$prime)` `        {` `            // if the prime is more than half it's value,` `            // none of the following ones will work, so break now` `            if (\$test/2 < \$prime)` `                break;` `            // test if it divides exactly` `            if (!(\$test % \$prime))` `            {` `                // if so, it's not a prime number` `                \$is_prime = false;` `                // break now` `                break;` `            }` `        }` `        // if we an't prove otherwise, it's a prime number` `        if (\$is_prime)` `            // add it to the list` `            \$primes[] = \$test;` `    }    ` `    ` `    // show the n'th prime number` `    echo 'Prime ' . \$n . ' is ' . array_pop(\$primes);` `?>`

Which produces:

Prime 201 is 1229

### Solution 2

J can be used to show prime numbers easily.

p: 47
223

Prime numbers start at 0, not 1. So prime number 47 in theory is actually 48.

## Log

• May 16, 2005 - Added solution 2.
• May 2, 2005 - Added solution 1.
© 2004-20 robson | cc unless stated