sp-12. 再帰と繰り返しの回数

sp-12. 再帰と繰り返しの回数 （Scheme プログラミング） URL: https://www.kkaneko.jp/pro/scheme/index.html 金子邦彦 1

• https://www.kkaneko.jp/pro/scheme/index.html

アウトライン 12-1 繰り返し計算 12-2 パソコン演習 12-3 課題 2

本日の内容 • 再帰を使った，繰り返し計算 • 数学の「再帰的定義」と，Scheme プログラムの関係 • 繰り返し回数 • 関数は「何回繰り返して」実行され るか 3

12-1 繰り返し計算 4

繰り返しの例 • 階乗 • 「n - 1 の階乗」に n を足すことを繰り返す • ユークリッドの互助法 • m と n の最大公約数を求めるために，「割った余 りを求めること」を，余りが０になるまで繰り返 す 5

12- 2 パソコン演習 6

パソコン演習の進め方 • 資料を見ながら，「例題」を行ってみる • 各自，「課題」に挑戦する • 自分のペースで先に進んで構いません 7

DrScheme の使用 • DrScheme の起動 プログラム • → PLT Scheme → DrScheme 今日の演習では「Intermediate Student」 に設定 Language → Choose Language → Intermediate Student → Execute ボタン 8

例題１． 階乗 • 階乗を計算する関数 ! を作り，実行す る • 次の方針でプログラムを作成する n > 0 のとき，n! = n × (n-1)! 例） 6! = 6×5! 9

階乗 • n = 0 のとき n!= 1 • n > 0 のとき n! = n  ( n − 1)! 10

「例題１．階乗」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • 入力した後に，Execute ボタンを押す ;;! : number -> number ;;to compute n*(n-1)*...*2*1 (define (! n) (cond [(= n 0) 1] [else (* n (! (- n 1)))])) 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 0! = 1 である [(= n 0) 1] [else (* n (! (- n 1)))])) n! は (n-1)! を計算して，n を掛ける 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 終了条件 [(= n 0) 1] 自明な解 [else (* n (! (- n 1)))])) 18

終了条件 (= n 0) No Yes (* n (! (- n 1))) 1 が自明の解 19

階乗 • ! の内部に ! が登場 (define (! n) (cond [(= n 0) 1] [else (* n (! (- n 1)))])) • ! の実行が繰り返される 例： (! 5) = (* 5 (! 4)) (! 4) = (* 4 (! 3)) 20

例題２．ステップ実行 • 関数 ! （例題１）について，実行結果に至る過程 を見る • (! 3) から 6 に至る過程を見る • DrScheme の stepper を使用する (define (! n) (cond [(= n 0) 1] [else (* n (! (- n 1)))])) (! 3) = ... = (* 3 (! 2)) = ... = (* 3 (* 2 (! 1))) = ... = (* 3 (* 2 (* 1 (! 0)))) = ... = (* 3 (* 2 (* 1 1))) = (* 3 (* 2 1)) = (* 3 2) = 6 21

「例題２．ステップ実行」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • • Intermediate Student で実行すること 入力した後に，Execute ボタンを押す ;;! : number -> number ;;to compute n*(n-1)*...*2*1 (define (! n) (cond [(= n 0) 1] [else (* n (! (- n 1)))])) (! 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) から 6 が得られる過程の概略 最初の式 (! 3) = ... = (* 3 (! 2)) = ... = (* 3 (* 2 (! 1))) = ... = (* 3 (* 2 (* 1 (! 0)))) = ... = (* 3 (* 2 (* 1 1))) = (* 3 (* 2 1)) = (* 3 2) コンピュータ内部での計算 = 6 実行結果 41

(! 3) から 6 が得られる過程の概略 (! 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)) 42

(! 3) から 6 が得られる過程の概略 (! 3) = ... = (* 3 (! 2)) = = = = = = = = この部分は (! 3) = (cond [(= 3 0) 1] [else (* 3 (! (- 3 1)))]) = (cond [false 1] [else (* 3 (! (- 3 1)))]) = (* 3 (! (- 3 1))) = (* 3 (! 2)) ... (* 3 (* 2 (! 1))) これは， ... (* (define 3 (* 2 (* (! 1 (!n)0)))) ... (cond (* 3 (* [(= 2 (*n1 0) 1)))1] (* 3 (* [else 2 1)) (* n (! (- n 1)))])) の を 3 で置き換えたもの (* 3n 2) = 6 43

(! 3) から 6 に至る過程 (! 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))))」 が収縮して６になる 44

線形再帰的プロセス • 基本的な計算式へ展開 例 (! 3) ⇒ (* 3 (* 2 (* 1 (! 0)))) 再帰の呼び出し回数（＝ステップ 数ともいう）に比例して成長する ⇒ 「線形再帰」の名前の由来 45

