#まえがき
みなさん競技プログラミングをはじめて、割と最初のほうに自分専用ライブラリづくりをされるかなと思います。
僕もしました。昨日。
そしたらですね、素晴らしい記事を見つけたわけです。
Pythonで競技プログラミング 〜基本的なアルゴリズム 〜
これがあればいろんな数学的に必要な概念をコードにするときにめっちゃ楽やん！
というか、そもそも数学知識が無いと剰余が同じ数字出すだけでもTLE連発することになりますから（経験談）、どのみち考えても大してうまくいくわけないしこうやってちゃんとしてそうなコードを写経するのは遅かれ早かれ必要になるんですよね。
で、さすがに今後コードを使いまわせるとはいえ、この内容を丸コピするだけじゃあなんか嫌だなと思ってコードの内容を読んでいくわけですけど、ちょくちょく数学的知識が必要なのか「なんでこうなるかわからん！」って部分が出てきたんですよ。
そんなわけで、教養のない数学糞雑魚系文系AtCoderの僕には考えたってわからないので、またほうぼう頼りながら祝日をつかって素数関連のコードを追ってみました。（それ以外はまだちゃんと追ってないです）
まぁ使うだけならやっぱりいらない解説だと思うんですけど、ロジックを理解しないコードをコピペして終わらせるなって社畜ちゃんも言ってるから...後輩ちゃんもがんばってるから...
新人プログラマの女の子が独り立ちをする話👩💻 1/6 pic.twitter.com/M39qWhNQjG
— ビタワン🐕社畜ちゃん⑦巻2/27発売予定☃️ (@vitaone_) December 1, 2019
今回も後輩ちゃんでも理解出来るくらい分解して一から解説するぞー
#解説
##Nが素数かどうか判定
まずはある値が素数であるかどうか判定するコードです。
素数とは何かという話も含めて解説します。（だって俺はちゃんと知らなかったし）
#前提として、約数という概念を知っておきましょう。
#約数とは、ある数を割り切れるすべての数字を指します。 24なら(1,2,3,4,6,8,12,24)
#さて、数字には素数と合成数という概念があります。
#素数とは1とその数自身以外に約数をもたない孤独な数のことです。（0,1は対象外）
#心が乱されているときは、素数を数えるとよいというのは有名な話ですね。
#つぎに、合成数とは素数ではないもの、自然数（自然数とは「正の整数」で、
#「2」「30」「400」などのこと）で、1とその数自身以外の約数を持つ数をいいます。
#では、素数をもとめるために合成数の法則を知りましょう。
#まず、n が合成数なら必ず √n(2乗するとnになる数) 以下の素因数(自然数の約数になる素数)を持つという法則があります。
#そのため、nが素数かどうかは √n 以下の素数たちで割り算すればよいということになります。
#（こんなんで理解できるやつは数学糞雑魚系文系AtCoder名乗らせません）
#例えとして、簡単な素数として2,3,5,7...という並びがあります。
#√n（二乗したらnになる数）以下の素因数をもつということは、
#ある素数を2乗した数よりnが小さいかを確認することでどの素数まで見ればいいのかがわかります。
#例えば 31 が素数かどうか判定するときに 5^2 < 31 < 7^2 なので 5 以下の素数で割り切れないことを証明すればOKです。
#つまり「2 の倍数でない，3 の倍数でない，5 の倍数でない」ことを確認すればOKです。
#これがすべて真であるとき、「n が合成数なら必ず √n(2乗するとnになる数) 以下の素因数(自然数の約数になる素数)を持つ」という法則から、「素因数をもたないということは合成数ではない」が成り立ち、nが素数であることを証明できます。
#Q.E.D. 証明終了（いいたいだけ）
#Nに対して存在しうる素数の最大値までを探索するやりかたです。
#つまり、n=31なら合成数である場合√31以下の素数を持つので、
#2~5までのすべての数字で割り切れるかどうかだけ確認するということですね。
#この範囲には素数以外も含まれますが、素数かどうかの判定なら1とn以外で割り切れないので、
#どの数でも割り切れないはずですね！
def is_prime(n):
#2~(N+1)までをiに代入してみていく
#これは素数が2から始まり、2からnまでだとnの1つ前までの値しかiに代入できないから。
for i in range(2, n + 1):
#前述の例でみると、i^2したときにn以下というのは、n=31のとき i=5なら25で無視
#i=6なら36でbreakということである。
if i * i > n:
break
#そもそもnを割り切れる数字が1とn以外にあったら素数ではない
#そのため、iが素数であるかどうかを判定する必要がないので
#単純に割り切れるかどうかだけを見ればよい。
if n % i == 0:
return False
#すべて見終わった後にnが1でなければ素数である（1は素数ではない）
return n > 1
##N以下の素数の列挙（エラトステネスのふるい）
素数列挙の必殺奥義です。
注意点として、listによるフラグ管理で素数かそうでないかを管理してください。
決してリストの中の要素を消したり追加したりしないでください。
フラグ管理でおわれるからこそ速度が速いのであって、そんなことをすると愚直に計算する場合と似たような速度になります。
参考
https://engineering.linecorp.com/ja/blog/algorithm-description-for-coding-tests/
https://zenn.dev/noodlewhale/articles/c5b069237ee72a
#次はNという数の中に含まれる素数をすべて列強する方法です。
#愚直に計算する場合
#先ほどの「Nが素数かどうか判定」のコードを繰り返し続けるだけす。
#一つ一つの数字に対してあの処理を繰り返すので、ループ回数がもりもり増えて遅くなります。
#なので、今回は紀元前より伝わる神器、「エラトステネスの篩」を抜きましょう。
#エラトステネスのふるい
#最初に、2 から n までの整数を並べる。
#素数は2,3,5,7...と序盤から並んでいるので、ここから一つずつ取り出して、
#その倍数は全部素数じゃないのとしてふるい落としていくのがエラトステネスのふるい。
#2~nまでの整数でまだふるい落とされていない一番小さい数をpとして取り出す。
#p 以外の p の倍数を全て消す。
#次に小さくふるい落とされていない数字を取り出し、上記を繰り返す。
#p が √n を越えたら終了。最終的に生き残ったものが素数。
#(頭が良すぎる)
#n=30 で実験してみます。
#・生き残っている素数候補の集合を A とおく。
#A={2,3⋯,30}
#・ p=2 の倍数をふるい落とす
#A={2,3,5,7,9,11,13,15,17,19,21,23,25,27,29}
#・ p=3 の倍数をふるい落とす
#A={2,3,5,7,11,13,17,19,23,25,29}
#・ p=5 の倍数をふるい落とす
#A={2,3,5,7,11,13,17,19,23,29}
#・次は p=7 となるが √30 より大きいので終了。 30 以下の素数が高速に求まった！
#なぜ√n以下の素数だけ見ればよいのか（これがちょーあたまいいポイントです）
#まずこのロジックの目的はn以下の合成数を消すことです。（そしたら素数が残りますね）
#合成数とはa×b=cとなる数字ですね。
#この数字を見た時、aとbがどういう関係にあるかということを考えてみてください。
#もしaが√nより大きいのだとしたら、bは√nより小さい数になります。
#なぜなら、√nはi^2=nになる数字のことなので、aがiより大きいならそれより大きい数と
#乗算すると当然nより大きい数字になってしまうからです。
#だからn以下の合成数(a×b)において、aもしくはbには必ず√n以下の数字が含まれています。
#その場合、n以下の合成数には必ず上記例の
#a or bどちらかに√n以下の数字が入っている = √n以下の数字の倍数である
#ことが言えるため、√n以下の数字の倍数を消すだけですべてのn以下の合成数を消すことができます。
#Q.E.D. 証明終了（いいたいだけ）
#エラトステネスのふるい
def sieve(n):
#すべての要素がtrueで0~n+1までのインデックスをもつリストを作成。N=30だったら0~30まで
#最後に対応する数字の要素がtrueだったらそれは素数であるとする。
is_prime = [True for _ in range(n+1)]
#0を検証する意味はないので、
#インデックス0は「1」に当たると考え、1は素数ではないのでFlaseに変更。
#つまり、このlistのインデックス番号+1を表すことを覚えておくこと。
is_prime[0] = False
#2からnまでのrangeは2~30までなので、i=2~29まで回るので、iの最大値をnにするために+1
for i in range(2, n+1):
#iは2から始まるので-1してインデックス1（数字としては「2」）から確認 trueだったらその倍数をふるいにかけていく。
if is_prime[i-1]:
#i=2だったらj=4 i=3なら6といったiの倍の数値をjの開始値として
#その倍数の要素をfalseにしていく。
j = 2 * i
#n以下の合成数だけみればいいので、jがn以下の間だけループ
while j <= n:
#iが2なら数字としては4,6,8....と2を使った合成数をnまでfalseにし続け、
#つぎはi=3...5...と繰り返していく。
is_prime[j-1] = False
#jをiずつ加算することで、常にiの倍数を参照できる。
j += i
#ここまでの処理がすべて終われば、list内のtrueとなっているものが素数だけになっている。
#最後に、listから素数の数字を再現して返り値に渡す。
#n=30なら1~31までforを回す。is_primeはインデックスとしては
#0~30まで生成されているので単純に1空まわすとオーバーするが、
#is_prime[i-1]を参照することでカバーしている。
#nを1加算しているのは、is_primeのインデックスに対応する数字が+1だから、
#tableに突っ込む値をiであわせるために加算している
#対応するインデックスの要素がtrueだったら素因数としてリストに突っ込む
table = [ i for i in range(1, n+1) if is_prime[i-1]]
return is_prime, table
##素因数分解
ここまで来た皆さんはもう素数をある程度理解したと思うので、きっと簡単です
あのころめっちゃ苦労したりしなかったりした素因数分解も、ここまできたらかわいいものです。
#nを素因数分解したリストを返すロジックです。
#素因数分解とは、
#「自然数（自然数とは「正の整数」で、「2」「30」など）を素数の掛け算で表す」ことです。
#例[2,2,2,3,5] = 120 素因数分解サイトhttps://keisan.casio.jp/exec/system/1161228771
def prime_decomposition(n):
#1は素数ではないので見る必要はない
i = 2
table = []
#ここから素因数分解のロジックになるのですが、i * i <= nの範囲でだけうごき、
#nをiで割ってはテーブルに突っ込んでいき、i * i > nとなったタイミングでnがまだ残っていれば
#それを最後の素数として取り出して終わりという処理を行っております。
#こちらについても解説しましょう。
#i*i<=nの素因数をすべて取り出せば、それ以上の素因数は最高でも１つしかのこらないので、
#のこってたら素因数リストに追加するし、1だったらそのまんまってやれば全部の素因数出せます。
#なぜそうなるのかというと、i*i>nの素因数が複数、p,qと存在していた場合、
#それはp*q > nとなるが、p,qはnの約数だからp*q<nにならないといけないため、
#矛盾するからです。
#結果、i*i>nの素因数は複数存在しないということがわかるため、
#ここまでの素数を全部みてまだ数字が残ってたらそれは最後の素数であることが証明されます。
#Q.E.D. 証明終了（いいたいだけ）
while i * i <= n:
#素因数分解の場合、20は[2,2,5]となるように、ひたすら素数になるまで分解していきます。
#nをiで割り切れるとき、それを同じ数で割りまくっていけば
#iがいくつあるかを見ることができます。
#2で割りまくって、3で割りまくって...とnへの割り算を下から順に繰り返していくので、
#2や3で割り切れる合成数の約数は出力されません。
while n % i == 0:
#次にnの割り算をする場合、抜き出した素数分の値は引かれていないといけないので、
#直接nの数値を変更しています
#i * i > nとなったタイミングでnが2以上であれば、それは単一の素数です。
n /= i
table.append(i)
i += 1
#1は素数ではないので、nをすべてのiで割りまくった後に1より大きければ
#それが最後の素数になる。
#割り切れている場合nは1になっているので、無視。
if n > 1:
table.append(n)
return table
これらのロジックを考えた人は本当に頭がいいなぁと実感しますね。
僕にはとてもできない。（小学生並みの感想）
#ぽえむ
僕は思います。
文系に必要なのはストーリーだと。
世の中のコードには「魔法の記述」というのが存在します。
「とりあえず今は気にしなくていいです」というあれです。
あれ、スッと入ってくる人とこない人がいると思うんですけどどうですか？
だってよくわからないのに動くわけじゃないですか。
たとえるなら数字の0~9を知らないまま掛け算を始めるような不安感。
土台があいまいな状態での鉄骨わたり。
たしかに数学にはよく「これはこういう者として理解してください」「公式として暗記してください」という表現が良くされます。
実際これは効率的に結果を得るうえで正しい方法だと思います。
しかし、文系とはそういうものじゃないのです。
文系は過去が好きだし、回りくどい表現が好きだし、起承転結が欲しいのです。
数式を見たらそれがなぜ生まれて、どんなことに使われていて、なぜ自分がそれを学んで、何を得るのかまで全部聞きたいのです。
そしてそれをすべて理解したとき、はじめて「完全に理解した」というわけです。
これを理系どもは「チョットワカル」とかいうから理系と文系にはきのことたけのこより深い溝があるんです。
たとえば、直角三角形の面積を求めるとき「三角形の面積を求める公式を思い出す」だけで済む方は理系です。
文系は「公式の生い立ち」を思い出すところから始まるので、
「僕らが最初に学ぶのは正方形の面積を出す方法だ...図形の面積を求めるときは最小の正方形がいくつその中に存在するかを求めればいい。多少大きさが変わったとしても長方形なら１列を見た時に縦に何個積みあがっているかがわかれば、その列がいくつあるかで答えが出る...つまり長方形なら底辺(x)×高さ(y)で面積が求まるわけだ。しかし三角形には斜めの線が入っている...クソッ！どうすれば...!!いや、待てよ。俺はすでにこの問題を解き明かす武器をそろえているはずだ。そうか、そういうことか、直角三角形は頂点の数が少ないだけで長方形と持っている要素は変わらない。つまり、反対側に空いた頂点の部分に全く同じ形の直角三角形を組み合わせることで長方形になる！だから、長方形の面積を出した後に半分にすればそれは形はどうあれ直角三角形の面積と等しくなるはずだ！！！つまり！！！俺が導き出す答えは...底辺×高さ/2ィィィィ！！！」
こうです。（異論は認めません）
この過程で解説に入ってくるあらゆる数学的単語も分解して考えないといけないので、文系は頭の容量が足りずに数学なんかやってらんねーとなったのです。
あと、単純に頭使いたくない馬と鹿と仲良しな人も当然自動的に文系になります。
世の中には文系と理系という区別しかないので、頭使いたくない人もどちらかにグルーピングされてしまうのです。
文系が勉強しないんじゃなくて、勉強したくない人が文系にグルーピングされてるだけだってことをしっかり理解しておいてください。
文系だからって自分を卑下しないで！！
なお、当然ですが僕は馬と鹿と仲良しだった人です。
理系の皆さん（特に数学教師のみなさん）ご理解いただけましたでしょうか。
文系とはこういう生き物なのです。
頭の作りが違うのです。
数学が嫌いな文系の子に直角三角形の面積の出し方を教える際はぜひ上のような解説をしてみてください。
人気教師になれると思います。
理系のつよつよコーダー諸君は上記を頭に入れたうえで引き続き数学糞雑魚系文系AtCoderへの指導をお願いします。
#追記
理系の人からこの考え方は理系だといわれました。
ということは、この世には理系も文系もないのではないだろうか。
起承転結も因果関係も全部ロジックなんだ...すべては始まりがあって結果が出るのだ...
そうか、わかったぞ...世界の心理が、ふははは、この世にいる人間はやはり皆同じなんだ...
はは...大きな星が点いたり消えたりしている…。あはは、大きい！ 彗星かな？ いや、違う……違うな。彗星はもっと、バァーって動くもんな。暑苦しいなぁ、ここ。うーん……出られないのかな？おーい、出してくださいよ。ねぇ？