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 42 is 181

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-17 robson | cc unless stated