PHPで陳素数を求める

はじめに

この記事では、陳素数をPHPで求める方法について触れています。
とある面談で「陳素数をPHPで求めてください」とお題があり、行き詰まったのがきっかけで記事を書いています。
別言語でも基本的なロジックは変わらないはずですので、カスタマイズしてもらえれば良いかと思います。

陳素数とは

wikipediaより引用

素数 p が陳素数（ちんそすう、Chen prime）であるとは、p + 2 が素数または2つの素数の積（=半素数）であることを意味する。例えば 19 は素数であり、2 を加えた 21 は 3 × 7 と2素数の積で表されるので陳素数である。この名前は、そのような素数は無限に存在すると証明した陳景潤による。
陳素数を小さい順に列記すると次の通り。
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 67, 71, 83, 89, 101, …

つまり、陳素数(ここではpとする)とはp+2が素数または半素数(2つの素数の積)に該当するものを指します。

説明だけだとイメージがわかないため具体例をいくつか提示していきます。
2 → 2+2=4は半素数(4=2×2)なので、2は陳素数
3 → 3+2=5は素数なので、3は陳素数
5 → 5+2=7は素数なので、5は陳素数
7 → 7+2=9は半素数(9=3×3)なので、7は陳素数
・・・・・こんなイメージです。

「素数だけど陳素数ではない数」も例を提示します。
43 → 43+2=45は素数ではない、かつ半素数でもない(45=5×3×3)ので陳素数に該当しません

具体例を提示してイメージが湧いたところで、実装内容を紹介していきます。

PHPで実装

1〜100までで陳素数である数字を表示するプログラムを書いてみました

public function index()
{
    $sosu_list = $this->getSosu();
    // 陳素数かどうかの判定
    foreach ($sosu_list as $num) {
        // num+2が素数であるかどうか
        if (in_array(($num + 2), $sosu_list)) {
            echo $num . "\n";
            // num+2が半素数であるかどうか
        } elseif ($this->checkHansosu($num + 2, $sosu_list)) {
            echo $num . "\n";
        }
    }
}

private function getSosu()
{
    $sosu_list = [];
    $target_num = 100;
    for ($i = 1; $i <= $target_num + 2; $i++) {
        $point = 0;
        for ($j = 1; $j <= $i; $j++) {
            if ($i % $j == 0) {
                $point += 1;
            }
        }

        if ($point == 2) {
          $sosu_list[] = $i;
        }
    }
    return $sosu_list;
}

private function checkHansosu($num, $sosu_list)
{
    foreach ($sosu_list as $v1) {
        foreach ($sosu_list as $v2) {
            if ($v1 * $v2 === $num) {
                return true;
            }
        }
    }
    return false;
}

プログラムの出力結果

2 3 5 7 11 13 17 19 23 29 31 37 41 47 53 59 67 71 83 89

参考

【素数or半素数】陳素数とは｜SOSU Lover (Number Mania)｜note