1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 |
- <?php
- declare(strict_types=1);
- enum State {
- case Maybe;
- case Prime;
- case NotPrime;
- }
- function sieve(int $limit): array {
- $all = [];
- $all[0] = State::NotPrime;
- $all[1] = State::NotPrime;
- for ($i = 2; $i <= $limit; $i++) {
- $all[$i] = State::Maybe;
- }
- for ($i = 2; $i <= $limit; $i++) {
- if ($all[$i] == State::NotPrime) {
- continue;
- }
- $all[$i] = State::Prime;
- for ($j = 2; $j <= $limit / $i; $j++) {
- $all[$i * $j] = State::NotPrime;
- }
- }
- $res = [];
- foreach ($all as $i => $v) {
- if ($v === State::Prime) {
- $res[] = $i;
- }
- }
- return $res;
- }
|