# 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 239 is 1499

### 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