アウトライン
12-1 繰り返し計算
12-2 パソコン演習
12-3 課題
2
•再帰を使った，繰り返し計算
•数学の「再帰的定義」と，Scheme
プログラムの関係
•繰り返し回数
•関数は「何回繰り返して」実行され
るか
本日の内容
3
12-1 繰り返し計算
4
•階乗
•「n -1 の階乗」に n を足すことを繰り返す
•ユークリッドの互助法
•m とn の最大公約数を求めるために，「割った余
りを求めること」を，余りが０になるまで繰り返
す
繰り返しの例
5
12-2 パソコン演習
6
•資料を見ながら，「例題」を行ってみる
•各自，「課題」に挑戦する
•自分のペースで先に進んで構いません
パソコン演習の進め方
7
•DrScheme の起動
プログラム → PLT Scheme → DrScheme
•今日の演習では「Intermediate Student」
に設定
Language
→ Choose Language
→ Intermediate Student
→ Execute ボタン
DrScheme の使用
8
•階乗を計算する関数 !を作り，実行す
る
•次の方針でプログラムを作成する
n > 0 のとき，n! = n ×(n-1)!
例） 6! = 6×5!
例題１． 階乗
9
•n = 0 のとき
1!n
•n > 0 のとき
)!1(! nnn
階乗
10
1. 次を「定義用ウインドウ」で，実行しなさい
•入力した後に，Execute ボタンを押す
;;! : number -> number
;;to compute n*(n-1)*...*2*1
(define (!n)
(cond
[(= n0) 1]
[else (* n(!(- n1)))]))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆次は，例題２に進んでください
(! 3)
(! 4)
「例題１．階乗」の手順
11
「例題１．階乗」の実行結果
12
まず，Scheme のプログラムを
コンピュータに読み込ませている
13
これは，
(!4)
と書いて，nの値を
4 に設定しての実行
実行結果である「24」が
表示される
14
!
24
入力 出力
4
入力は数値 出力は数値
入力と出力
15
;; ! : number -> number
;; to compute n*(n-1)*...*2*1
;; Example: (! 4) = 24
(define (!n)
(cond
[(= n0) 1]
[else (* n(!(- n1)))]))
n! は(n-1)! を計算して，n を掛ける
0! = 1 である
! 関数
16
1. n = 0 ならば：→終了条件
1 →自明な解
2. そうで無ければ：
–「n -1 の階乗」に n をかける
⇒結局，1 から n までのかけ算を繰り返
す
階乗
17
;; ! : number -> number
;; to compute n*(n-1)*...*2*1
;; (! 4) = 24
(define (!n)
(cond
[(= n0) 1]
[else (* n(!(- n1)))]))
自明な解
終了条件
階乗
18
(= n0)
(* n(!(- n1)))
Yes
No
1 が自明の解
終了条件
19
•! の内部に ! が登場
•! の実行が繰り返される
例： (! 5) = (* 5 (! 4))
(! 4) = (* 4 (! 3))
(define (!n)
(cond
[(= n0) 1]
[else (* n(!(- n1)))]))
階乗
20
•関数 !（例題１）について，実行結果に至る過程
を見る
•(!3) から 6 に至る過程を見る
•DrScheme のstepper を使用する
21
例題２．ステップ実行
(define (!n)
(cond
[(= n0) 1]
[else (* n(!(- n1)))]))
(!3)
=...
= (* 3 (!2))
=...
= (* 3 (* 2 (!1)))
=...
= (* 3 (* 2 (* 1 (!0))))
=...
= (* 3 (* 2 (* 1 1)))
= (* 3 (* 2 1))
= (* 3 2)
= 6
1. 次を「定義用ウインドウ」で，実行しなさい
•Intermediate Student で実行すること
•入力した後に，Execute ボタンを押す
;;! : number -> number
;;to compute n*(n-1)*...*2*1
(define (!n)
(cond
[(= n0) 1]
[else (* n(!(- n1)))]))
(! 3)
2. DrScheme を使って，ステップ実行の様子を
確認しなさい （Step ボタン，Next ボタンを使用）
•理解しながら進むこと
☆次は，例題３に進んでください
例題１と同じ
「例題２．ステップ実行」の手順
22
! の「n」は「3」で置き換わる
23
「(= 3 0)」は「false」で
置き換わる
24
「(cond [false 式Ｘ] [else 式Ｙ])」は
「式Ｙ」で置き換わる
25
「(- 3 1)」は，「2」で
置き換わる
26
! の「n」は「2」で置き換わる
27
「(= 2 0)」は「false」で
置き換わる
28
「(cond [false 式Ｘ] [else 式Ｙ])」は
「式Ｙ」で置き換わる
29
「(- 2 1)」は，「1」で
置き換わる
30
! の「n」は「1」で置き換わる
31
「(= 1 0)」は「false」で
置き換わる 32
「(cond [false 式Ｘ] [else 式Ｙ])」は
「式Ｙ」で置き換わる 33
「(- 1 1)」は，「0」で
置き換わる
34
! の「n」は「1」で置き換わる 35
「(= 0 0)」は「true」で
置き換わる 36
「(cond [true 式Ｘ] [else 式Ｙ])」は
「式Ｘ」で置き換わる
37
「(* 1 1)」は，「1」で
置き換わる
38
「(* 2 1)」は，「2」で
置き換わる
39
「(* 3 2)」は，「6」で
置き換わる
40
(!3)
=...
= (* 3 (!2))
= ...
= (* 3 (* 2 (!1)))
=...
= (* 3 (* 2 (* 1 (!0))))
=...
= (* 3 (* 2 (* 1 1)))
= (* 3 (* 2 1))
= (* 3 2)
= 6
最初の式
実行結果
コンピュータ内部での計算
(! 3) から 6 が得られる過程の概略
41
(!3)
=...
= (* 3 (!2))
= ...
= (* 3 (* 2 (!1)))
=...
= (* 3 (* 2 (* 1 (!0))))
=...
= (* 3 (* 2 (* 1 1)))
= (* 3 (* 2 1))
= (* 3 2)
= 6
(!3)
= (cond
[(= 3 0) 1]
[else (* 3 (!(- 3 1)))])
= (cond
[false 1]
[else (* 3 (!(- 3 1)))])
= (* 3 (!(- 3 1)))
= (* 3 (!2))
この部分は
(! 3) から 6 が得られる過程の概略
42
(!3)
=...
= (* 3 (!2))
= ...
= (* 3 (* 2 (!1)))
=...
= (* 3 (* 2 (* 1 (!0))))
=...
= (* 3 (* 2 (* 1 1)))
= (* 3 (* 2 1))
= (* 3 2)
= 6
(!3)
= (cond
[(= 3 0) 1]
[else (* 3 (!(- 3 1)))])
= (cond
[false 1]
[else (* 3 (!(- 3 1)))])
= (* 3 (!(- 3 1)))
= (* 3 (!2))
この部分は
これは，
(define (!n)
(cond
[(= n0) 1]
[else (* n(!(- n1)))]))
のnを3 で置き換えたもの
(! 3) から 6 が得られる過程の概略
43
(!3)
=...
= (* 3 (!2))
=...
= (* 3 (* 2 (!1)))
=...
= (* 3 (* 2 (* 1 (!0))))
=...
= (* 3 (* 2 (* 1 1)))
= (* 3 (* 2 1))
= (* 3 2)
= 6
「(! 3)」が膨張して
「(* 3 (* 2 (* 1 (! 0))))」
になる
基本的な計算式への展開
「(* 3 (* 2 (* 1 (! 0))))」
が収縮して６になる
演算の実行
(! 3) から 6 に至る過程
44
例(! 3) ⇒(* 3 (* 2 (* 1 (! 0))))
•基本的な計算式へ展開
再帰の呼び出し回数（＝ステップ
数ともいう）に比例して成長する
⇒「線形再帰」の名前の由来
線形再帰的プロセス
45
(!3)
=...
= (* 3 (!2))
= ...
= (* 3 (* 2 (!1)))
=...
= (* 3 (* 2 (* 1 (!0))))
=...
= (* 3 (* 2 (* 1 1)))
= (* 3 (* 2 1))
= (* 3 2)
= 6
n=3 のとき，
4回繰り返して実行される
①
②
③
④
!が繰り返される回数
46
(!4)
=...
= (* 4 (!3))
= ...
= (* 4 (* 3 (!2)))
=...
= (* 4 (* 3 (* 2 (!1))))
=...
= (* 4 (* 3 (* 2 (* 1 (!0)))))
=...
= (* 4 (* 3 (* 2 (* 1 1))))
= (* 4 (* 3 (* 2 1)))
= (* 4 (* 3 2))
= (* 4 6)
=24
n=4 のとき，
5回繰り返して実行される
①
②
③
④
⑤
! が繰り返される回数
47
•階乗を計算する関数 !を作り，実行す
る
•次の方針でプログラムを作成する
n > 0 のとき，1 から開始して，1 ×2
×・・・×n を計算する
例） (! 6) = 1 ×2 ×3 ×4 ×5 ×6
例題３． 反復的プロセスでの階乗
48
•n! の計算
1. まず，1 に2 を掛ける
2. 次に，3 を掛ける
3. ・・・
4. n に達するまで続ける
反復的プロセスでの階乗
49
1. 次を「定義用ウインドウ」で，実行しなさい
•入力した後に，Execute ボタンを押す
;; ! : number -> number
;; to compute n*(n-1)*...*2*1
;; (! 4) = 24
(define (!n)
(factorial 1 1 n))
(define (factorial product counter max)
(cond
[(> counter max) product]
[else (factorial (* counter product)
(+ counter 1)
max)]))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆次は，例題４に進んでください
(! 4)
(! 10)
(! 20)
「例題３．反復的プロセスでの階乗」の手順
50
まず，Scheme のプログラムを
コンピュータに読み込ませている
51
これは，
(!4)
と書いて，nの値を
4 に設定しての実行
実行結果である「24」が
表示される
52
!
24
入力 出力
4
入力は数値 出力は数値
入力と出力
53
54
! 関数
;; ! : number -> number
;; to compute n*(n-1)*...*2*1
;; (! 4) = 24
(define (!n)
(factorial 1 1 n))
(define (factorial product counter n)
(cond
[(> counter n) product]
[else (factorial (* counter product)
(+ counter 1)
n)]))
product ← counter・product
counter ← counter + 1
counter: 1 から n まで数えるカウンタ
product: 部分積（計算の途中結果）
とする．
product ← counter・product
counter ← counter + 1
を繰り返す．counter がn に達すると
n!が求まる
反復的プロセスでの階乗
55
1. counter > n ならば：→終了条件
product →自明な解
2. そうで無ければ：
次を実行する
product ← counter・product
counter ← counter + 1
反復的プロセスでの階乗
56
57
反復的プロセスでの階乗
;; ! : number -> number
;; to compute n*(n-1)*...*2*1
;; (! 4) = 24
(define (!n)
(factorial 1 1 n))
(define (factorial product counter n)
(cond
[(> counter n) product]
[else (factorial (* counter product)
(+ counter 1)
n)]))
終了条件
自明な解
(> counter n)
(factorial (* counter product)
(+ counter 1)
n)
Yes
No
product が自明の解
終了条件
58
•factorial の内部に factorial が登場
•factorial の実行が繰り返される
例： (factorial 6 4 10) = (factorial 24 5 10)
(factorial 24 5 10) = (factorial 120 6 10)
59
例題４．ステップ実行
(define (factorial product counter n)
(cond
[(> counter n) product]
[else (factorial (* counter product)
(+ counter 1)
n)]))
例題４．ステップ実行
•関数 !（例題３）について，実行結果に至る過程
を見る
•(!4) から 24 に至る過程を見る
•DrScheme のstepper を使用する
60
(define (factorial product counter n)
(cond
[(> counter n) product]
[else (factorial (* counter product)
(+ counter 1)
n)]))
(!4)
= (factorial 1 1 4)
=...
= (factorial 1 2 4)
=...
= (factorial 2 3 4)
=...
= (factorial 6 4 4)
=...
= (factorial 24 5 4)
=...
=24
1. 次を「定義用ウインドウ」で，実行しなさい
•Intermediate Student で実行すること
•入力した後に，Execute ボタンを押す
(define (!n)
(factorial 1 1 n))
(define (factorial product counter max)
(cond
[(> counter max) product]
[else (factorial (* counter product)
(+ counter 1)
max)]))
(! 4)
2. DrScheme を使って，ステップ実行の様子を
確認しなさい （Step ボタン，Next ボタンを使用）
•理解しながら進むこと
☆次は，例題５に進んでください
例題３と同じ
「例題４．ステップ実行」の手順
61
(!4)
= (factorial 1 1 4)
=...
= (factorial 1 2 4)
=...
= (factorial 2 3 4)
=...
= (factorial 6 4 4)
=...
= (factorial 24 5 4)
=...
=24
最初の式
実行結果
コンピュータ内部での計算
(! 4) から 24 が得られる過程の概略
62
(!4)
= (factorial 1 1 4)
=...
= (factorial 1 2 4)
=...
= (factorial 2 3 4)
=...
= (factorial 6 4 4)
=...
= (factorial 24 5 4)
=...
=24
product, counter の
値が変化する
・counter
→繰り返し回数
・product
→部分積
product counter max
(! 4) から 24 が得られる過程の概略
63
例(! 3) =(factorial 1 1 3)
= (factorial 1 2 3)
= (factorial 2 3 3)
= (factorial 6 4 3)
•線形再帰的プロセスのような伸び縮みは無い
•関数を再帰的に呼び出す各ステップで計算が実
行される
伸び縮み無し
各ステップで，
product とcounter
に関する計算が
実行される
反復的プロセスの特徴
64
(!4)
= (factorial 1 1 4)
=...
= (factorial 1 2 4)
=...
= (factorial 2 3 4)
=...
= (factorial 6 4 4)
=...
= (factorial 24 5 4)
=...
=24
(factorial 1 1 4)
= (cond
[(> 1 4) 1]
[else (factorial (* 1 1)
(+ 1 1)
4)])
= (cond
[false 1]
[else (factorial (* 1 1)
(+ 1 1)
4)])
= (factorial (* 1 1) (+ 1 1) 4)
= (factorial 1 (+ 1 1) 4)
= (factorial 1 2 4)
この部分は
(factorial 1 1 4) から (factorial 1 2 4) が得られる過程
65
(!4)
= (factorial 1 1 4)
=...
= (factorial 1 2 4)
=...
= (factorial 2 3 4)
=...
= (factorial 6 4 4)
=...
= (factorial 24 5 4)
=...
=24
(factorial 1 1 4)
= (cond
[(> 1 4) 1]
[else (factorial (* 1 1)
(+ 1 1)
4)])
= (cond
[false 1]
[else (factorial (* 1 1)
(+ 1 1)
4)])
= (factorial (* 1 1) (+ 1 1) 4)
= (factorial 1 (+ 1 1) 4)
= (factorial 1 2 4)
この部分は
これは，
(define (factorial product counter n)
(cond
[(> counter n) product]
[else (factorial (* counter product)
(+ counter 1)
n)]))
のcounter を1 で，product を1 で，nを4 で置き換えたもの
(factorial 1 1 4) から (factorial 1 2 4) が得られる過程
66
(!4)
=...
= (* 4 (!3))
= ...
= (* 4 (* 3 (!2)))
=...
= (* 4 (* 3 (* 2 (!1))))
=...
= (* 4 (* 3 (* 2 (* 1 (!0)))))
=...
= (* 4 (* 3 (* 2 (* 1 1))))
= (* 4 (* 3 (* 2 1)))
= (* 4 (* 3 2))
= (* 4 6)
= 6
(!4)
= (cond
[(= 4 0) 1]
[else (* 4 (!(- 4 1)))])
= (cond
[false 1]
[else (* 4 (!(- 4 1)))])
= (* 4 (!(- 4 1)))
= (* 4 (!3))
この部分は
これは，
(define (!n)
(cond
[(= n0) 1]
[else (* n(!(- n1)))]))
のnを4 で置き換えたもの
(! 4) から (* 4 (! 3)) が得られる過程
67
(!4)
= (factorial 1 1 4)
=...
= (factorial 1 2 4)
=...
= (factorial 2 3 4)
=...
= (factorial 6 4 4)
=...
= (factorial 24 5 4)
=...
=24
n=4 のとき，
5回繰り返して実行される
①
②
③
④
⑤
factorial が繰り返される回数
68
•次のプログラムでは，square は何回実行されるか
(define (square x)
(* x x))
(define (total-square x)
(cond
[(empty? x) 0]
[else (+ (square (first x)) (total-square (rest x)))]))
例題５．繰り返し回数
69
実行結果の例
(total-square (list 10 20 30))
1400
•square は，リストの要素数だけ実行される
繰り返し回数
70
•ユークリッドの互助法を使って，２つ
の整数 m, n から，最大公約数を求める
プログラム my-gcd を作り，実行する
例） 180, 32 のとき： 4
•ユークリッドの互助法を用いる
例題６．最大公約数の計算
71
•２つの整数 m, n の最大公約数:
（m, n は正または０）
•n = 0 なら
最大公約数は m
• n ≠ 0 なら
最大公約数は， 「m をn で割った余り」 と n の最大公
約数に等しい
ユークリッドの互助法
72
1. 次を「定義用ウインドウ」で，実行しなさい
•入力した後に，Execute ボタンを押す
;; my-gcd: number number -> number
;; to find the greatest common divisor of n and m
;; Example: (my-gcd 180 32) = 4
(define (my-gcd m n)
(cond
[(= n0) m]
[else (my-gcd n
(remainder m n))]))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆次は，例題７に進んでください
(mygcd 180 32)
「例題６．最大公約数の計算」の手順
73
まず，Scheme のプログラムを
コンピュータに読み込ませている
74
これは，
(my-gcd 180 32)
と書いて，mの値を 180 に，
nの値を 32 に設定しての実行
実行結果である「4」が
表示される
75
my-gcd
4
入力 出力
180 32
入力は，２つの数値 出力は数値
入力と出力
76
;; my-gcd: number number -> number
;; to find the greatest common divisor of n and m
;; Example: (my-gcd 180 32) = 4
(define (my-gcd m n)
(cond
[(= n0) m]
[else (my-gcd n
(remainder m n))]))
my-gcd 関数
77
1. n = 0 ならば：→終了条件
m →自明な解
2. そうで無ければ：
(1) n
(2) m をn で割った余り
の２数の最大公約数を求める．
以上のことを，n が０に達するまで繰り返す
最大公約数の計算
78
;; my-gcd: number number -> number
;; to find the greatest common divisor of n and m
;; Example: (my-gcd 180 32) = 4
(define (my-gcd m n)
(cond
[(= n0) m]
[else (my-gcd n
(remainder m n))]))
自明な解
終了
条件
79
(= n0)
(my-gcd n
(remainder m n)
Yes
No
m が自明の解
終了条件
80
•my-gcd の内部に my-gcd が登場
•my-gcd の実行が繰り返される
例： (my-gcd 180 32)
= (my-gcd 32 20)
(define (my-gcd m n)
(cond
[(= n0) m]
[else (my-gcd n
(remainder m n))]))
最大公約数の計算
81
•関数 my-gcd （例題６）について，実行結果に至
る過程を見る
•(my-gcd 180 32) から 4 に至る過程を見る
•DrScheme のstepper を使用する
82
例題７．ステップ実行
(define (my-gcd m n)
(cond
[(= n0) m]
[else (my-gcd n
(remainder m n))]))
(my-gcd 180 32)
= …
= (my-gcd 32 20)
= …
= (my-gcd 20 12)
= …
= (my-gcd 12 8)
= …
= (my-gcd 8 4)
= …
= (my-gcd 4 0)
= …
= 4
1. 次を「定義用ウインドウ」で，実行しなさい
•Intermediate Student で実行すること
•入力した後に，Execute ボタンを押す
;; my-gcd: number number -> number
;; to find the greatest common divisor of n and m
;; Example: (my-gcd 180 32) = 4
(define (my-gcd m n)
(cond
[(= n0) m]
[else (my-gcd n
(remainder m n))]))
(my-gcd 180 32)
2. DrScheme を使って，ステップ実行の様子を
確認しなさい （Step ボタン，Next ボタンを使用）
•理解しながら進むこと
☆次は，課題に進んでください
例題６
と同じ
「例題７．ステップ実行」の手順
83
(my-gcd 180 32)
= …
= (my-gcd 32 20)
= …
= (my-gcd 20 12)
= …
= (my-gcd 12 8)
= …
= (my-gcd 8 4)
= …
= (my-gcd 4 0)
= …
= 4 実行結果
コンピュータ内部での計算
最初の式
(my-gcd 180 32) から 4 が得られる過程の概略
84
(my-gcd 180 32)から (my-gcd 32 20) が得られる過程
(my-gcd 180 32)
= …
= (my-gcd 32 20)
= …
= (my-gcd 20 12)
= …
= (my-gcd 12 8)
= …
= (my-gcd 8 4)
= …
= (my-gcd 4 0)
= …
= 4
(my-gcd 180 32)
= (cond
[(= 32 0) 180]
[else (my-gcd 32
(remainder 180 32))])
= (cond
[false 180]
[else (my-gcd 32
(remainder 180 32))])
= (my-gcd 32
(remainder 180 32))
= (my-gcd 32 20)
この部分は
180 を32 で割った余り
は20 85
(my-gcd 180 32)
= …
= (my-gcd 32 20)
= …
= (my-gcd 20 12)
= …
= (my-gcd 12 8)
= …
= (my-gcd 8 4)
= …
= (my-gcd 4 0)
= …
= 4
(my-gcd 180 32)
= (cond
[(= 32 0) 180]
[else (my-gcd 32
(remainder 180 32))])
= (cond
[false 180]
[else (my-gcd 32
(remainder 180 32))])
= (my-gcd 32
(remainder 180 32))
= (my-gcd 32 20)
この部分は
これは，
(define (my-gcd m n)
(cond
[(= n0) m]
[else (my-gcd n
(remainder m n))]))
のmを180 で，nを32 で置き換えたもの
(my-gcd 180 32) から (my-gcd 32 20) が得られる
過程
86
(my-gcd 180 32)
= …
= (my-gcd 32 20)
= …
= (my-gcd 20 12)
= …
= (my-gcd 12 8)
= …
= (my-gcd 8 4)
= …
= (my-gcd 4 0)
= …
= 4
①
②
③
④
⑤
⑥m=180, n=32 のとき，
6回繰り返して実行される
my-gcd が繰り返される回数
87
12-3 課題
88
•関数 my-gcd （授業の例題６）に関する問題
•(my-gcd 210 66) から 6 が得られる過程の概略を
数行程度で説明しなさい
•DrScheme のstepper を使うと，すぐに分かる
課題１
89
•バックの中のコインの合計を求める関数
sum-coin についての問題
•下記の空欄を埋めて，関数 sum-coins の定義を終
えなさい．実行結果も報告しなさい
•sum-coins は，コインの個数のリストと，コイン
の金額のリストの２つのリストを入力とする
;; Contract: sum-coins : a-list-of-numbers a-list-of-numbers -> number
;; Example: (sum-coins (list 23 0 5 7) (list 1 5 10 25)) = 248
(define (sum-coins a b)
(cond [( ) ]
[else (+ (* ( ) ( ))
( ( ) ( )))]))
課題２
90
•ここにあるのは「間違い」の例です．同じ間
違いをしないこと
１．(= a empty) は間違い
⇒a がリストのとき、(= a empty) はエラーです．
「=」は数値の比較には使えるが，リスト同士
の比較には使えないものと考えて下さい
正しくは，(empty? a) です
課題２のヒント
91
•関数 my-gcd （授業の例題６）に関する問題
•m, n の最大公約数を，ユークリッドの互助法で求
めた場合と，次ページに示すような方法で求めた場
合とで，関数の繰り返し回数を比較し，自分なりの
考察を加えて報告しなさい
課題３．繰り返し回数
92
(define (first-divisor n m i)
(cond
[(= i1) 1]
[else (cond
[(and (= (remainder n i) 0)
(= (remainder m i) 0)) i]
[else (first-divisor n m (- i1))])]))
(define (gcd-structural n m)
(first-divisor n m (min n m)))
1. まず，n とm の小さい方を変数 i に入れる．
2. i がn とm の両方を割れれば i の値を返し，終了．
3. i の値を1小さくして2へ．
→n とm は変わらない．i が変化
「i で割り切れるかを調べながら，
i を１減らす」ことを，割り切れる
まで繰り返す
93
•「エラトステネスのふるい」の原理に基づ
いて100以下の素数を求めるプログラムを作
りなさい
課題４．エラトステネスのふるい
94
２ ３ ４ ５ ６ ７ ８ ９ １０ １１ ・・・
２×２２×３２×４２×５
まず，２の倍数を消す
エラトステネスのふるい (1/4)
95
２ ３ ４ ５ ６ ７ ８ ９ １０ １１ ・・・
３×２
次に，３の倍数を消す
３×３
エラトステネスのふるい (2/4)
96
２ ３ ４ ５ ６ ７ ８ ９ １０ １１ ・・・
次に，５の倍数を消す
（「４の倍数」は考えない．
それは，「４」がすでに消えているから）
５×２
エラトステネスのふるい (3/4)
97
２ ３ ４ ５ ６ ７ ８ ９ １０ １１ ・・・
以上のように，２，３，５・・・の倍数を消す．
１０（これは１００の平方根）を超えたら，この操作を止める
（１００以下で，１１，１３・・・の倍数はすでに消えている）
エラトステネスのふるい (4/4)
98
