{{ message }}

Instantly share code, notes, and snippets.

# icio/get_prime.php

Created Mar 22, 2011
N-th Prime Numbers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 */ /** * 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 : \$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

to join this conversation on GitHub. Already have an account? Sign in to comment