【擬似言語⑧】偶数と素数 | 小さい関数から組んでみる（基本情報技術者, 科目B, アルゴリズム）

このNoteでは、偶数と素数をある範囲で生成する擬似言語をテーマにします。偶数は簡単ですが、素数はちょっと難しいですよね。

教科書や過去問では「こんぐらい素組みしなさい」ですが。このNoteでは、小さい関数作りから逆アプローチしてみます。偶数/素数か判別する関数、ある範囲で呼び出す関数の2つに分けます。

素数アルゴがちょっと難しいって感じてた方が、少しスッキリしたら嬉しいです。

テキストの基礎を生かして、プログラム的な考察/工夫を学んでいきます。基礎と実用にギャップを感じる方のために作りました。
＞【FEB】擬似言語の教科書Note

ぜひ一緒に学習を進めていきましょう！

このNoteは、私がIT専門学校で授業したことを基に作成しています。IT専門学校でFEは第一目標として、カリキュラムが構築されています。何も知らずに入学しても、1年生10月にはFE合格していきますよ。実績ある教育ノウハウを詰め込んだので、少しでも信頼して頂けたら嬉しいです。

＞全Noteへのリンク（FE節）
※科目Aのテーマ別/科目B/旧FE午後など沢山作りました！

偶数アルゴ | 教科書アルアル

「1から10までの数のうち、偶数を表示する」擬似言語を作ります。教科書でよくあるやつです。

○手続き：calcEvenNumbers()
  整数型: i

  / 1から10まで1ずつ増やしながらループ */
  for (i を 1 から 10 まで 1 ずつ増やす)      
    / iを2で割った余りが0と等しい（＝偶数）なら */
    if (i mod 2 が 0 に等しい)
      「iの値」を表示
    endif      
  endfor

for文で「i」を「1」から「10」まで「1ずつ増や」して、その間にif文で「2で割り切れたら（=余りが0だったら）偶数」と判定します。

「mod」を使う良い機会なので、教科書/先生が、学習者/学生さんに組ませたいアルゴリズムです。

もっと簡単な方法がありますね。

○手続き：calcEvenNumbers2()
  整数型: i

  for (i を 2 から 10 まで 2 ずつ増やす)      
    「iの値」を表示
  endfor

iを「2」から「10」まで「2ずつ増やす」と、2, 4, 6, 8, 10。内心”なんだかなぁ”とお互い思っちゃいますが、正しいですね。

関数化 | 機能を分ける

「1から10の偶数を表示」って簡単なアルゴリズムだし、擬似言語の練習課題だから、1つの関数にしちゃいましたが。機能は2つに分けられます。

「1から10の数を生み出す」「ある数が偶数か判断する」。

「ある数が偶数か判断する」を関数を作ってみます。

○論理型：isEven(整数型: num)
  / numを2で割った余りが0と等しいなら、true（真）を返す */
  if (num mod 2 が 0 に等しい)
      return true
  else
      return false
  endif

「1から10の数を生み出す」関数内で、呼び出します。

○手続き：calcEvenNumbers()
  整数型: i

  for (i を 1 から 10 まで 1 ずつ増やす)      
      if (isEven(i) が true に等しい)
          「iの値」を表示
      endif      
  endfor

素数アルゴ | 教科書にないアプローチで

「1から10までの数のうち、素数を表示する」擬似言語を作ります。教科書でよくあるやつ。ちょっと難しい。

教科書ではいきなり組ませますが、今回は「1から10の数を生み出す」「ある数が素数か判断する」に分けて考えてみます。

テキストで挫折された方に少しでもサポートできたら嬉しいです。

「素数」とは、2以上の自然数で、約数が1とその数自身だけの数。つまり、3は素数（1と3だけで割り切れるので）、5も素数（1と5だけ）。4はダメ（1, 2, 4）、6もダメ（1, 2, 3, 6）。

「ある数が素数か判断する」関数は、for文で「i」を「2」から「num-1」まで「1ずつ増やし」ながら、「引数num」が「i」割り切れるかで判断するアルゴリズム。「1」と「num」で割り切れるのは当然なので調べず、「2」から「num-1」になってます。

○論理型：isPrime(整数型: num)
  整数型: i
  論理型: divideFlag

  divideFlag ← true
  for (i を 2 から num-1 まで 1 ずつ増やす)      
    / numがiで割り切れる（余りが0）なら、素数ではない */
    if (num mod i = 0)
      divideFlag ← false
    endif      
  endfor

  / 割り切れる数が一度もなければ true、あれば false を返す */
  if (divideFlag = true)
    return true
  else
    return false
  endif

事前に「divideFlag ← true 素数である」としておいて、一度割り切れたら「divideFlag ← false 素数じゃない」に変えます。ループ前にキメウチして適宜変更するテは以前使いましたね、＞＊

バグ対応 | 引数チェック

少しバグ対応。「素数とは、2以上の自然数～」なので、1は素数じゃないし、-1や-2も素数じゃないです。引数に入ったら計算しないで弾きたい。

「引数が2以上の数か」のチェックを追加します。

  / 1（以下も）は素数ではない */
  if (num ≦ 1)
    return false
  endif

○論理型：isPrime(整数型: num)
  整数型: i
  論理型: divideFlag

  / 1（以下も）は素数ではない */
  if (num ≦ 1)
    return false
  endif

  divideFlag ← true
  for (i を 2 から num-1 まで 1 ずつ増やす)      
    / numがiで割り切れる（余りが0）なら、素数ではない */
    if (num mod i = 0)
      divideFlag ← false
    endif      
  endfor

  / 割り切れる数が一度もなければ true、あれば false を返す */
  if (divideFlag = true)
    return true
  else
    return false
  endif

関数最初に引数チェックするのも、以前のNoteでやりましたね。＞【擬似言語⑤】最大値のNote（引数チェック）

効率化❶ | これ以上やる必要ない→ループ離脱break

少しずつ効率化もしたいです。

1度でも割り切れたら素数じゃないので、それ以上判定する必要はありません。

例えば「4」の時、2で割り切れた瞬間に「素数じゃない」のが確定するので、3で割り切れるか調べる必要がありません。ループと途中で抜けちゃいましょう（break）。

    if (num mod i = 0)
      divideFlag ← false
      break / 以降の判定を止める*/
    endif      

○論理型：isPrime(整数型: num)
  整数型: i
  論理型: divideFlag

  / 1（以下も）は素数ではない */
  if (num ≦ 1)
    return false
  endif

  divideFlag ← true
  for (i を 2 から num-1 まで 1 ずつ増やす)      
    / numがiで割り切れる（余りが0）なら、素数ではない */
    if (num mod i = 0)
      divideFlag ← false
      break / 以降の判定を止める*/
    endif      
  endfor

  / 割り切れる数が一度もなければ true、あれば false を返す */
  if (divideFlag = true)
    return true
  else
    return false
  endif

「それ以上する必要がない」時のループ離脱は、線形探索でやりましたね。　＞【擬似言語⑥】線形探索のNote

効率化❷ | これ以上やる必要ない → 関数離脱return

更に効率化を考えて見ます。

ループをbreakしたのは「素数じゃないのが確定した」からなので、「return false」で関数自体も終了しちゃいましょう。

    if (num mod i = 0)
      return false
    endif      

ループを全部通り抜けたってことは、一度も「素数じゃない」判定を受けなかったので「素数だった」んです。「return ture」で関数を終了して良いですね。

  for (i を 2 から num-1 まで 1 ずつ増やす)      
    ～～略～～
  endfor
  return ture

以上で「return false」「return true」をするので、変数「divideFlag」は要らなくなったので消します。最後のif文（devideFlagに応じたretrun実行）も不要に。

完成版

以上より、3点盛り込んで完成版に仕上げます。

• [1]：最初に引数チェック

• [2]：割り切れチェック
  一度でも割り切れたら、false返して終了

• [3]：ループ抜けたら、true返して終了

○論理型：isPrime(整数型: num)
  整数型: i

  / [1] 1（以下も）は素数ではない */
  if (num ≦ 1)
    return false
  endif

  / [2] 素数か判定*/
  for (i を 2 から num-1 まで 1 ずつ増やす)      
    / numがiで割り切れる（余りが0）なら、素数ではない */
    if (num mod i が 0 に等しい)
      return false
    endif      
  endfor
  / [3] 素数だった判定
  return true

大分スッキリしましたね。見やすいし分かり易い。

関数の実装とブチマケ

やっと「ある数を素数か判定する関数」が出来たので、「1から10の数を生み出す」関数に呼び出してもらいましょう。

