科目Bの数値計算問題の解き方｜素数・約数・最大公約数を追うコツ

素数とか最大公約数とか、数学の問題みたいで手が止まってしまう。

科目Bで、数字ばかりが並ぶコードを見て身構えたことはありませんか？

配列や文字列の問題なら追えるのに、素数や約数が出てくると、急に数学のテストを受けている気分になる。そう感じている人は少なくないのではないでしょうか。

大丈夫です。科目Bの数値計算の問題で必要なのは、数学のひらめきではありません。割る数と余りを表に書いて、1行ずつ追っていく地道な手順だけです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、割り算の余りを使って偶数行だけ色を変えたり、件数を一定の単位で区切ったりする処理は日常的に書いています。

そうした処理でつまずく原因は、たいてい計算そのものではなく、ループの範囲や条件の境目を読み違えることです。この記事では、その読み違えを防ぐ方法を、科目Bの解き方に合わせて5つの段階で紹介します。

科目B全体の中で、数値計算のようなアルゴリズムの問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

数値計算の問題は何を聞いているのか¶

最初に、数値計算の問題がどんな形で出てくるのかを押さえておきましょう。何を求めるコードなのかが分かるだけで、読む場所はぐっと絞り込めます。

数値計算の問題とは、整数を受け取り、割り算や余りを使って性質を調べる処理のことです。素数かどうか、約数がいくつあるか、2つの数の最大公約数はいくつか、といった内容がよく題材になります。

どれも中学校で習う言葉ですが、試験で問われるのは数学の知識そのものではありません。その性質を調べるコードが、どう動き、どこで答えを出すかです。

よく出る題材と見るべきポイント¶

数値計算の問題で扱われる題材は、いくつかの型に収まります。代表的なものを表にまとめました。

表のとおり、どの題材にも共通しているのは、割り算の余りが 0 かどうかで判断している点です。ここさえ押さえれば、題材が変わっても読み方は同じです。

割り切れるとは余りが 0 のこと¶

数値計算のコードを読むうえで、いちばん大切な言い換えがあります。a が b で割り切れるということは、a を b で割った余りが 0 だということです。

たとえば 12 を 3 で割ると余りは 0 なので、3 は 12 の約数です。12 を 5 で割ると余りは 2 なので、5 は約数ではありません。

素数も約数も最大公約数も、すべてこの一文の組み合わせでできています。コードの中に余りが 0 と等しいという条件を見つけたら、割り切れるかどうかを調べている、と読み替えてください。

余りと商の計算そのものに不安がある場合は、文法を整理したこちらの記事で先に確認しておくと安心です。

【関連記事】擬似言語の余り（剰余）と割り算がわからない人へ｜偶数判定と桁の取り出しを解説

まず目を付ける場所¶

設問の意味がつかめたら、次はコードのどこから読むかを決めます。数値計算の問題では、目を付ける場所が3つに絞られます。

ひとつ目はループの範囲、ふたつ目は余りを調べる条件、みっつ目は答えを返す場所です。この順番で見ていくと、全体の流れが自然に見えてきます。

ループの範囲で何を試しているかを見る¶

最初に見るのは、for や while がどこからどこまで回っているかです。数値計算のループは、割る数の候補を順番に試していることがほとんどです。

1 から n までなら、約数をすべて探しています。2 から n − 1 までなら、1 と自分自身以外に割り切れる数がないか、つまり素数かどうかを調べています。

上限が n ではなく、i × i が n 以下という形になっていることもあります。これは、調べる範囲を半分以下に減らす工夫です。理由はあとの例題で確かめます。

途中で抜ける場所と返す値を見る¶

次に見るのは、ループの途中で return している場所や、フラグを書き換えている場所です。素数判定では、割り切れる数が1つでも見つかった時点で、素数ではないと答えが決まります。

そのため、コードには途中で結果を返す行か、見つかったことを記録するフラグが必ずあります。どちらの書き方なのかを先に確かめておくと、トレースのときに迷いません。

フラグを使った書き方の読み方は、こちらの記事でくわしく解説しています。

