Skip to content

Instantly share code, notes, and snippets.

@bcremer
Created August 27, 2020 07:08
Show Gist options
  • Save bcremer/e4f761a314adacefc42255ca8889d661 to your computer and use it in GitHub Desktop.
Save bcremer/e4f761a314adacefc42255ca8889d661 to your computer and use it in GitHub Desktop.
Generate prime numbers using the Sieve of Eratosthenes, Lazily evaluted with PHP
<?php
// Generate prime numbers using the Sieve of Eratosthenes
// Lazily evaluted
// Inspired by: https://www.youtube.com/watch?v=5jwV3zxXc8E
$primes = sieve(nat(2));
foreach ($primes as $value) {
echo $value . PHP_EOL;
if ($value > 30) {
return;
}
}
function nat(int $start)
{
yield $start;
yield from nat($start + 1);
}
function sieve(Generator $numbers)
{
$number = $numbers->current();
$numbers->next();
yield $number;
yield from sieve(filterMultiplesOf(remaining($numbers), $number));
}
function remaining(Generator $generator)
{
yield from $generator;
}
function filterMultiplesOf(Generator $numbers, int $number)
{
foreach ($numbers as $next) {
if ($next % $number !== 0) {
yield $next;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment