So I've been doing a bunch of code challenges out of boredom lately, a lot require working with Primes so I wrote a class to help. Wondering if yall SMRT people had any comments on how to improve it or what not:

class PrimeNumber
{
    private static $known = [2,3,5,7,11,13,17];

public static function checkPrime($n)
{
    if ($n < 0) $n = abs($n);

    if ($n < 2) return false;

    if (in_array($n, static::$known)) return true;

    $s = ceil(sqrt($n));
    foreach (static::generator() as $i) {
        if ($i > $s) break;
        if ($n%$i == 0) return false;
    }
    return true;
}

public static function generator()
{
    $index = 0;
    while (true) {
        if (isset(static::$known[$index])) {
            yield static::$known[$index++];
        } else {
            $n = max(static::$known) + 2;
            while (!static::checkPrime($n)) {
                $n += 2;
            }
            static::$known[$index++] = $n;
            yield $n;
        }
    }
}
}

    Not on any of the sites where they run your code =\

      Derokorian wrote:

      So I've been doing a bunch of code challenges out of boredom lately, a lot require working with Primes so I wrote a class to help.

      I think it depends on what exactly are the requirements, e.g., are you supposed/need to test a particular number for primality, or are you supposed/need to generate all primes within a range?

      NogDog wrote:

      I using gmp_prob_prime() allowed?

      Miller-Rabin only determines for sure if a number is composite though... but admittedly with $reps == 10 a number that is not determined to be composite is indeed most probably prime.

        if(function_exists('gmp_prob_prime')) {
    $result = gmp_prob_prime("$n");
    if($result != 1) {
        return (bool) $result;
    } 
}
// do your own prime calculation here

        🙂

          Write a Reply...