Skip to content

Instantly share code, notes, and snippets.

@ozdemirburak
Created April 28, 2017 22:18
Show Gist options
  • Save ozdemirburak/23703a8b1d73642004e05d4991aae8de to your computer and use it in GitHub Desktop.
Save ozdemirburak/23703a8b1d73642004e05d4991aae8de to your computer and use it in GitHub Desktop.
Find all prime numbers up to any given n using Sieve of Eratosthenes.
<?php
/**
* Find all prime numbers up to any given n using Sieve of Eratosthenes.
*
* https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
* https://en.wikipedia.org/wiki/Eratosthenes
*
* @param int $n
*
* @return array|void
*/
function getPrimes($n)
{
if ($n <= 1) {
return;
}
$array = array_fill_keys(range(2, $n), true);
for ($i = 2; $i <= (int) sqrt($n); $i++) {
if ($array[$i] === true) {
for ($j = $i ** 2; $j <= $n; $j += $i) {
$array[$j] = false;
}
}
}
return array_keys($array, true);
}
$primeNumbers = getPrimes(365);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment