C言語教室 第22回 - 素数を求める

だいぶ前に

素数の魅力

という記事を書いたのですが、この記事のPVが毎週コンスタントにあり、全体としてもかなり上位のPVを持つページになっています。素数って人気があるんですね。

これも、少し前になるのですが、お世話になっている AyumiKatayama さんの

Prime numbers sieve C言語化編

を読んで、この話に参加しようと思っていました。やってみたかったことはリストを使うので、リストの説明が済んだので、ようやく書けるところまで来ました。もっとも、この記事の主旨とは少しずれているかもしれませんが、そこは悪しからず。

---

ということで、今回は素数を求めるプログラムを書いてみます。素数を求めるには、エラトステネスの篩という方法を使うのが簡単です。

エラトステネスの篩

エラトステネスの篩 - Wikipedia

自然数の一覧を用意して、最も小さな数から、その数の倍数を捨てて、数を増やしつつ、最終的に残った数が素数になるよという方法です。

ドイツ語版ウィキペディアのSKoppさん - 投稿者自身による著作物transferred from German Wikipedia, original file was located at de:Bild:Animation Sieb des Eratosthenes.gif, CC 表示-継承 3.0, https://commons.wikimedia.org/w/index.php?curid=327783による

これをC言語で書くのに、自然数の一覧を配列にするのが最も簡単です。

#include <stdio.h>
#define MAX 1000

void main() {
  int i, j;
  int n[MAX + 1];

  /* init */
  for (i = 0; i <= MAX; i++)
    n[i] = -1;

  /* check */
  for (i = 2; i * i <= MAX; i++)
    for (j = i * i; j < MAX; j += i)
      n[j] = 0;

  /* output */
  for (i = 2; i < MAX; i++)
    if (n[i])
      printf("%d\t", i);
  printf("\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	101	103	107	109	113	127	131	137	139	149	151	157	163	167	173	179	181	191	193	197	199	211	223	227	229	233	239	241	251	257	263	269	271	277	281	283	293	307	311	313	317	331	337	347	349	353	359	367	373	379	383	389	397	401	409	419	421	431	433	439	443	449	457	461	463	467	479	487	491	499	503	509	521	523	541	547	557	563	569	571	577	587	593	599	601	607	613	617	619	631	641	643	647	653	659	661	673	677	683	691	701	709	719	727	733	739	743	751	757	761	769	773	787	797	809	811	821	823	827	829	839	853	857	859	863	877	881	883	887	907	911	919	929	937	941	947	953	967	971	977	983	991	997	

配列を使うのが素直で、メモリを節約するために配列を char にしたり、ビットフィールドは使いにくいのですが、上手にビット演算を行って、素数かどうかを示すのに１ビットまで圧縮する方法もあるとは思います。いずれにせよ、求める数だけの領域が必要になり、このやり方で領域を分割するのは難しそうです。

そういう訳で、リストを使って篩を実装してみようと思い立ちました。今回は単方向リストで書いてみます。

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000

// list
typedef struct node {
  int val;
  struct node *next;
} Node;

void main() {
  int n = MAX;
  int i;

  // generate list
  Node *head = NULL;
  for (i = n; i >= 2; i--) {
    Node *node = malloc(sizeof(Node));
    node->val = i;
    node->next = head;
    head = node;
  }

  // check
  Node *current = head;
  while (current->val * current->val <= n) {
    // Remove nonPrime
    Node *prev = current;
    Node *node = current->next;
    while (node != NULL) {
      if (node->val % current->val == 0) {
        prev->next = node->next;
        free(node);
        node = prev->next;
      } else {
        prev = node;
        node = node->next;
      }
    }
    current = current->next;
  }

  // output
  current = head;
  while (current != NULL) {
    printf("%d\t", current->val);
    current = current->next;
  }
  printf("\n");

  // destroy remain
  current = head;
  while (current != NULL) {
    Node *next = current->next;
    free(current);
    current = next;
  }
}

コードをコンパクトにしたいので、処理の中にリスト操作も埋め込んでしまいました。最初に自然数の一覧をリストとして生成し、この中から倍数（余りが0）をみつけたら、リストから外していきます。これで調べる数の自乗が最も大きな数を超えたら、リストに残った数が素数です。

配列とやっていることはほとんど(ループの回し方だけ少し違う)同じですし、配列よりもリストのほうがメモリはたくさん使うのですが、計算が進むにつれリストは短くなっていくので、メモリも減っていきます。

この先のコードはまだ検討していないのですが、次に求める領域をリストに追加して、リストの最初から繰り返せば続きの計算ができるのでは、なんて思っています。もしかしたらもう一捻りが必要かもしれませんが。

---

python のイテレータも実装は確認していませんが、基本的にはこういう構造で、filterにかけている処理こそが篩の部分になっているような気はしています。

今回は特に課題という形にせず、自由演習ということで解答は用意しないと思いますが、リストを使ったコードを、前回までの教室で学んだ自身のリスト関数を使って書いてみてください。余力があれば、より大きな数字に対して素数を調べる方法なんて研究していただければ幸い。とても大きな数を相手にする場合は、途中からファイルに吐き出す必要も出てくるとは思うのですが、まだファイル操作やってないので、続きはその頃かな。

次回は、スタック、キューなどを取り上げる予定です。

#C言語 #プログラミング講座 #素数 #エラトステネスの篩 #リスト