! が繰り返される回数 (! 3) ① = ... = (* 3 (! 2)) ② = ... = (* 3 (* 2 (! 1))) ③ = ... = (* 3 (* 2 (* 1 (! 0)))) ④ = ... = (* 3 (* 2 (* 1 1))) = (* 3 (* 2 1)) n=3 のとき， = (* 3 2) = 6 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))) n=4 のとき， = (* 4 (* 3 2)) 5回繰り返して実行される = (* 4 6) 47 = 24

例題３． 反復的プロセスでの階乗 • 階乗を計算する関数 ! を作り，実行す る • 次の方針でプログラムを作成する n > 0 のとき，1 から開始して，1 × 2 ×・・・×n を計算する 例） (! 6) = 1 × 2 × 3 × 4 × 5 × 6 48

反復的プロセスでの階乗 • n! の計算 1. 2. 3. 4. まず，1 に 2 を掛ける 次に，3 を掛ける ・・・ 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

! 関数 ;; ! : number -> number ;; to compute n*(n-1)*...*2*1 ;; (! 4) = 24 (define (! n) (factorial 1 1 n)) (define (factorial product counter n) (cond product ← counter・product [(> counter n) product] [else (factorial (* counter product) (+ counter 1) n)])) counter ← counter + 1 54

反復的プロセスでの階乗 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

反復的プロセスでの階乗 ;; ! : 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)])) 57

終了条件 (> counter n) Yes No (factorial (* counter product) (+ counter 1) n) product が自明の解 58

例題４．ステップ実行 • factorial の内部に factorial が登場 (define (factorial product counter n) (cond [(> counter n) product] [else (factorial (* counter product) (+ counter 1) n)])) • factorial の実行が繰り返される 例： (factorial 6 4 10) = (factorial 24 5 10) (factorial 24 5 10) = (factorial 120 6 10) 59

例題４．ステップ実行 • 関数 ! （例題３）について，実行結果に至る過程 を見る • (! 4) から 24 に至る過程を見る • DrScheme の stepper を使用する (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 60

「例題４．ステップ実行」の手順 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) から 24 が得られる過程の概略 (! 4) 最初の式 = (factorial 1 1 4) = ... = (factorial 1 2 4) = ... = (factorial 2 3 4) = ... = (factorial 6 4 4) = ... = (factorial 24 5 4) = ... コンピュータ内部での計算 = 24 実行結果 62

(! 4) から 24 が得られる過程の概略 (! 4) = (factorial 1 1 4) = ... = (factorial 1 2 4) product, counter の = ... 値が変化する = (factorial 2 3 4) ・counter = ... → 繰り返し回数 = (factorial 6 4 4) ・product = ... → 部分積 = (factorial 24 5 4) = ... = 24 product counter max 63

反復的プロセスの特徴 • 線形再帰的プロセスのような伸び縮みは無い • 関数を再帰的に呼び出す各ステップで計算が実 行される 例 (! 3) = (factorial 1 1 3) = (factorial 1 2 3) = (factorial 2 3 3) = (factorial 6 4 3) 伸び縮み無し 各ステップで， product と counter に関する計算が 実行される 64

(factorial 1 1 4) から (factorial 1 2 4) が得られる過程 (! 4) (factorial 1 1 4) = (factorial 1 1 4) = (cond = ... [(> 1 4) 1] = (factorial 1 2 4) この部分は [else (factorial (* 1 1) (+ 1 1) = ... 4)]) = (factorial 2 3 4) = (cond [false 1] = ... [else (factorial (* 1 1) = (factorial 6 4 4) (+ 1 1) 4)]) = ... = (factorial (* 1 1) (+ 1 1) 4) = (factorial 24 5 4) = (factorial 1 (+ 1 1) 4) = ... = (factorial 1 2 4) = 24 65

(factorial 1 1 4) から (factorial 1 2 4) が得られる過程 (! 4) (factorial 1 1 4) = (factorial 1 1 4) = (cond = ... [(> 1 4) 1] = (factorial 1 2 4) この部分は [else (factorial (* 1 1) (+ 1 1) = ... 4)]) = (factorial 2 3 4) = (cond これは， [false 1] = ...(define (factorial product counter n) [else (factorial (* 1 1) (cond = (factorial 6 4 4) (+ 1 1) [(> counter n) product] 4)]) = ... [else (factorial (* counter product) (+ counter 1) = (factorial (* 1 1) (+ 1 1) 4) = (factorial 24 n)])) 5 4) = (factorial 1 (+ 1 1) 4) counter を 1 で，product を 1 で，n を 4 で置き換えたもの = の... = (factorial 1 2 4) = 24 66

