PHPで素数判定

何かで素数判定がどうちゃらこうちゃらみたいな記事を読んだので、自分も作ってみようと思ってパパッと1〜100までの素数判定プログラム書いてみました。

素数とは

そもそも素数とは*1とその数自身以外に約数がない正の整数*らしいです。
1とその数自身でしか割り切れないということで約数を2つしか持ちません。
この性質を使ってプログラムを組んでいこうと思います。

コード

まずは大まかな流れです。

for ($i = 1; $i <= 100; $i++) {
  if ($iが素数なら) {
    echo $i
  }
}

次に、$iが素数かどうかを判別する方法ですが
ここで約数を2つしか持たない性質を使います。

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

  $point = 0;

  for ($j = 1; $j <= $i; $j++) {
    if ($i % $j == 0) {
      $point += 1;
    }
  }

  if ($point == 2) {
    echo $i . "\n";
  }

}

$iが$jで割り切れる度に$pointに1を加算していくので、 $iが素数であるなら$pointの値は2になります。出力結果は以下です。

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

まとめ

調べてみたら素数を判定するのにも色々な方法があるんですね。今はあまり気が乗らないので時間ある時にでも見てみようと思います。