案内ページに書いた通り, ここでは算数ネタをもとにしてプログラミングと数学を勉強する糸口を紹介します. プログラミングいろいろな視点や切り口があります.
プログラムでも数学の証明や計算でも, 少しずつ改善する様子はなかなか見せてもらえません. しかし最終的には自分自身でプログラム・証明・計算をブラッシュアップする必要があります. ここでは実際にその様子を見せます. つまりはじめに見せるプログラムや考察には甘いところがたくさんあります. そのつもりで議論を追いかけてください.
素数は「1と自分自身以外では割り切れない,
1より大きい整数」です.
ここでは与えられた整数が実際に素数かどうかを判定します.
ある整数が素数かどうか判定するには定義を確認する以外にありません. 数学, とりわけ大学の数学に苦手意識を持つ人の多くは, この「定義を大事にし, 定義に基づいて考える」習慣が身についていません. ここでいう「大学の数学」には統計学のような実用的な数学も含みます. 現実問題として, 少なくとも私の観測範囲では小中高とそうした教育を受ける機会がないか, そうした機会があったとしても児童・生徒がそれを受け止めきれません. 実際, 恐ろしくストイックな立場での数学で, 習得するのも大変なのです.
一方, 数学の議論をプログラムに落とし込むときに使えるのは, まさにこの定義です. むしろ定義以外に道具がありません. この事情を逆手にとってプログラミングを通じた数学学習を提案するのがこのコンテンツの目的の一つです.
数学に関するプログラムを書くとき, まず真っ先に考えるべきは定義に基づいて考え, 定義の通りに実装することです. 急がば回れではありませんが, 数学学習にとって, 実はプログラム実装は直接的なご利益があります. 自分が教師としてプログラムに数学を教えていると言ってもいいでしょう. 実際この視点で物理・数学教育にプログラミングを導入している人もいるほどです.
ここでもこの視点を強く意識してコンテンツを作っています.
1は素数に含まない¶こういうところでつまづく人もいるでしょうから,
念のため補足しておきます.
もし1を素数にすると素因数分解の一意性の言明が汚くなるからです.
ひどく感覚的で「合理的」には見えないかもしれません.
言明が汚くなるとどう困るかを説明します.
端的に言えばそれを説明する文章や表現が複雑になります.
つまり文章が読みにくく・分かりにくくなります.
いろいろな人がいろいろ考えた結果,
不必要な複雑さを削ってわかりやすくした結果が「1は素数としない」です.
数学に限らず「こう仮定しておくと先々で便利だから」と先手を打たれた議論はよくあります. そして実際に先々に進んで味わい尽くさないと便利さが見えてきません. わからないことに出会ったら立ち止まってじっくり考えるのも大事ですが, いったんわからないことだけ覚えておき, 先に進んでみるのも同じくらい大事です.
話が横道に逸れてしまいましたが, 大事なことなのであえてここでも議論しました. 本筋に戻って, まずは文章のレベルで素数判定しましょう. 大きな数だと大変なので小さい数で確認します.
7は2で割り切れない.7は3で割り切れない.7は4で割り切れない.7は5で割り切れない.7は6で割り切れない.これで7が素数ではないことが確認できました.
ここですでに大事な視点が出ています.
まず1で割るのを省略しています.
絶対に1で割れるので一々確認する必要がないからです.
同じように7でも絶対に割れるためこれも確認不要です.
もう一つついでに言えば8以上も確認不要です.
今度は絶対に割れないからです.
つまり与えられた3以上の整数Nが素数かどうか調べるには,
2からN-1までの全ての数で割れるかどうか調べれば十分です.
定義に照らせば2は素数とすぐにわかるので,
あえて3以上と注意をつけました.
3以上の整数N, 「2からN-1までの全ての数で割れるかどうか」¶ここで既に面倒なことを言っています.
「2からN-1までの全ての数で割れるかどうか」はN=2では意味を持ちません.
つまり「2から1までの全ての数で割れるかどうか」は意味を持ちません.
暗黙のうちに「2,3,4,5,...」と増加列を仮定しているからです.
言語によってはプログラムの中ではっきりと加算処理を入れる必要があるため,
増えるか減るかは大事な要素です.
そして減らす列を考えることもあります.
そして数によって考える列が増加列か減少列か変わるとなると面倒です.
そこで減少列だけ考えればよくするため上のような書き方にしました.
「そんな面倒なことを考えるくらいなら2からNまで確認すればいいのでは?」と思うかもしれません.
しかしプログラムの書き方によってはNが入るかどうかは大きな問題になります.
いまの時点では説明もしづらいため,
あとで実際にプログラムを書いてどこが問題になるかコメントします.
気になったら細かく何度も確認しましょう. 実際にこれから何度もしつこく確認します. 特にプログラムは何度でも簡単に実行できます. 気になることがあれば本やネットで調べるのも大事ですが, 調べたことを手元ですぐに実行してみましょう.
そろそろ文章ばかりで飽きているでしょう. いったんプログラムを書きます. もちろんいろいろな書き方があります. ここでは次のように書いてみましょう.
b = False
b = (7%2 == 0) or b
b = (7%3 == 0) or b
b = (7%4 == 0) or b
b = (7%5 == 0) or b
b = (7%6 == 0) or b
print(b)
False
都合によって「合成数ならTrue」,
「素数ならFalse」が出るようにしています.
見てわかるようにFalseと出ました.
つまり7は素数です.
プログラムとして何をしたのか解説しましょう.
いまN=7で,
2からN-1=6まで全ての数で割り切れないかチェックする必要があります.
はじめに論理値としてb=Falseを設定しました.
そのあと7%2 == 0を計算し,
もとのbとの論理和(いわゆるまたは)を取り,
bの値を更新します.
これを2から6まで続けて最後にTrueになっていれば素数ではありません.
どこかで割れていればそこでTrueになり,
以降orによって値はずっとTrueです.
最後にprint(b)でbの値を出力して確認します.
print(7%1)
0
割り切れるので当然結果は0です.
以下, それぞれ各整数で7を割った余りが出力されるか確認できます.
print(7%2)
1
7を2で割ったあまりは1なので1が出力されます.
print(7%3)
1
7を3で割ったあまりは1なので1が出力されます.
print(7%4)
3
ようやく1以外の値が出てきました.
7を4で割ったあまりは3なので3が出力されます.
print(7%5)
2
7を5で割ったあまりは2なので2が出力されます.
print(7%6)
1
7を6で割ったあまりは1なので1が出力されます.
print(7%7)
0
当然あまりは0です.
print(7%8)
print(7%9)
print(7%10)
print(7%11)
7 7 7 7
どれもあまりは7です.
それぞれ適切な値が出ているか確認してください.
ここまで来て誰もが思うはずです.
いちいちこんなにたくさん書いていられるか.
もちろん簡潔に書く方法があります.
for文を使います.
ここでは「習うより慣れろ」の精神で細かい説明をせずに使います.
for i in range(1, 10):
print(f"7%{i} = {7%i}")
7%1 = 0 7%2 = 1 7%3 = 1 7%4 = 3 7%5 = 2 7%6 = 1 7%7 = 0 7%8 = 7 7%9 = 7
追加の要素としてrange(1, 10)とprint()中のf"{i}"も出てきてしまいました.
前者は大事なのでこれから説明します.
ここで後者は説明しません.
「フォーマット済み文字列」などで検索して調べてみてください.
for¶上のfor文が生成する処理はよくforループと呼ばれます.
一番基本的なくり返し処理です.
実はPythonに限らずいろいろな言語でforでくり返し処理を書きます.
これ以外にもいろいろな言語での共通処理・共通の関数名があり, 同じ名前ではなくても類似の処理・関数があります. Pythonの読み書きだけができればいいわけでもないので, 他言語・多言語学習時には気にかけてみてください.
range()関数¶まず何がしたいかを確認し, それをPythonでどう表すかを考えます.
今は算術演算子%の挙動を調べるのが目的です.
一つ二つで十分な場合もありますが,
たくさんのケースを調べたくなる場合もあります.
たくさんのケースとしてたくさんの数を用意するのがrange()関数です.
(ちなみにプログラミングでは関数はよくf()と括弧つきで書きます.)
range()の挙動自体もいろいろ調べてみましょう.
for i in range(5):
print(i)
0 1 2 3 4
見てすぐわかるように0からはじまって4で終わります.
何故かはともかく少なくともPythonではこうなっています.
他のrange()の挙動や厳密な意味・定義は深く説明しません.
いくつか基本的なところだけ挙動を具体的に示して先に進みます.
次にrange(0,5)を確認します.
これはrange(5)と同じで,
「0からはじめて5より小さい整数を連続で作る」です.
for i in range(0,5):
print(i)
0 1 2 3 4
次にrange(2,5)を確認します.
今度は「2からはじめて5より小さい整数を連続で作る」です.
for i in range(2, 5):
print(i)
2 3 4
次にrange(0,10,2)を確認します.
今度は「0から10より小さい整数を2刻みで作る」です.
for i in range(0, 10, 2):
print(i)
0 2 4 6 8
実は負の方にも進められます.
例えばrange(10,0,-3)は
今度は「10からはじめて0より大きい整数を-3刻みで作る」です.
for i in range(10, 0, -3):
print(i)
10 7 4 1
range()関数は引数の数で挙動が変わります.
わからなくなったらマニュアルやリファレンスで調べるのも大事ですが,
実際に実行して確認するのも大事です.
ネット上にある情報はバージョンが古いこともあれば,
あなたが実行しているバージョンよりも新しいこともあります.
どちらもあなたがプログラムを実行したときと違う結果になる場合があります.
本の版と同じようなもので,
プログラムにバージョン込みで情報を調べる必要があるのです.
何にせよ実行して得られた結果が最優先です. 実行してどうなるか, 常に細かく確認する癖をつけてください.
4での確認¶そろそろ素数判定に戻りましょう.
4は2の倍数なので明らかに素数ではありません.
プログラムを書いて確認します.
for i in range(2, 4):
print(f"4%{i} = {4%i}")
4%2 = 0 4%3 = 1
4%2=0があるため素数ではありません.
一番最初に確認した真偽値判定もfor文で試してみましょう.
b = False
for i in range(2, 4):
b = (4 % i == 0) or b
print(f"b for 4%{i}: {b}")
b for 4%2: True b for 4%3: True
一度でもTrueが出たらずっとTrueになるようにしています.
紛らわしいですが,
「Trueだったら合成数」としているため4は合成数です.
4%2=0があるために最終結果もTrue判定です.
6での確認¶今度は4を6に変えます.
b = False
for i in range(2, 6):
b = 6 % i == 0 or b
print(f"b for 6%{i}: {b}")
b for 6%2: True b for 6%3: True b for 6%4: True b for 6%5: True
これも合成数としてTrue判定されました.
上のプログラムでは4を6に変えるときにrangeの中,
bを更新するところ,
printの中と三個所変える必要がありました.
実際, 私自身, このコンテンツを作る途中で何度か更新漏れを起こしてしまい,
「何でうまくいかないのか?」と混乱しました.
アホと言えばアホなのですが, プログラミングに慣れていてもやってしまいがちなミスでもあります.
こうしたミスをなくすためによくやる処方箋の一つが「定数の抽象化」などと呼ばれる手法です.
ここでは単に変数を使うだけです.
b = False
N = 6
for i in range(2, N):
b = (N % i == 0) or b
print(f"b for {N}%{i}: {b}")
b for 6%2: True b for 6%3: True b for 6%4: True b for 6%5: True
単純に6をNに変えました.
これで最初のNだけ変えれば全部変わります.
9での確認¶b = False
N = 9
for i in range(2, N):
b = N % i == 0 or b
print(f"b for {N}%{i}: {b}")
b for 9%2: False b for 9%3: True b for 9%4: True b for 9%5: True b for 9%6: True b for 9%7: True b for 9%8: True
ここまでは全て偶数だったので2の余りを見た時点でTrueが出てきました.
今度は偶数ではないのできちんと2の時点ではまだFalse,
3からようやくTrueです.
上のコード片で変えるべきはNだけで,
いちいちループの全体を書くのは面倒です.
この手続き全体をまとめてしまいましょう.
ここでプログラミングの意味での関数が出てきます.
何はともあれ関数を書いて実行します.
def is_composite(n):
print(f"---CHECK FOR {n}---")
b = False
for i in range(2, n):
b = n % i == 0 or b
print(f"b for {n}%{i}: {b}")
if b:
print(f"{n} is not a prime!")
else:
print(f"{n} is a prime!")
確認用の出力をいくつか追加しています.
6が合成数と判定されるか(Trueになるか)確認しましょう.
is_composite(6)
---CHECK FOR 6--- b for 6%2: True b for 6%3: True b for 6%4: True b for 6%5: True 6 is not a prime!
次に関数の引数を変えるだけで他の数もチェックできるか確認します.
4の再確認¶is_composite(4)
---CHECK FOR 4--- b for 4%2: True b for 4%3: True 4 is not a prime!
9の再確認¶is_composite(9)
---CHECK FOR 9--- b for 9%2: False b for 9%3: True b for 9%4: True b for 9%5: True b for 9%6: True b for 9%7: True b for 9%8: True 9 is not a prime!
11の確認¶is_composite(11)
---CHECK FOR 11--- b for 11%2: False b for 11%3: False b for 11%4: False b for 11%5: False b for 11%6: False b for 11%7: False b for 11%8: False b for 11%9: False b for 11%10: False 11 is a prime!
念のため簡単に注意します. プログラミングでの関数は数学の関数とは必ずしも一致しません. 数学での関数はある入力に対して出力は常に同じです. しかしプログラミングの「関数」は同じ入力に関して出力が変わることがあります. プログラミングでは処理をまとめただけのモノ, つまり手続きも「関数」として扱うからです. 手続きと関数を律儀にわけているプログラミング言語もあります. ここではPythonの流儀に準じた言葉遣いにします. 以後詳しくは触れません.
一応素数判定プログラムはできました. しかしいくつか実用上の問題があります. 次回簡単に何が問題かを紹介し, 解決策を紹介します. プログラミング利用の限界に関する話題もいくつか紹介します.
実用上という言葉が気になっている人もいるでしょう. あなたもそうかもしれません. ごく簡単に素数の理論・計算の応用について紹介します.
素数判定は素因数分解の基礎です. そして実は現代的な暗号の理論は素因数分解に基づいていて, 応用上も非常に重要です. オンラインショッピングなどでの決済情報の安全な通信のために暗号化は本質的に重要です. 少なくとも私の講座を受講するくらいの人で, オンラインショッピングを全く使ったことがない人はまずいないでしょう. 素因数分解を基礎にした暗号の理論やプログラミング・システムは日常のありとあらゆる場面で応用されているのです.
現代的によく使われているRSA暗号では1000桁を越える素数が出てきます. 何も考えず定義に基づいて素数判定しようとすると, 大まかに見て$10^{1000}$秒程度かかります. そしていろいろな工夫をしても凄まじい時間がかかる事実が暗号の安全性を支えています. 量子コンピューターによる暗号解読といった話題もあります. 数学的にも難しくなりすぎるためここではこれ以上紹介できませんが, 素数の数学・プログラミングは最先端の研究にもつながる程のテーマなのです.