作曲・指導・C言語・Linux

金沢音楽制作

金沢音楽制作では、楽曲・楽譜の制作と、作曲や写譜などレッスンを行っています。


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.hsqrt()関数(square root)を使って、次のように書き直す。

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

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

条件式 走査数 速度
i < n 1000000 1m32.011s
i <= n/2 1000000 0m44.574s
i <= sqrt(n) 1000000 0m0.551s

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

条件式 走査数 速度
i <= sqrt(n) 100000000 2m39.402s

これをi < nで律儀に計算してたら、とんでもなく時間がかかりそうだ。今まで計算量を意識したことはないが、一部を変更するだけでここまで差がでるのなら、今後少しだけ意識しようと思う。

2022-05-07