에라토스테네스의 체 구현 함수 eratosthenes()

1 개요

에라토스테네스의 체 구현
함수 eratosthenes()
함수 primes_sieve()

2 PHP

<?php
function primes_sieve($size) {
    $a = array_fill(0,$size+1,false);
    for($i=2; $i<$size; $i++) $a[$i] = true;
    $sqrt_size = sqrt($size);
    for($i=2; $i<$sqrt_size; $i++) {
        for($j=$i*2; $j<$size; $j+=$i) $a[$j] = false;
    }
    return $a;
}
echo json_encode( primes_sieve(10) );
# [false,false,true,true,false,true,false,true,false,false,false]
print_r( primes_sieve(10) );
# Array
# (
#     [0] => 
#     [1] => 
#     [2] => 1
#     [3] => 1
#     [4] => 
#     [5] => 1
#     [6] => 
#     [7] => 1
#     [8] => 
#     [9] => 
#     [10] => 
# )

3 같이 보기