System Note
$ cat /proc/ai-disclosure
本記事の構成および論理分析にはAI（人工知能）を使用しています。情報の正確性は、システム管理者（UNIXユーザー）による手動検証済みです。
【素数で遊ぼう】C言語で割り算からエラトステネスのふるいまで｜定番問題をコードパズルにしてみた | UNIX Cafe
プログラミングを学んでいると、何度も出てくる数に 素数 があります。
素数は、2、3、5、7、11 のように、1と自分自身でしか割り切れない整数です。言葉だけ見ると数学っぽいですが、コードにすると「割り切れるかどうかを試す」小さなパズルになります。
今回は、この素数を C言語 で遊びながら見ていきます。関数、for文、余り演算、配列を使いながら、まずは全部の割り算を試すところから始めて、最後はエラトステネスのふるいまで進みます。
最後に、同じ考え方を Python で書くとどう表せるかも補足します。この記事ではC言語を主役にして、Pythonは見比べるための別表現として扱います。
目次
素数ってなに？
素数は、約数が 1 と自分自身だけの整数です。
| 数 | 素数？ | 理由 |
|---|---|---|
| 1 | いいえ | 素数ではない特別な数 |
| 2 | はい | 1と2でしか割り切れない |
| 3 | はい | 1と3でしか割り切れない |
| 4 | いいえ | 2で割り切れる |
| 5 | はい | 1と5でしか割り切れない |
| 9 | いいえ | 3で割り切れる |
ここで大事なのは、1は素数ではない という点です。
「1と自分自身で割り切れるなら、1も素数では？」と思いたくなりますが、現在の数学では 1 は素数に入れません。素数を使った分解のルールをきれいに保つためです。
素数判定の基本ルール
今回のルールを、コードで考えやすい形にするとこうなります。
1以下は素数ではない2以上の数を調べる- 途中で割り切れる数が見つかったら素数ではない
- 最後まで割り切れなければ素数
C言語では、割り切れるかどうかを % で調べられます。
n % i == 0これは「n を i で割った余りが 0」という意味です。つまり、きれいに割り切れます。
その1：まずは全部割ってみる
まずは一番わかりやすい方法から始めます。
n が素数かどうかを調べるには、2 から n - 1 までで割ってみます。途中で割り切れたら、その数は素数ではありません。
prime_basic.c という名前で、次のコードを作ってみます。
#include <stdio.h>
int is_prime(int n) {
if (n <= 1) {
return 0;
}
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}
int main(void) {
int numbers[] = {1, 2, 3, 4, 5, 9, 11, 15, 17, 21};
int size = sizeof(numbers) / sizeof(numbers[0]);
for (int i = 0; i < size; i++) {
if (is_prime(numbers[i])) {
printf("%d: prime\n", numbers[i]);
} else {
printf("%d: not prime\n", numbers[i]);
}
}
return 0;
}このコードでは、素数なら 1、素数でなければ 0 を返す関数を作っています。
試す数字を変えてみる
int numbers[] = {1, 2, 3, 4, 5, 9, 11, 15, 17, 21}; の部分は、素数と素数でない数が混ざるように選んだサンプルです。
6、7、8、10 などを飛ばしていることに、特別な数学的な理由はありません。出力が長くなりすぎないように、いくつか抜き出しています。
自分で試したい場合は、この配列の中身を自由に変えて大丈夫です。
int numbers[] = {6, 7, 8, 10, 13, 19, 25, 31};数字を増やしたり、順番を変えたりしても動きます。配列の個数は自動的に数えているので、size を手で直す必要はありません。
sizeof で配列の個数を数える
int size = sizeof(numbers) / sizeof(numbers[0]); は、配列 numbers に入っている要素の個数を数えています。
C言語では、配列に「何個入っているか」を直接教えてくれる機能がありません。そこで、配列全体のサイズを、配列の1個分のサイズで割ります。
sizeof(numbers) // 配列全体のサイズ
sizeof(numbers[0]) // 配列の1個分のサイズつまり、考え方はこうです。
配列全体のサイズ / 1個分のサイズ = 要素の個数たとえば int が4バイトの環境で、numbers に10個の数字が入っているなら、配列全体は 40 バイト、1個分は 4 バイトです。
40 / 4 = 10これで size には 10 が入ります。そのため、for (int i = 0; i < size; i++) と書けば、配列の最後まで順番に調べられます。
return 0 と return 1 の使い方
C言語には、Python の True や False のような書き方もありますが、ここではシンプルに 1 を「はい」、0 を「いいえ」として使っています。
return 1;は「素数です」return 0;は「素数ではありません」
このくらいの小さな関数なら、条件判定の練習にもなります。
コンパイルと実行
macOS のターミナルなら、次のようにコンパイルできます。
gcc -std=c99 prime_basic.c -o prime_basic実行します。
./prime_basic実行結果はこうなります。
1: not prime
2: prime
3: prime
4: not prime
5: prime
9: not prime
11: prime
15: not prime
17: prime
21: not primeその2：平方根まで調べれば十分
さきほどのコードはわかりやすいのですが、少し無駄があります。
たとえば 100 が素数かどうかを調べるとき、2 で割り切れることがすぐにわかります。もし割り切れる数があるなら、片方の約数は必ず平方根以下に出てきます。
そこで、ループの条件を i < n から i * i <= n に変えます。
for (int i = 2; i * i <= n; i++)sqrt 関数を使ってもよいのですが、今回は i * i <= n と書くことで、数学関数を使わずに済ませます。
36の約数で折り返しを見てみる
なぜ平方根まででよいのかは、36 の約数ペアを見るとわかりやすいです。
| 約数のペア | 見方 |
|---|---|
| 2 * 18 = 36 | 小さい側は2 |
| 3 * 12 = 36 | 小さい側は3 |
| 4 * 9 = 36 | 小さい側は4 |
| 6 * 6 = 36 | ここが折り返し地点 |
| 9 * 4 = 36 | 4 * 9 の逆向き |
| 12 * 3 = 36 | 3 * 12 の逆向き |
| 18 * 2 = 36 | 2 * 18 の逆向き |
6 * 6 = 36 の 6 が、36 の平方根です。ここを超えると、9、12、18 のような大きい約数は、すでに出てきた 4、3、2 とペアになっています。
つまり、平方根を超えたところに新しい小さい約数は出てきません。だから、i * i <= n まで調べれば十分です。
たとえば 17 を調べる場合、全部試す方法なら 2 から 16 まで確認します。一方、i * i <= 17 なら、調べるのは 2、3、4 までです。5 * 5 = 25 は 17 を超えるので、そこでループを抜けます。
今度は、1 から 100 までの素数を表示してみましょう。prime_list.c という名前で作ります。
#include <stdio.h>
int is_prime(int n) {
if (n <= 1) {
return 0;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}
int main(void) {
for (int n = 1; n <= 100; n++) {
if (is_prime(n)) {
printf("%d ", n);
}
}
printf("\n");
return 0;
}コンパイルします。
gcc -std=c99 prime_list.c -o prime_list実行します。
./prime_list実行結果はこうなります。
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 ここでは、素数を空白区切りで横に並べています。
その3：双子素数を探してみる
素数を判定できるようになると、少し遊び方を変えられます。
たとえば、差が 2 の素数のペアは 双子素数 と呼ばれます。
3と55と711と13
前に見つけた素数を覚えておいて、次の素数との差が 2 なら表示します。twin_prime.c という名前で作ります。
#include <stdio.h>
int is_prime(int n) {
if (n <= 1) {
return 0;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}
int main(void) {
int previous = 2;
for (int n = 3; n <= 100; n++) {
if (is_prime(n)) {
if (n - previous == 2) {
printf("(%d, %d)\n", previous, n);
}
previous = n;
}
}
return 0;
}main関数の読み方
この main 関数では、previous に「前に見つけた素数」を入れておきます。
int previous = 2;最初の素数は 2 なので、まず previous に 2 を入れています。そのあと、3 から 100 まで順番に調べます。
for (int n = 3; n <= 100; n++)is_prime(n) が本当だったときだけ、つまり n が素数だったときだけ、前の素数との差を見ます。
if (n - previous == 2)差が 2 なら、previous と n は双子素数です。そのため、printf でペアとして表示します。
最後に、今見つけた素数 n を previous に入れ直します。
previous = n;これで、次の素数が見つかったときに「ひとつ前の素数」と比べられます。双子素数探しでは、この previous がメモの役割をしています。
コンパイルします。
gcc -std=c99 twin_prime.c -o twin_prime実行します。
./twin_prime実行結果はこうなります。
(3, 5)
(5, 7)
(11, 13)
(17, 19)
(29, 31)
(41, 43)
(59, 61)
(71, 73)ここでは 100 までしか調べていません。1000 や 10000 に変えると、見つかるペアが増えます。
その4：エラトステネスのふるい
最後に、少し有名な方法を見てみます。エラトステネスのふるい です。
これは、最初に「全部素数かもしれない」と考えておき、あとから倍数を消していく方法です。
2の倍数を消す3の倍数を消す5の倍数を消す- 消されずに残った数が素数
同じような割り算を何度もする代わりに、表に印をつけていくイメージです。
prime_sieve.c という名前で作ります。
#include <stdio.h>
#define LIMIT 100
int main(void) {
int is_prime[LIMIT + 1];
for (int i = 0; i <= LIMIT; i++) {
is_prime[i] = 1;
}
is_prime[0] = 0;
is_prime[1] = 0;
for (int p = 2; p * p <= LIMIT; p++) {
if (is_prime[p]) {
for (int multiple = p * p; multiple <= LIMIT; multiple += p) {
is_prime[multiple] = 0;
}
}
}
for (int n = 1; n <= LIMIT; n++) {
if (is_prime[n]) {
printf("%d ", n);
}
}
printf("\n");
return 0;
}main関数の読み方
この main 関数では、is_prime という配列を使って、数ごとに「素数かもしれない」という印を持たせています。
int is_prime[LIMIT + 1];LIMIT は 100 なので、is_prime[0] から is_prime[100] まで使える配列を作っています。LIMIT + 1 にしているのは、添字 100 まで使いたいからです。
最初は、すべての数を「素数かもしれない」と考えて、配列の中身を 1 にします。
for (int i = 0; i <= LIMIT; i++) {
is_prime[i] = 1;
}ただし、0 と 1 は素数ではありません。ここは先に 0 にしておきます。
is_prime[0] = 0;
is_prime[1] = 0;次のループが、エラトステネスのふるいの中心です。
for (int p = 2; p * p <= LIMIT; p++)p がまだ素数候補として残っているなら、その倍数を消していきます。消す、というのは is_prime[multiple] = 0; にすることです。
for (int multiple = p * p; multiple <= LIMIT; multiple += p) {
is_prime[multiple] = 0;
}multiple += p は、p の倍数を順番に進むための書き方です。たとえば p が 3 なら、9、12、15、18 のように進みます。
最後に、まだ 1 のまま残っている数を表示します。これが、ふるいにかけたあとに残った素数です。
コンパイルします。
gcc -std=c99 prime_sieve.c -o prime_sieve実行します。
./prime_sieve実行結果は、さきほどの prime_list.c と同じです。
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 4つの方法を比べてみる
| 方法 | 特徴 | 向いている場面 |
|---|---|---|
| 全部割る | 一番わかりやすい | 素数判定の最初の練習 |
i * i <= n まで調べる | 無駄な割り算を減らせる | 1つの数を調べるとき |
| 双子素数を探す | 素数判定を使って遊べる | 条件を変えて試す練習 |
| エラトステネスのふるい | 倍数をまとめて消す | たくさんの素数を探すとき |
最初から一番速い方法だけを覚えるより、まずは全部試すコードを書いてから、少しずつ無駄を減らしていくと理解しやすいです。
C言語で試すときの注意点
for (int i = ...)の書き方を使うので、gcc -std=c99を付けてコンパイルすると安心1は素数ではないので、最初にn <= 1をチェックするi * i <= nは便利だが、とても大きな数では整数の範囲にも注意するLIMITを大きくしすぎると配列も大きくなるので、まずは100や1000で試す
改造して遊ぶポイント
素数のコードは、値を少し変えるだけで遊び方が増えます。
100までではなく500まで調べる- 双子素数ではなく、差が
4の素数ペアを探す - 素数が何個あったかを数える
- 一番大きな素数だけを表示する
「条件を1つ変えると、結果がどう変わるか」を見るのが、この手のコードパズルの楽しいところです。
Pythonではどう書ける？
ここまでC言語で見てきた素数判定は、Pythonでも同じ考え方で書けます。Pythonでは True と False をそのまま返せるので、戻り値の意味が少し読みやすくなります。
まず、平方根まで調べる素数判定は次のように書けます。
def is_prime(n):
if n <= 1:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
for n in range(1, 21):
if is_prime(n):
print(n, end=" ")エラトステネスのふるいも、リストを使うと短く書けます。
def sieve(limit):
is_prime = [True] * (limit + 1)
is_prime[0] = False
is_prime[1] = False
p = 2
while p * p <= limit:
if is_prime[p]:
for multiple in range(p * p, limit + 1, p):
is_prime[multiple] = False
p += 1
return is_prime
limit = 100
prime_flags = sieve(limit)
for n in range(2, limit + 1):
if prime_flags[n]:
print(n, end=" ")C言語版とPython版の違い
同じ素数判定のコードでも、C言語では配列や整数の扱いを意識しながら書きます。一方、Pythonではリストや真偽値を使って、同じ流れを少し短く表せます。
| 観点 | C言語 | Python |
|---|---|---|
| 真偽値 | 1 と 0 を返して判定することが多い | True と False を返せる |
| 配列 | int is_prime[LIMIT + 1] のようにサイズを意識する | [True] * (limit + 1) でリストを作れる |
| 繰り返し | for文で初期値、条件、増分を書く | range() や while で短く書ける |
| 学びやすい点 | 配列や整数の扱いが見えやすい | 素数判定の流れを短いコードで確認しやすい |
このシリーズでは、まずC言語で仕組みを丁寧に扱い、必要に応じてPythonでどう書けるかを補足していきます。Python版を別の記事として分けるよりも、同じ記事の中で比較したほうが、コードの違いが見えやすくなるからです。
まとめ：素数は割り算で遊べるコードパズル
今回は、C言語で素数を調べるコードを書きました。
- 素数は、1と自分自身でしか割り切れない数
1は素数ではない%を使うと、割り切れるかどうかを調べられるi * i <= nまで調べれば、無駄な割り算を減らせる- たくさんの素数を探すなら、エラトステネスのふるいも使える
- Pythonでは同じ考え方を短く書けるので、処理の流れを確認しやすい
FizzBuzz で使った % は、素数判定でも主役になります。倍数を見つける、割り切れるか調べる、条件を変えて結果を見る。ここまでできると、ただの割り算が立派なプログラミングの遊び道具になります。
C言語の次にUnityやUnreal Engineを学ぶ選択肢
用途ごとに選ぶ C言語のおすすめ本
