^216）素数を表示する計算量の話

Twitterで「2から100までの素数を出力するプログラムを書け」という文と共に次のようなコードをみかけた（Cに書き直してある）。

#include <stdio.h>

int main(void)
{
  printf("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");

  return 0;
}

この類のコードは昔からネタ的に見かけるんだけど、今見ると意外とありだな、って思った。素数は絶対に変わらない値だし、素数をテーブルで保存しておいて、素因数分解することだってできる。まあ実際に使うなら、ファイルに書き出しておいて、それを読み込む形になるとは思うけど。

文系のぼくが素数を判定するコードを書くなら、試し割り法という簡単な方法で書く。というかこれしか思いつかない。もし、2未満の値であれば偽を返し、そうでない場合は要素nをn/2までの各値で割っていき、割れきれなければ真を返す。

//C99
#include <stdio.h>
#include <stdbool.h>

static bool isPrimeNumber(int n)
{
  if (n < 2) {
    return false;
  }

  for (int i = 2; i <= n/2; i++) {
    if (n % i == 0) {
      return false;
    }
  }

  return true;
}

割る値をn/2にしたのは、要素nが割り切れるかを試す値がn/2を超えることが絶対にないからだ。しかし、Wikipediaの「エラトステネスの篩」の項を読んでみると、どうやらnの平方根までの計算でいいらしい。そりゃそうだ。自分の数学センスのなさが表れている。

9行目をmath.hのsqrt()関数（square root）を使って、次のように書き直す。

  for (int i = 2; i <= sqrt(n); i++) {

さて、n/2とsqrt(n)で速度がどの程度違うのか気になったので調べてみた。値が小さいと恩恵が少ないので、100万まで数字を与えてその中から素数を表示させた。

速い、めっちゃ速い。i <= n/2がi < nの半分ほどの時間になっているのは納得だけど、i < sqrt(n)はそこから更に88倍速い計算になっている。もっと大きな数字でも試してみた。

2022-05-07