RobsonLittle 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 84 is 433

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

© 2004-20 robson | cc unless stated