56547511は素数でしょうか？
目次
前回のフィボナッチ数表示プログラムを改良
前回のフィボナッチ数表示プログラムはPython本家本元ウェブサイトに紹介されているものでした。
関数fib(n)はnより小さいフィボナッチ数を表示します。
初項、第0項と第1項をそれぞれ0と1として、0+1=1を第2項、1+1=2を第2項、1+2=3を第4項と数列を生成するアルゴリズムは
第n+2項＝第n項＋第n+1項
の関係式で表されます。これが次のコードです。
a, b = 0, 1
a, b = b, a+b
そこで次に第n項まで表示するプログラムを考えてみます。
プログラム：fib2.ipynb
>>> def fib(n):
>>> a, b = 0, 1
>>> for t in range(0, n+1):
>>> print(f'第{t}項\t {a}')
>>> a, b = b, a+b
>>> print()
>>> fib(100)
Google Colaboratory（グーグルコラボラトリー）をグーグルアカウントで起動します。ノートブックを新規作成して、上のコードをコピーします。
ファイルネームをfib2.ipynbとして保存します。このファイルはグーグルドライブのMy Driveに保存されます。
コードを1行目から見ていきます。
def fib(n):
関数fib(n)の定義です。コロン:を忘れないように。以下のコードは行頭インデントを行います。
a, b = 0, 1
初項の代入です。第0講、第1項をそれぞれa、bとして0と1を代入します。
for t in range(0, n+1):
print(f'第{t}項\t {a}')
a, b = b, a+b
range()関数は連続した整数を生成します。
range(0, n+1)により0からnまでの整数を生成します。
一番シンプルなrange(n)は0からn-1までのn個の整数を生成します。range(a, b)はaからb-1までの整数を生成します。
ここでは第0項から第n項までのフィボナッチ数を表示させるためにrange(0, n+1)とします。もちろん、range(n+1)としても同じです。
生成された値を変数tに0,1,2,…,nの順に代入していくのがfor文です。for文も最後にコロン:が必要です。
以下のコードは行頭インデントします。
print(f'第{t}項\t {a}')
a, b = b, a+b
インデントされたこの2行が、tが0からnまでの間繰り返し処理されます。
print(f'第{t}項\t {a}')
Python3.6以降では f文字列(f-string)という表示方法が使用可能です。
print文ではよく使う便利なコードです。print(f'')とすることで''の中に変数を渡して、その中身を表示させることができます。
ここでは第t項を表す変数tの数値を用いて第5項と表示させます。それが第{t}項という使い方です。
\tは水平タブ（tab）を表します。変数aは第t項を表します。そこで{a}とします。
タブのおかげで変数aの先頭が揃います。
a, b = b, a+b
これがフィボナッチ数のメイン・アルゴリズムです。
第t+2項＝第t項＋第t+1項
第t項a、第t+1項bに対して、変数tが1つ大きくなると第t+1項をb、第t+2項をa+b、すなわち第t項＋第t+1項とするということです。
print()
これで関数fib(n)の定義を終わりにします。実はこの1行はなくても同じように動いてくれます。
fib(100)
第100項まで表示します。f(1000)としても、あっという間に第1000項まで表示されます。
素数判定プログラム
さっそく次のコードをコピーして、ファイル名をprime1.ipynbとして保存します。
プログラム：prime1.ipynb
>>> n = int(input('素数判定したい3以上の整数nを入れてね。n='))
>>> for k in range(2,n):
>>> if n % k == 0:
>>> print(f'{n} は {k} を約数にもつので合成数、素数ではありません！')
>>> break
>>> else:
>>> print(f'{n} は素数！')
実行させると、nの値をたずねられます。
12を代入してみると、12は素数ではありません、と返ってきます。645267を代入してみると、645267は素数です、と返ってきます。
このコードはフィボナッチ数のものと同じ行数です。for文、range()関数のところは同じです。
if n % k == 0:
print(f'{n} は {k} を約数にもつので合成数、素数ではありません！')
break
n % kはnをkで割った余りです。これが0に等しいならば、次のインデントされた2行を実行します。nをkで割った余りが0ということはkはnの約数ということです。
2以上のkが約数であると、その時点でnは素数ではないと判定されます。次のbreakによってプログラムは終了します。
else:
print(f'{n} は素数！')
range(2,n)によってkは2からn-1まで生成されます。そのすべてのkがnの約数でないとelse:が実行されます。nの約数が1とnだけとなるのでnは素数と判定されます。
単純なアルゴリズムですが、CPUパワーが大きいPCにとって大きなnに対しても判定が可能です。
56547511の素数判定にどれほどの時間がかかるか、試してみてください。