【関連記事】擬似言語のフラグ変数（論理型）の使い方とは？見つかったかどうかを覚えておく処理を解説

例題：素数判定と最大公約数¶

ここからは、実際の例題を使って追い方を確かめます。まずは素数判定です。

次のコードは、受け取った整数 n が素数なら true を、素数でなければ false を返す関数です。なお、この記事の例題はどれも説明のために作成したもので、IPA の公開問題そのものではありません。

○論理型: isPrime(整数型: n)
  整数型: d
  if (n が 2 より小さい)
    return false
  endif
  d ← 2
  while (d × d が n 以下)
    if (n ÷ d の余り が 0 と等しい)
      return false
    endif
    d ← d + 1
  endwhile
  return true

最初の if は、1 以下の数を素数から外すための処理です。素数は 2 以上の数で考えるので、ここで先に答えを返しています。

while の中では、d を 2 から1ずつ増やしながら、n が d で割り切れるかを調べています。割り切れたら、その時点で false を返して終わりです。

最後まで割り切れる数が見つからなければ、ループを抜けて true を返します。素数判定のコードは、ほとんどがこの形をしています。

d × d が n 以下で止めてよい理由¶

ここで気になるのが、なぜ d を n − 1 まで試さず、d × d が n 以下のところで止めてよいのか、という点です。答えは、約数がペアになっていることにあります。

たとえば 36 の約数は、1 と 36、2 と 18、3 と 12、4 と 9、6 と 6 のようにペアで現れます。ペアの小さいほうは、必ず 6 以下に収まっています。

つまり、小さいほうの候補だけ調べれば、割り切れる数があるかどうかは判定できます。小さいほうの上限が、d × d が n を超えない範囲というわけです。

試験でこの理由を説明させられることはあまりありません。けれども、ループの上限を選ぶ空欄問題では、この考え方を知っているかどうかで迷う時間が大きく変わります。

最大公約数を求めるコード¶

続いて、最大公約数を求めるコードを見てみましょう。2つの数を割り続けて答えを出す、ユークリッドの互除法と呼ばれる方法です。

○整数型: gcd(整数型: a, 整数型: b)
  整数型: r
  while (b が 0 と等しくない)
    r ← a ÷ b の余り
    a ← b
    b ← r
  endwhile
  return a

やっていることは、a を b で割った余りを求め、b を a に、余りを b に移すことの繰り返しです。余りが 0 になったとき、そのときの a が最大公約数になります。

コードは短いのですが、3行の代入が続くので、頭の中だけで追うとすぐに混乱します。こういうコードこそ、トレース表の出番です。

変数をトレース表で追う¶

では、2つのコードを実際に値を入れて追ってみましょう。変数ごとに列を作り、ループが1回まわるたびに1行ずつ書いていくのがコツです。

素数判定のトレース¶

まずは isPrime に 91 を渡した場合です。91 は一見素数に見えますが、本当にそうでしょうか？

トレース表は次のようになります。

d が 7 のとき余りが 0 になり、false が返ります。91 は 7 × 13 なので、素数ではありませんでした。

もし 97 を渡したら、d が 9 まで進んでも割り切れず、d が 10 になったところで d × d が 100 となって 97 を超えます。そこでループを抜け、true が返ります。

表にしてみると、上限の判定と余りの判定という2つの条件が、どの順番で効いているのかがよく分かります。頭の中で追うと、この2つを混ぜてしまいがちです。

最大公約数のトレース¶

次に、gcd に 48 と 18 を渡した場合を追ってみます。ここでは、代入が終わったあとの a、b、r の値を1行にまとめて書きます。

3回目の終わりで b が 0 になったので、ループを抜けて a の 6 が返ります。48 と 18 の最大公約数は、たしかに 6 です。

表を見ると、毎回、前の b が次の a に、前の余りが次の b に、斜めにずれて移っていくのが分かります。この斜めの動きをつかめれば、互除法のコードはもう怖くありません。

トレース表の作り方そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

間違いやすい選択肢の見分け方¶

数値計算の問題では、正解とよく似た誤りの選択肢が並ぶことがよくあります。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

よくある誤りを表にまとめました。

この中でも、特によく狙われるのが等号と開始値、そして代入の順番です。順番に見ていきましょう。

以下と未満の違いは平方数で試す¶

素数判定の上限で、d × d が n 以下とするか、n より小さいとするかは、空欄問題の定番です。どちらも正しそうに見えるので、読むだけではなかなか判断できません。

こういうときは、平方数を入れて試すのが近道です。たとえば n が 49 のとき、未満の条件だと d が 7 になった時点で 49 が 49 より小さいかを調べて偽になり、7 で割る前にループを抜けてしまいます。

その結果、49 が素数だと判定されてしまいます。以下の条件なら d が 7 のときも調べるので、正しく false が返ります。

境目の値で試すと、等号の有無による違いがはっきり見えます。数値計算に限らず、ループの境目で迷ったときに使える考え方です。ループの範囲の読み方は、こちらの記事でもくわしく扱っています。

【関連記事】科目Bの繰返し問題が解けない人へ｜ループ回数を追うコツ

開始値が 1 だと何が起きるか¶

素数判定で d を 1 から始める選択肢も、ときどき見かけます。どんな整数も 1 で割れば余りは 0 なので、最初の1回で必ず false が返ってしまいます。

一方で、約数を数える問題なら、1 から始めるのが正解です。1 も立派な約数だからです。

このように、同じ開始値でも、設問が何を求めているかで正解が変わります。だからこそ、最初に設問を読む段階を飛ばさないことが大切なのです。

代入の順番は1行入れ替えて試す¶

最大公約数のコードでは、a ← b と b ← r の順番を入れ替えた選択肢が狙われます。b ← r を先に実行すると、b がすでに余りに書き換わっているので、そのあとの a ← b で a にも余りが入ってしまいます。

48 と 18 で試すと、1回目の後に a も b も 12 になります。2回目は余りが 0 になって a にも 0 が入り、最後に 0 が返ります。正しい答えの 6 とは違うので、誤りだとすぐに分かります。

実務でも、値を入れ替える処理の順番を間違えると、片方の値が消えてしまう不具合になります。私も以前、2つの設定値を入れ替えるつもりで書いた処理で同じ失敗をし、両方が同じ値になっているのを見て原因に気づいたことがあります。

選択肢で迷ったら、小さな数を1組だけ選んで、それぞれの選択肢で1回分だけトレースしてみてください。全部を最後まで追わなくても、1回目の結果だけで候補を絞れることがほとんどです。

Giji Academy のシミュレーターで動かす¶

紙のトレースで動きをつかんだら、最後は実際に動かして確かめましょう。値が何度も入れ替わる処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数の値が変わる様子を目で確かめられます。互除法で a と b が斜めにずれていく様子を一度見ておくと、代入の順番で迷うことはぐっと減るはずです。

試すときは、自分で作ったトレース表と見比べながら進めてください。一致すれば理解できている証拠で、ずれたときはその行が次に練習すべき場所です。

数値を変えて何度か試すのもおすすめです。素数と素数でない数、平方数、片方がもう片方の倍数になっている2つの数など、境目になりそうな値を入れてみると、条件の意味がより深く分かります。

まずはGiji Academy の擬似言語シミュレーターで、繰返しや条件分岐の講座を選び、余りを使った処理を動かしてみてください。

まとめ¶

科目Bの数値計算の問題は、数学の難しさを問うものではありません。割り切れるとは余りが 0 のこと、という一文を軸に、ループの範囲と条件を表で追っていけば必ず解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、91 や 48 と 18 のような小さな数で十分です。小さな数を何度か自分の手で追ううちに、見慣れない数値計算のコードが出ても、落ち着いて読めるようになります。

数字ばかりのコードに見えても、中でやっていることは割って余りを見る、の繰り返しです。次に数値計算の問題に出会ったら、まずはメモ用紙に割る数と余りの列を書くところから始めてみてください。