Skip to content

Instantly share code, notes, and snippets.

@drupol
Last active September 1, 2020 12:47
Show Gist options
  • Save drupol/ef6f8b618023957953612c4e8b3df1d2 to your computer and use it in GitHub Desktop.
Save drupol/ef6f8b618023957953612c4e8b3df1d2 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes for finding Prime numbers and Twin Prime numbers
<?php
/**
* Run this code with: "php -n <file.php>" to make sure no configuration will be used
* so xdebug will not be used either.
*/
declare(strict_types=1);
include __DIR__ . '/vendor/autoload.php';
use loophp\collection\Collection;
function primesGenerator(Iterator $iterator): Generator
{
yield $primeNumber = $iterator->current();
$iterator = new \CallbackFilterIterator(
$iterator,
fn(int $a): bool => $a % $primeNumber !== 0
);
$iterator->next();
return $iterator->valid() ?
yield from primesGenerator($iterator):
null;
}
function integerGenerator(int $init = 1, callable $succ): Generator
{
yield $init;
return yield from integerGenerator($succ($init), $succ);
}
$primes = primesGenerator(integerGenerator(2, fn(int $n): int => $n + 1));
$limit = 1000000;
// Create a lazy collection of Prime numbers from 2 to infinity.
$lazyPrimeNumbersCollection = Collection::fromIterable(
primesGenerator(
integerGenerator(2, static fn ($n) => $n + 1)
)
);
// Print out the first 1 million of prime numbers.
foreach ($lazyPrimeNumbersCollection->limit($limit) as $prime) {
var_dump($prime);
}
// Create a lazy collection of Prime numbers from 2 to infinity.
$lazyPrimeNumbersCollection = Collection::fromIterable(
primesGenerator(
integerGenerator(2, static fn ($n) => $n + 1)
)
);
// Find out the Twin Prime numbers by filtering out unwanted values.
$lazyTwinPrimeNumbersCollection = Collection::fromIterable($lazyPrimeNumbersCollection)
->zip($lazyPrimeNumbersCollection->tail())
->filter(static fn (array $chunk): bool => 2 === $chunk[1] - $chunk[0]);
foreach ($lazyTwinPrimeNumbersCollection->limit($limit) as $prime) {
var_dump($prime);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment