定番アルゴリズムの読み方｜偶数の個数・ランク付け・素因数分解

問題の題材が変わるたびに、プログラムも全部覚え直さないといけないのでしょうか？

題材が違っても、 「最初の値・繰り返す範囲・条件・更新」 を分けると、処理を追いやすくなります。

今回は3題を使い、間違えやすい読み方を練習しましょう。

先に結論：3題で押さえるのは、この3つ

• 個数を数えるなら、条件に合うたびに＋1。 値そのものを足すと、個数ではなく合計になる。
• 評価を1つに決めるなら、分岐のつながりと順番を見る。 独立した「もし」は、複数の条件を満たすと何度も更新することがある。
• 素因数分解では、割り切れる間は同じ数で割り続ける。 1回だけでは、同じ素因数が複数ある場合を取りこぼす。

各題は「手で考える→コードを読む→値を追って確かめる」の順で進めます。コードは共通テスト用プログラム表記を参考にしたオリジナル学習例です。実際の過去問の引用ではなく、試験では当該問題文の説明・指示を優先してください。

道場の入口：違う題材でも、処理を分解して読む

夜の部室。壁には「道場」の紙が貼られ、ユウキの前に、題材の違う問題が並んでいました。

ユウキ「数える問題、点数を分ける問題、割り算する問題……全部違いますよ」

テッパン先輩「じゃあ、何を手がかりに読もうか」

Sandy「まず手で解いてみ。それから、何を入れて、どこを回して、何を判定して、どう更新しとるかを見るんや」

すべてのアルゴリズムが同じ形になるわけではありません。今回は、この3題に共通する読み方を身に付けます。

一問目：3桁の偶数は何個ある？

ここでは3桁の正の整数を扱います。範囲は100から999まで、両端を含めて900個です。偶数は100、102、…、998なので、個数は450個と手で求められます。

範囲の両端を含むかを確認し、最後に処理する偶数は998と押さえる。

プログラムでは「条件に合う数を見つけるたびに、個数を1増やす」と考えます。この個数を覚える変数が、カウンター変数です。

kosuu = 0
i を 100 から 999 まで 1 ずつ増やしながら繰り返す:
｜ もし i % 2 == 0 ならば:
⎿ ⎿ kosuu = kosuu + 1
表示する(kosuu)

%は割り算の余りです。i % 2 == 0は「2で割った余りが0」、つまり偶数であるという条件になります。

個数は「＋1」、合計は「＋その値」

数えるときは条件に合うたびに1を足し、合計するときは対象の値を足す。

100から105までだけを見ると、次のように進みます。

100で1個、102で2個、104で3個と増えます。101・103・105では、何も代入しないので、それまでの個数が残ります。 初期化の0は反復前に1回だけ設定し、各周回で0へ戻すことはしません。

また、個数を数えるなら kosuu = kosuu + 1。数値の合計を求めるなら、合計へiを足します。どちらも更新ですが、足すものが違います。

Sandy「見つけた数そのものを足したら、個数やなくて合計になるで。箱に何を覚えさせたいか、先に決めよか」

100から2ずつ進めたら、判定を省ける

100が偶数だと分かっているので、2ずつ増やせば、偶数だけを通れます。

kosuu = 0
i を 100 から 999 まで 2 ずつ増やしながら繰り返す:
⎿ kosuu = kosuu + 1
表示する(kosuu)

この場合、最後に処理する値は998です。結果は同じ450個ですが、反復回数は900回から450回へ減り、偶数かどうかの判定も不要になります。

ただし、開始値を101にして同じように2ずつ増やすと、通るのは奇数です。範囲・開始値・増やす幅をセットで確認しましょう。ここで比較したのは処理回数であり、実行時間が必ず半分になるという保証ではありません。

二問目：点数をA・B・C・Dに分ける

次は、0〜100の整数の点数を次のルールで分類します。

今回の重なる下限条件は大きい境界から調べ、境界の値を含むか確かめる。

92点ならA、78点ならB、55点ならC、31点ならDです。

3つ以上の行き先へ分ける分岐を多分岐と呼びます。今回は「そうでなくもし」を使って条件をつなぎます。

もし tensuu >= 80 ならば:
⎿ hyouka = "A"
そうでなくもし tensuu >= 60 ならば:
⎿ hyouka = "B"
そうでなくもし tensuu >= 40 ならば:
⎿ hyouka = "C"
そうでなければ:
⎿ hyouka = "D"

上から条件を調べ、最初に成り立った枝の処理だけを実行します。92点なら最初の条件に当たるため、残りの条件はこの分岐では調べません。

たとえば78点では、最初の tensuu >= 80 は成り立たず、次の tensuu >= 60 が成り立つのでBです。55点なら、80と60の条件を通過し、40の条件でCになります。

つまり、Bの枝に来た時点で80点未満だと分かっているため、条件に80点未満と書かなくても、今回の順番なら60〜79点だけがBになります。

「もし」を独立して並べると、結果が変わる

同じ変数への更新が重なる場合、独立した分岐とつながった多分岐で結果が変わる。

次のコードでは、それぞれの「もし」が別々の条件分岐です。

hyouka = "D"
もし tensuu >= 80 ならば:
⎿ hyouka = "A"
もし tensuu >= 60 ならば:
⎿ hyouka = "B"
もし tensuu >= 40 ならば:
⎿ hyouka = "C"

92点は3つとも満たすため、hyoukaはA→B→Cと上書きされ、最後はCになります。前回の「代入は値の更新」が、ここでも効いています。

ただし、「もし」を複数並べる書き方が常に誤りなのではありません。複数の条件について、それぞれ処理したい場合には使えます。今回は評価を1つに決めたいのに、重なる条件で同じ変数を更新していることが問題です。

順序と境界値を確かめる

つながった多分岐でも、最初に「40点以上ならC」と書けば、92点はそこでCに確定してしまいます。今回のように下限だけを調べる重なった条件は、80、60、40と、大きい境界から並べます。

これは「どんな条件でも厳しい順に書けばよい」という万能ルールではありません。範囲を重ならない条件で書く方法もあります。

境界の80点も重要です。>= 80なら80点はA、> 80へ変えれば80点はその枝を通りません。39・40、59・60、79・80を試すと、条件のずれを見つけやすくなります。

配列 Tensuu = [92, 78, 55, 31]を順に取り出し、この分岐を適用すれば、結果はA・B・C・Dです。反復するのは「人の数」、分岐するのは「その人の点数」と分けて読みましょう。

三問目：60を素因数分解する

素因数分解は、2以上の整数を素数の積で表すことです。 60を手で割ると、次のようになります。

60÷2＝30、30÷2＝15、15÷3＝5、5÷5＝1。

したがって、60＝2×2×3×5です。2が2回登場するところが、今回の急所です。

割り切れる間は同じ数で割り続け、60を2×2×3×5へ分解する。

「2で割れたら、すぐ次の候補へ進む」では、2が1個足りなくなります。必要なのは、割り切れる間は同じ数で割り続けることです。

外側で割る数を進め、内側で割り続ける

n = 60
warukazu を 2 から 60 まで 1 ずつ増やしながら繰り返す:
｜ n % warukazu == 0 の間繰り返す:
｜ ｜ 表示する(warukazu)
⎿ ⎿ n = n ÷ warukazu

繰り返しの中に、別の繰り返しが入っています。これが ネストしたループ（入れ子の繰り返し） です。

• 外側：割る数を2、3、4、…と進める。
• 内側：その数で割り切れる間、因数を表示し、nを商へ更新する。

ポイントは、割った直後は、割る数を増やさずに内側の判定へ戻ることです。

1. warukazu = 2：60は割れるので2を表示し、nを30へ更新。
2. 同じ2でもう一度判定：30も割れるので2を表示し、nを15へ更新。
3. 15は2で割れないので、内側を抜ける。ここで初めて外側が3へ進む。
4. 3で15を割ってnは5。4では割れず、5で割るとnは1になる。

表示する順番は2、2、3、5です。外側は「割る数」、内側は「同じ数で割る回数」を担当しています。

4が表示されないのは、2で割れるだけ割った後のnには、因数2が残っていないからです。4で割れるなら2でも割れるはずなので、4は候補になっても表示されません。同じ理由で、ほかの合成数も表示されず、候補を先に素数判定する必要はありません。

「nが1になった」と「外側の反復が終わった」は別

この学習用コードは、上限を固定値60にしています。nは割るたびに小さくなりますが、外側の上限は変わりません。

nが1になった後も、外側は残りの候補を60まで進めます。ただし、1は2以上の数で割り切れないので、それ以上の表示はありません。図の表は、割り算を実行した4回だけの抜粋です。

途中で外側も終了する工夫や、調べる候補を減らす方法もありますが、ここでは二重の反復を読み取るため、分かりやすい固定範囲を使っています。

もし内側を「もし」に変えて1回だけ割ると、表示は2、3、5になり、最後にn＝2が残ります。表示した因数の積は30で、60になりません。繰り返しを分岐へ変えると、同じ因数が複数ある場合を取りこぼすのです。

学習例：奇数の個数？ それとも奇数の合計？

最後に、このプログラムの表示を考えてみましょう。以下も本文用の学習例です。

goukei = 0
i を 1 から 5 まで 1 ずつ増やしながら繰り返す:
｜ もし i % 2 == 1 ならば:
⎿ ⎿ goukei = goukei + i
表示する(goukei)

更新が＋iなので、求めるのは個数ではなく1＋3＋5の合計9。

答えは9です。条件に合うのは1、3、5で、更新は「＋1」ではなく「＋i」。したがって、奇数の個数3ではなく、奇数の合計1＋3＋5＝9を求めています。

6なら偶数の2＋4を足した結果、15なら判定を無視して全部足した結果です。間違えたときは、判定を読み違えたのか、更新を読み違えたのかを分けて見直せます。

まとめ：今回の3題を、4つの観点で整理する

ユウキ「数える、分ける、割る。問題は違うのに、見る場所が整理できました」

Sandy「せや。何でも同じ型やと思うんやなくて、まずこの3問で、値を追う練習や」

今回の3題では、範囲の端、分岐の順序、反復の内側と外側が重要でした。答えだけでなく、どの行でどの値が変わったかを説明できると、初めて見るコードを読む手がかりになります。

ほかのテーマは情報Ⅰサバイバルの記事一覧から読めます。学んだ手順をプログラムや作品にしてみたい方は、プログラミングスクールSandboxもご覧ください。

参考資料

• 大学入試センター：試作問題「情報」の概要（PDF） — 共通テスト用プログラム表記の例示。条件分岐、反復、整数の商・余り、問題文の指示の扱い。
• Python公式：if・while・forの仕様 — 分岐の選択と反復の実行規則。検算には同等の処理を使用。
• CP-Algorithms：Integer factorization — 試し割りと、同じ因数で割り続ける考え方。本文の固定上限コードは学習用に構成。