Ex15 PrimeNumberMemo

From Prog0

素数の判定について

与えられた整数が素数かどうか判定する isPrime関数について考えます。

int isPrime(int a){
  int i;

  if (a == 2) return 1;         /* 2 は素数 */
  if (a%2 == 0) return 0;       /* 2 以外の 2 で割り切れるものは非素数 */
  for (i = 3; i < a/2; i+=2) {   /* 3からa/2までの奇数で割り切れるかを調査 */
    if (a%i == 0) return 0;     /* 割り切れたので非素数 */
  }
  return 1;                     /* 割り切れなかったので素数 */
}

この関数の for ループの上限にはいろいろな別解があるので、整理してみます。

まず大きい方を考えると、ループ継続条件を i <= a とすると、i==a のとき必ず割り切れてしまうので誤り。
i < a あるいは i <= a-1 であれば正しく動作するはずです。（a が奇数のみなら i <= a-2 でもよい）

次に上限をどこまで小さくできるか考えると、a が p で割り切れるとき a == p*q （p, qは整数）と書けますが、 p > q なら先に q で割った時点で素数でないと判定済のはずですね。 したがって p==q となる整数までチェックすれば十分だから、i <= sqrt(a) まで調べればよいわけです。 sqrt関数は math.h をインクルードしないと使えないので、i*i <= a と書いても同じです。

また、偶数は先に素数でないと判定が済んでいて、奇数だけを調べる場合は a == p*q の q が 2 でない事が分かっていますから、 i < a/2.0 か i <= a/2（整数除算の切り捨てで右辺が小さくなるので = をつけた） でも良いはずです。 （じつは = 抜きで i < a/2 とした場合も、条件が微妙になりそうな 7 と 11 がもともと素数なので、結果的には正しく判定できてしまう。） q が 3 以上と考えて i <= a/3 とするともっと良いでしょう。 （なお、a==9 のとき 3 で割りきれて素数でない、と判定する必要があるので、等号無しの i < a/3 は誤り。）