エラトステネスのふるいは、素数を効率的に求めるアルゴリズムの一つです。このアルゴリズムをC言語で実装する方法について、初心者でもわかりやすいように解説します。
1. エラトステネスのふるいとは？
エラトステネスのふるいは、2以上の整数の中から素数を見つけるアルゴリズムです。最初に2を素数とし、次にその倍数（4, 6, 8, …）を素数ではないとマークします。次に、次の素数3の倍数をマークし、これを繰り返すことで、最終的に素数だけが残る仕組みです。
2. プログラムの構成
プログラムの流れを簡単に説明します。まず、配列aを使って各整数を素数かどうかを判定します。初期状態では、すべての値を0（素数候補）に設定します。次に、2からNまでの数を順に調べ、素数であれば、その倍数を全て素数ではないとマークします。
具体的には、`if(a[i] == 0)`で素数をチェックし、`for(k=2; i*k < N+1; k++)`でその倍数に1を代入します。これにより、素数でない数を排除していきます。
3. プログラムの解説
プログラムの各部分についてさらに詳しく見てみましょう。
for(i=0; i < N+1; i++) a[i] = 0;：配列aを初期化します。for(i=2; i < N+1; i++)：2からNまでの数を順に処理します。if(a[i] == 0)：iが素数の場合に、その倍数を排除します。for(k=2; i*k < N+1; k++)：iの倍数に1を代入し、素数ではないとマークします。
4. プログラムの出力
プログラムでは、素数を表示する部分もあります。20個の素数を1行に表示するように工夫されています。`if(l % 20 == 0)`で20個ごとに改行が入るようになっています。
例えば、出力結果は次のようになります。
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
5. まとめ
エラトステネスのふるいは、素数を求めるための非常に効率的なアルゴリズムです。このプログラムでは、C言語を使って素数を求める方法を実装しました。初心者でも理解しやすいようにプログラムの各部分を解説しました。ぜひ、この方法を活用して、素数を効率的に求めてみましょう。
コメント