{{ message }}

Instantly share code, notes, and snippets.

# icio/get_prime.php

Created Mar 22, 2011
N-th Prime Numbers
 */ /** * Calculate the n-th prime number(s). * * This function operates on the realisation that a number is prime if a factor * cannot be found in the primes less than it (since all numbers can be expressed as * a product of primes). We can further optimise this process by only considering * primes less than or equal to the square root as potential factors. * * @param int|array \$nth * The index/indices of the primes you want. * @param int|false \$t * The number of seconds to allow for calculation, or false (denoting no * time limit (though bare max_execution_time in mind)). * @param int \$tCheck * How frequently (in terms of numbers tested for being prime) a breached * time limit is checked for. * * @return int|array|null * Returns an integer if \$nth is an integer and an array if \$nth an * array. The array is associative of the form \$n => get_prime(\$n), where * \$n is an integer within the original \$nth array. * If the time limit is reached, null is returned where \$nth is an * integer and an array with any computed primes is returned where \$nth * is an array. */ function get_prime(\$nth, \$t = false, \$tCheck = 1000) { // Transform the arguments into a common form and discard bad n-th's \$singular = !is_array(\$nth); \$nth = array_filter((array) \$nth, function(\$n) { return is_int(\$n) && \$n > 0; }); if (!\$nth) return \$singular ? null : array(); // The n-th prime we're aiming for \$n = max(\$nth); // The first prime is the only even one \$primes = array(1 => 2); if (\$n == 1) { return \$singular ? \$primes[1] : \$primes; } // Loop counters \$c = 1; \$p = 3; \$begin = microtime(true); while (true) { // Check if \$p is prime \$prime = true; \$sqrt = sqrt(\$p); for (\$i = 1; \$i < \$c && \$primes[\$i] <= \$sqrt; \$i++) { if (\$p % \$primes[\$i] == 0) { \$prime = false; break; } } // Record \$p if prime if (\$prime) { \$primes[++\$c] = \$p; if (\$c == \$n) { break; } } // Check if time limit expired (every \$tCheck passes) if (\$t && (\$p % \$tCheck <= 1) && (microtime(true) - \$begin) > \$t) { break; } // Next \$p to check \$p += 2; } if (\$singular) { return isset(\$primes[\$n]) ? \$primes[\$n] : null; } else { return array_intersect_key(\$primes, array_fill_keys(\$nth, null)); } } /* * ============= * USAGE EXAMPLE */ ?>

The 1,000th prime number:

get_prime(1000);

In trying to calculate the 10,000th prime we limit ourselves to 0.1 seconds. Where this is not enough time the function will bail and return null.

get_prime(10000);
get_prime(10000, 0.1);

Array functions can be used to get a set of primes…

array_map('get_prime', range(0, 50));

… but it is far more efficient to request them all from get_prime simultaneously. The resultant array will be slightly different.

get_prime(range(0, 50));
Call took ', \$t, ' seconds.'; if (\$dump) var_dump(\$result); return \$result; }

### skywarth commented Apr 17, 2021

 Splendid