Skip to content

enhancement: Prime number generator #2

@Viktorminator

Description

@Viktorminator

Hey @dbierer !
At first, thank you for the great book! I don't have your email, so github seems a right place to send you a message.
I've recently saw that algorithm for Prime number generator can be slightly improved (p.333 in the PHP 7 Programming Cookbook).
From

function generatePrimes($max)
{
    yield from [1, 2, 3];
    for ($x = 5; $x < $max; $x++) {
        if ($x & 1) {
            $prime = TRUE;
            for ($i = 3; $i < $x; $i++) {
                if (($x % $i) === 0) {
                    $prime = FALSE;
                    break;
                }
            }
            if ($prime) yield $x;
        }
    }
}

to

function generatePrimes($max)
{
    yield from [1, 2, 3];
    for ($x = 5; $x < $max; $x++) {
        if ($x & 1) {
            $prime = TRUE;
            for ($i = 3; $i <= sqrt($x); $i++) {
                if (($x % $i) === 0) {
                    $prime = FALSE;
                    break;
                }
            }
            if ($prime) yield $x;
        }
    }
}

Only slight change in for $i <= sqrt($x)
I hope you find it useful.

Best!

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions