素数とは何か(序盤は雑談です)
素数とは2以上で約数が自明なものしか持たない整数のことを言います。
ここでいう自明なものとは1と自分自身を指します。
言い方を変えると、整数nに対してn÷mが整数となるmが1とnしかないとき、nを素数といいます.
なぜ素数が大切なのか
それは正整数の集合に積という演算を与えたとき基底となるのが素数だからです.
数学を勉強した人なら基底がいかに大事か理解していることでしょう.
ちなみに演算が和であれば基底は1つで十分です(1のみですべての正整数を作れる)
(ちなみに基底の概念が整備されていなかった昔は素数というのはそこまで重要視されていなかったららしいです.こんな数あるよねーぐらいの認識だったとか)
素数の個数は?
素数の個数は無限個であるとユークリッド大先生が相当昔に証明されています。
無限という概念がなかった時代に「素数の個数がある数であるとするとそれよりも多く素数が存在する」という言葉で書き記していらっしゃいます。今では無限大という便利な概念が整備されていますが、それがなかった時代にここまで正確に無限大の概念を直感的に理解していたユークリッド先生って何者なんでしょうね。
素数の分布について
素数の全体の個数は無限個であるということは分かりました。
しかし1~nまでの数に素数はどのくらいあるんだろう？という疑問は相当難しい問題で解決したのは1896年です。(いまでは初等的な照明が存在しますがあくまで初等的なだけであって理解は相当難しいです)
しかもあくまで「割合」であり厳密に「いくつあるのか」という式はいまだにわかっていません(多分)
ただ具体的にnを与えたら人間でも、なんなら理解力がとてつもない犬でも数えることができます。
なぜならn以下のすべての数で実際に割って約数が自明なものしか存在しないことを確認すればいいのですから。頑張ればできます。
そして1800年代には素数表のようなものがあったらしいです。乗っている素数の上限がいくつか知りませんが。
しかし、間違いも結構あったらしくオイラー先生が1797年に1000009は素数ではないという定理?を証明しておられます。
つまり「nが素数であるかどうかは頑張れば理論上計算できるがまあ間違える」わけですよ。
ならどうすればよいのかコンピュータで代わりに計算すればええんです。
今回はnが素数か判定するプログラムではなく1~nの間に素数がいくつあるのかを求めるプログラムを目標とします
案1.1 とにかく割ってみよう
nが素数であるとは2からn-1までの整数で割り切るものが存在しないという定義でしたね。
ならそれをプログラムで実装します
def number1(n):
cnt=1
for i in range(2,n+1):
for j in range(2,i):
if i%j==0:
break
elif i%j!=0 and j==i-1:
cnt+=1
return cnt
2の処理がうまくいかなかったのであらかじめcnt=1としましたが素直に実装するとこのような感じになると思います。
これでも人間よりは圧倒的に早いのですが、せめてオイラー先生の1000009までを爆速でやりたいわけですよ。これでは遅すぎます。
改善案を考えましょう
案1.2 奇数だけ考えよう
素数かどうかを考える際、2を除く偶数は明らかに素数ではないですよね?ならそれを除きましょう.
def number2(n):
cnt=1
for i in range(3,n+1,2):#←ここが変わっただけ
for j in range(2,i):
if i%j==0:
break
elif i%j!=0 and j==i-1:
cnt+=1
return cnt
これで奇数だけを考えればいいことになりました！単純に計算の数が半分になりましたね!
ただここでもう一つ......
割られる数が奇数だけなら割る数も奇数だけでええんじゃね？......
案1.3 さらに奇数を
def number3(n):
cnt=2#変更点
for i in range(3,n+1,2):
for j in range(3,i,2):#変更点
if i%j==0:
break
elif i%j!=0 and j==i-2:#変更点
cnt+=1
return cnt
これで2を除いて割る数、割られる数をすべて奇数にできました！単純に計算回数が0.25倍です！
ただ、まだ遅い。DI〇様に怒られます。
無駄がないのか考えてみましょう
案2.1 素数で割ろう!
例えばnが5で割れなかったのに25で割れるのでしょうか？答えはNoです。
n÷25=整数なら
n÷5=5*整数になるでしょう。
つまり3で割れなかったのに9で割ったり3と5で割れなかったのに15で割るとか無駄の極みなんですね。
つまり割る数は素数のみで良いのです
しかし素数を求めたいのに素数のリストを使ったりしたら意味がないので、自分で素数のリストを作りましょう
まず定義の再確認
nが素数とは2~n-1までの数で割って整数になるのが存在しないと考えていましたが
nが素数とはn未満の素数のどれでも割れないと考えましょう！
定義としてはどっちも同じですがプログラムで書くと大きく変わりますね！
さっきの割られる数は奇数だけでよいという考えも混ぜてプログラムを書くと
def number4(n):
li=[2]
for i in range(3,n+1,2):
for j in li:
if i%j==0:
break
elif i%j!=0 and j==li[-1]:
li.append(i)
return len(li)
とでもなると思います！最初に比べると相当相当早くなりました！
ただまだ明らかな無駄があります。
案2.2 範囲で分けよう
n÷素数が整数かどうかのチェックを今行っているわけですね。
この「整数」の最小値って何でしょう？......
2ですよね？
つまりnが100とかだとすると53とかで割る必要ないですよね……？
だって明らかに100÷53は2より小さいので。
ならこれを使えばさらに無駄を省けますね
def number5(n):
li=[2]
for i in range(3,n+1,2):
for j in li:
if i%j==0:
break
elif i%j!=0 and 2*j>i:#変更点
li.append(i)
break #変更点
return len(li)
でもまだ範囲を減らせます！
案2.3 数の性質を考えよう
nが√n以下のすべての素数で割れなかったとします(このすべてって仮定はとても大事です)
この時nが√nより大きい素数で割れますか？
実はありえません。
n÷m(√nより大きい素数)=k(整数)だったとすると
n÷k=mが成立しますね?
でも√の性質考えると
m>kです
(なぜならm<kだとするとk=m+aと書くことができ
n=m*(m+a)=m^2+m*aとなりイコールがバグるから)
先ほど√n未満の素数すべてで割れないと仮定したのにそのようなkで割れてしますことになるんですよ。
案2.2は1~n÷2までの素数という範囲で考えればよいとしましたが
実は1~√n未満の素数で良かったんですね！
ならこれを実装しましょう
def number6(n):
li=[2,3]
cnt=2
for i in range(5,n+1,2):
for j in li:
if i%j==0:
break
elif i%j!=0 and j**2>=i:#変更点
cnt+=1
li.append(i)
break
return cnt
これは相当早いです。
遊び程度であればこれで十分でしょうし、これさえあれば素数の個数という知識だけはオイラー先生に勝つこともできます(多分)
ではあとちょっとだけ高速化を狙いましょう
案3.1 篩にかける
僕の中学の時の数学の教科書には載っていたのですがエラトステネスの篩という素数を求める方法があります
まず2,3,4,5,6,...,nと数字を書きます
1.先頭にあるものに〇をつける
②,3,4,5,6,...,n
2.今〇をつけた数字の倍数を全部消す
②, 3,5,7,9,11,...,n
3.〇を無視して先頭の数字に〇をつける
②,③,5,7,9,11,...,n
4.今〇をつけた数字の倍数を消す
......というのを繰り返すと〇がついている数字がn以下の素数であるというアルゴリズムですね！
これをプログラムで実装しよう！という考えです
素直に書いたら大体以下のようになるのかなあと思います
def number7(n):
li=[int(x) for x in range(2,n+1)]
pri=[]
for i in range(n):
pri.append(li[0])
li=[int(x) for x in li if x%pri[-1]!=0]
if len(li)==0:
break
return len(pri)
しかし、これは結構遅いです。
ただ上で考えたことがそのまま活きてきます!
まず数字を書くという部分に該当する
li=[int(x) for x in range(2,n+1)]
の部分。偶数は最初に消えることわかっているんだから最初から書かなくていいですね。
こうしましょう
def number8(n):
li=[int(x) for x in range(3,n+1,2)]#変更点
pri=[2]#変更点
for i in range(n):
pri.append(li[0])
li=[int(x) for x in li if x%pri[-1]!=0]
if len(li)==0:
break
return len(pri)
ただこれでも結構遅いんです。
なぜなら
後半になると篩がすでに終わっているんですよ。
n=100で考えますね
3,5,7の倍数を消していきます。
実はこの時点で100以下の素数がすべて出ています
さっきの話と一緒ですね.√n未満の素数で十分なんです
なのにコンピュータは最後の素数97まで篩のチェックをして、リストにあるすべての数字が11の倍数かな,13の倍数かな,17の倍数かな,...,97の倍数かな？と確かめるんですよ。
この無駄な処理で遅くなっています。
だから√n未満で十分という処理を追加してあげましょう
def number9(n):
li=[int(x) for x in range(3,n+1,2)]
pri=[2]
for i in range(n):
if pri[-1]**2>n: #ここら辺が変更点
pri+=li
break
else:
pri.append(li[0])
li=[int(x) for x in li if x%pri[-1]!=0]
if len(li)==0:
break
return len(pri)
これで結構早くなりました！前のプログラムと競ってみましょう!
速度チェック
今回は number6とnumber9のみで速さを計測していきます!
オイラー先生の1000009をリスペクトしてn=1,000,000として10回計算をし平均を出してみます
number6 :平均タイム5.729981923103333
number9 :平均タイム3.960706377029419
篩が速いですね(タイムはpcスペックなどで変動するのであくまで参考程度に)
終わり
基本的な素数の個数の求め方をまとめてみました。
参考になると嬉しいです><
また別件ですが、最近プログラムの勉強がテスト勉強という大学の一大行事()のためできていませんでした。
その分この夏休みの期間にスキルアップできるよう精進したいと考えているのでご指導ご鞭撻よろしくお願いします！