エラトステネスの篩をPHPで書いてみた

積読の中に「プログラマのためのコードパズル」という本を見つけた。
その中にエラトステネスの篩がJavaScriptで書かれていたのだが、練習のためにPHPに変えて書いてみた。

エラトステネスの篩の仕組み

エラトステネスの篩（ふるい）は素数を見つけ出すアルゴリズム。
やっていることは
１）探索リストから最小の値を取り出して素数リストに加える
２）新規に加えた素数の倍数を探索リストから削除する
３）新規に加えた素数の平方が探索リストの末尾より大きいか確認する。
超えていたら処理を終了。超えていなければループする。

コード

<?php

//「エラトステネスの篩」素数を見つけ出すアルゴリズム.

function primeSearch ()
{
    
//変数.

    $prime_arr = []; //素数リスト.
    $num_arr = []; //探索リスト.
    $start = 2; //開始位置.
    $end = 100; //終了位置.
    $n = $start; //現在確認中の数値.

//開始数値～終了数値を配列に格納.
    for ($i = $start; $i <= $end; $i++)
    {
        $num_arr[] = $i;
    }

//探索リストが空になるまで素数を探索.
    while(count($num_arr))
    {
        //先頭の数値を素数として取得.
        $n = array_shift($num_arr);

        //素数リストに格納.
        $prime_arr[] = $n;

        //素数の倍数を削除.
        //逆向きにループすることで配列を削除しても、そのままのiの値で処理が可能.
        for( $i = count($num_arr)-1; $i >= 0; $i--)
        {
            if($num_arr[$i] % $n == 0)
            {
                array_splice($num_arr, $i, 1);
            }
        }

        //現在の素数の二乗が探索リストの末尾より大きければ終了.
        if ($n * $n > end($num_arr))
        {
            break;
        }
    }

    //残ったリストを素数リストに加えたのが素数の配列.
    //結果の配列を戻して終了.
    return array_merge($prime_arr, $num_arr);

}

print_r(primeSearch());

アマチュアレベルだと、これでも四苦八苦。
逆向きにループしているのが賢いと思った。
プロはこんなコードもサクッと書いてしまうのだろうか？

ちなみに上手い人はもっとスマートに書ける模様。

参考文献：プログラマのためのコードパズルJavaScriptで挑むコードゴルフとアルゴリズム/
柳井政和/技術評論社/2014.3.10初版