アルゴリズムトップ
0. はじめに
1. アルゴリズム
1. アルゴリズムとは
2. 当ページの範囲
3. 良いアルゴリズム
4. フローチャートの書き方(記号)
5. フローチャートの書き方(構造)
6. 順次構造
7. 分岐構造
8. 反復構造
2. 順次構造
1. 代入
2. 計算
3. 入力
4. 出力
5. 練習問題1
6. 練習問題2
3. 分岐構造
1. 条件分岐
2. 単一分岐
3. 練習問題1
4. 多重分岐
5. 複合条件
6. ケース(多方向分岐)
7. 練習問題2
8. 練習問題3
4. 反復構造
1. 反復構造の種類
2. 前判定型
3. 後判定型
4. 練習問題1
5. 練習問題2
6. 練習問題3
7. 多重反復処理(ネスト)
8. 練習問題4
9. 練習問題5
5. 配列
1. 配列とは
2. 練習問題
3. 2次配列
4. 練習問題
5. 素数を求める,その1
6. 素数を求める,その2
6. 検索・ソート
1. サブルーチン
2. シーケンシャルサーチ
3. バイナリサーチ
4. 練習問題
5. ルックアップテーブル
6. ソートとは
7. 選択法
8. 交換法
9. バブルソート
10. 挿入法
11. クイックソート
12. 処理速度の比較
7. 文字列
1. 文字と文字列
2. 文字列処理
3. 文字列のコピー
4. 練習問題
5. 文字列の比較
6. 文字列の連結
7. 文字列の検索
| |
前ページへ : 解答へ : 次の章へ
5-6.素数を求める,その2(エラトステネスのふるい)
- 問題:
- 100以下の素数を求めよ。 たいとるそのまま・・・(^_^;)
素数とは、1より大きく、1とその数以外に約数を持たない自然数である。すなわち
一番小さい素数は2である。ここでは「エラトステネスのふるい」という有名な
アルゴリズムによって素数を求める。
エラトステネスのふるいとは、
- 100個の配列を用意する
- すべての配列の中身に1を代入する
- 2の倍数番目の中に0を代入する
- 3の倍数番目の中に0を代入する
- 4番目はすでに0なので、次に進む
- 5の倍数番目の中に0を代入する
- 6番目はすでに0なので、次に進む
- 7の倍数番目の中に0を代入する
- :
- :
- 100の平方根まで繰り返す
|
例えば99を見たとき、100の平方根=10であるから、11でも割り切れるが、
11以下の数ですでにチェックされている。したがって100の平方根=10以上は
チェックする必要がない。
これをもう少し視覚的に見てみよう。
添字 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 |
中身 | / | / | 1 | 1 | 1 | 1 | 1 |
1 | 1 | 1 | 1 | 1 | 1 |
1 | 1 | 1 | 1 |
↓
2の倍数を消していきます。
↓
添字 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
中身 |
/ |
/ |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
↓
3の倍数を消していきます。
↓
添字 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
中身 |
/ |
/ |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
↓
4の倍数は2の倍数ですでに消えている。
そこで5の倍数を消していきます。
↓
添字 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
中身 |
/ |
/ |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
↓
6の倍数は2の倍数ですでに消えている。
そこで7の倍数を消していきます。
↓
↓
8の倍数は2の倍数ですでに消えている。
9の倍数は3の倍数ですでに消えている。
10の倍数は2の倍数ですでに消えている。
100の平方根=10を越えたのでおしまい。
↓
配列の中身が1である添え字が素数である。
前ページへ : 解答へ : 次の章へ
|