○ calcPrimeNumbers()
  整数型: n

  for (n を 1 から 10 まで 1 ずつ増やす)
      if (isPrime(n) が true に等しい)
          表示(n, "は素数です")
      endif
  endfor

すごいシンプルで良き。

折角なんで、関数の中身をぶちまけて整えてみます。

○ calcPrimeNumbers()
  整数型: n
  整数型: i
  論理型: isPrimeFlag

  / 1から10までの数を生み出す */
  for (n を 1 から 10 まで 1 ずつ増やす)    
    / [1] 1以下の数は素数ではない */
    if (n ≦ 1)
      isPrimeFlag ← false
    else
      / 一旦、素数であると仮定する */
      isPrimeFlag ← true
      
      / [2] 素数か判定（2 から n-1 まで回す） */
      for (i を 2 から n-1 まで 1 ずつ増やす) / [A]breakで離脱*/
        / nがiで割り切れるなら、素数ではない */
        if (n mod i が 0 に等しい)
          isPrimeFlag ← false
          break / これ以上ループする必要ないので抜ける[A] */
        endif
      endfor
    endif
    
    / [3] 素数だった場合の表示処理 */
    if (isPrimeFlag が true に等しい)
      表示(n, "は素数です")
    endif

  endfor

公開問題でも「素数」は出てますが、上のより少し簡単です。引数チェックないので。＞【FEB】令和05年問01のNote

引数チェックのif文を抜きました（nを1から→2から に変更）。ほぼ過去問と同じ（変数名が違うぐらい）。

○ calcPrimeNumbers()
  整数型: n
  整数型: i
  論理型: isPrimeFlag

  / 1から10までの数を生み出す */
  for (n を 2 から 10 まで 1 ずつ増やす)    
    isPrimeFlag ← true
      
    / [2] 素数か判定（2 から n-1 まで回す） */
    for (i を 2 から n-1 まで 1 ずつ増やす) / [A]breakで離脱*/
      / nがiで割り切れるなら、素数ではない */
      if (n mod i が 0 に等しい)
        isPrimeFlag ← false
        break / これ以上ループする必要ないので抜ける[A] */
      endif
    endfor
    
    / [3] 素数だった場合の表示処理 */
    if (isPrimeFlag が true に等しい)
      表示(n, "は素数です")
    endif

  endfor

まとめ

お疲れ様でした！

教科書では素組みするところを、2つの機能（偶数/素数を判定、判定する数を反復生成）に分けて、確実に動く小さい関数を作って、ガッチャンコするアプローチで学習してみました。今までの勉強と味変して刺激になったら良いかなと。

このシリーズは、＞【FEB】擬似言語の教科書Note の基礎を生かしつつ、考察と次回への布石を追加して「知識のリレー」を繋いでいくように作っています。

次回は、オツリの各硬貨枚数を算出をテーマにします。使う硬貨を100円だけ、50円も追加、10円や1円も追加って仕様拡張を、配列を使って手軽になるのを学びます。＞【擬似言語⑧】オツリ硬貨と配列の拡張性のNote

今回カットした課題を出しておきます。解説はLv3や4かな（未定＊）

• 課題1：奇数を表示する擬似言語に改良して下さい。

• 課題2：引数を設けて「startNumからendNumの偶数を表示する」擬似言語に、2つの関数の改良して下さい。

• 課題3：引数を設けて「multipleの倍数を表示する」擬似言語に更に改良して下さい。例えば、4の倍数を表示する、みたいな。

最後に私のお薦めの演習順番。
❶学習前の”分からせ”
＞【FEB】サンプル問題2のNote
❷テキスト
＞【FEB】擬似言語の教科書Note
＞【FEB】擬似言語の理解演習Note ←いまこの辺
↓※必要なら
うかる！ 基本情報技術者　[科目B・セキュリティ編](amazon)
うかる！ 基本情報技術者　[科目B・アルゴリズム編](amazon)
❸各年度の公開問題
＞【FEB】令和07年科目BのNote
＞【FEB】令和06年科目BのNote
＞【FEB】令和05年科目BのNote
➍解法の総復習（➋や➌と併用可）
＞【FEB】擬似言語の11の解法Note
➎模擬試験
＞【FEB】サンプル問題1のNote（擬似言語）
＞【FEB】サンプル問題1のNote（セキュリティ）