【PHP】素数を求めるプログラム

2022年7月14日

素数を全て表示するプログラムと素数の個数を求めるプログラムを紹介します。

素数とは

素数とは、「1」とその数以外に約数を持たない自然数（正の整数）のことです。

・「5」の約数は「1」「5」なので、「5」は素数です。

・「8」の約数は「1」「2」「4」「8」なので、「8」は素数ではありません。

つまり、nが素数である条件は「1」とｎの2つの数でしか割り切れないことになります。

素数を全て表示するサンプルプログラム

1から100までの素数を表示するプログラムです。

<?php
    for($i = 2; $i <= 100; $i++) {
        $flag = 0; //判定の初期化
        
        for($j = 2; $j < $i; $j++) { 
            if($i % $j == 0) { //(n-1)までの数の素数判定
                $flag = 1;
                break;
            }
        }
        if($flag == 0) {
            echo $i. "\n";
        }
    }
?>

<?php

for($i = 2; $i <= 100; $i++) {

$flag = 0; //判定の初期化

for($j = 2; $j < $i; $j++) {

if($i % $j == 0) { //(n-1)までの数の素数判定

$flag = 1;

break;

}

if($flag == 0) {

echo $i. "\n";

}

出力結果

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

二重ループを理解する

二重ループの処理は以下の表を見てみると分かりやすいと思います。

i／j	2	3	4	5	6	7	8	9
2
3	×
4	〇	×
5	×	×	×
6	〇	〇	×	×
7	×	×	×	×	×
8	〇	×	〇	×	×	×
9	×	〇	×	×	×	×	×
10	〇	×	×	〇	×	×	×	×

縦の要素iが素数であるかの判定で、〇は割り切れる、×が割り切れないという表になっています。

横の行で〇が一つもない数が素数となります。

素数の個数を求めるサンプルプログラム

100までの素数の個数を求めるプログラムコードです。

<?php
    $count = 0;
    
    for($i = 2; $i <= 100; $i++) {
        $flag = 0; //判定の初期化
        
        for($j = 2; $j < $i; $j++) { 
            if($i % $j == 0) { //(n-1)までの数の素数判定
                $flag = 1;
                break;
            }
        }
        if($flag == 0) {
            $count ++;
        }
    }
    echo $count. "\n";
?>

<?php

$count = 0;

for($i = 2; $i <= 100; $i++) {

$flag = 0; //判定の初期化

for($j = 2; $j < $i; $j++) {

if($i % $j == 0) { //(n-1)までの数の素数判定

$flag = 1;

break;

}

if($flag == 0) {

$count ++;

}

echo $count. "\n";

出力結果

100までの素数は（2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97）の計25個なので正しい結果になりました。

素数を全て表示するプログラムを少し変えて、個数を数えています。

以上です。

素数とは

素数を全て表示するサンプルプログラム

出力結果

二重ループを理解する

素数の個数を求めるサンプルプログラム

出力結果

カテゴリー