(! 4) から (* 4 (! 3)) が得られる過程 (! 4) (! 4) = ... = (cond = (* 4 (! 3)) [(= 4 0) 1] この部分は [else (* 4 (! (- 4 1)))]) = ... = (cond = (* 4 (* 3 (! 2))) [false 1] = ... [else (* 4 (! (- 4 1)))]) これは， = (* 4 (* 3 (* 2 (! 1)))) = (* 4 (! (- 4 1))) = ... (define (! n) = (* 4 (! 3)) = (* 4 (* 3 (* 2 (* 1 (! 0))))) = ... (cond = (* 4 (* [(= 3 (*n2 0) (* 1] 1 1)))) = (* 4 (* [else 3 (* 2 (* 1)))n (! (- n 1)))])) = の (* 4n (* を342))で置き換えたもの = (* 4 6) = 6 67

factorial が繰り返される回数 (! 4) = (factorial 1 1 4) ① = ... = (factorial 1 2 4) ② = ... = (factorial 2 3 4) ③ = ... = (factorial 6 4 4) ④ = ... = (factorial 24 5 4) ⑤ n=4 のとき， = ... 5回繰り返して実行される 68 = 24

例題５．繰り返し回数 • 次のプログラムでは，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 [(= n 0) 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

入力と出力 180 32 4 my-gcd 入力 入力は，２つの数値 出力 出力は数値 76

my-gcd 関数 ;; 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 [(= n 0) m] [else (my-gcd n (remainder m n))])) 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 終了 条件 [(= n 0) m]自明な解 [else (my-gcd n (remainder m n))])) 79

終了条件 (= n 0) No Yes (my-gcd n (remainder m n) m が自明の解 80

最大公約数の計算 • my-gcd の内部に my-gcd が登場 (define (my-gcd m n) (cond [(= n 0) m] [else (my-gcd n (remainder m n))])) • my-gcd の実行が繰り返される 例： (my-gcd 180 32) = (my-gcd 32 20) 81

例題７．ステップ実行 • 関数 my-gcd （例題６）について，実行結果に至 る過程を見る • (my-gcd 180 32) から 4 に至る過程を見る • DrScheme の stepper を使用する (define (my-gcd m n) (cond [(= n 0) 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 82

「例題７．ステップ実行」の手順 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 と同じ [(= n 0) m] [else (my-gcd n (remainder m n))])) (my-gcd 180 32) 2. DrScheme を使って，ステップ実行の様子を 確認しなさい （Step ボタン，Next ボタンを使用） • 理解しながら進むこと ☆ 次は，課題に進んでください 83

(my-gcd 180 32) から 4 が得られる過程の概略 (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 実行結果 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 180 32) (my-gcd 180 32) =… = (cond = (my-gcd 32 20) [(= 32 0) 180] =… この部分は [else (my-gcd 32 = (my-gcd 20 12) (remainder 180 32))]) =… = (cond = (my-gcd 12 8) [false 180] これは， =… [else (my-gcd 32 (define (my-gcd m n) = (my-gcd 8 4) (remainder 180 32))]) = (my-gcd 32 = … (cond [(= 4n 0) 0) m] (remainder 180 32)) = (my-gcd [else (my-gcd n = (my-gcd 32 20) =… (remainder m n))])) =4 の m を 180 で，n を 32 で置き換えたもの 86

my-gcd が繰り返される回数 (my-gcd 180 32) ① =… = (my-gcd 32 20) ② =… = (my-gcd 20 12) ③ =… = (my-gcd 12 8) ④ =… = (my-gcd 8 4) ⑤ =… = (my-gcd 4 0) ⑥ =… m=180, =4 n=32 のとき， 6回繰り返して実行される 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 [(= i 1) 1] [else (cond [(and (= (remainder n i) 0) (= (remainder m i) 0)) i] [else (first-divisor n m (- i 1))])])) (define (gcd-structural n m) (first-divisor n m (min n m))) 「i で割り切れるかを調べながら， i を１減らす」ことを，割り切れる まで繰り返す 1. まず，n と m の小さい方を変数 i に入れる． 2. i が n と m の両方を割れれば i の値を返し，終了． 3. i の値を1小さくして2へ． → n と m は変わらない．i が変化 93

課題４．エラトステネスのふるい • 「エラトステネスのふるい」の原理に基づ いて100以下の素数を求めるプログラムを作 りなさい 94

エラトステネスのふるい (1/4) ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ ・・・ ２×２ ２×３ ２×４ ２×５ まず，２の倍数を消す 95

エラトステネスのふるい (2/4) ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ ・・・ ３×２ ３×３ 次に，３の倍数を消す 96

エラトステネスのふるい (3/4) ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ ・・・ ５×２ 次に，５の倍数を消す （「４の倍数」は考えない． それは，「４」がすでに消えているから）97

エラトステネスのふるい (4/4) ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ ・・・ 以上のように，２，３，５・・・の倍数を消す． １０（これは１００の平方根）を超えたら，この操作を止める （１００以下で，１１，１３・・・の倍数はすでに消えている） 98