コラム 人と星とともにある数学 数学

素数判定プログラムをコーディング|Pythonで数学を学ぼう! 第4回

56547511は素数か?

前回のフィボナッチ数表示プログラムを改良

前回のフィボナッチ数表示プログラムはPython本家本元Webに紹介されているものでした。

関数fib(n)はnより小さいフィボナッチ数を表示します。

初項、第0項と第1項をそれぞれ0と1として、0+1=1を第2項、1+1=2を第3項、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の素数判定にどれほどの時間がかかるか、試してみてください。

  • この記事を書いた人
  • 最新記事

桜井進(さくらいすすむ)様

1968年山形県生まれ。 サイエンスナビゲーター®。株式会社sakurAi Science Factory 代表取締役CEO。 (略歴) 東京工業大学理学部数学科卒、同大学大学院院社会理工学研究科博士課程中退。 東京理科大学大学院非常勤講師。 理数教育研究所Rimse「算数・数学の自由研究」中央審査委員。 高校数学教科書「数学活用」(啓林館)著者。 公益財団法人 中央教育研究所 理事。 国土地理院研究評価委員会委員。 2000年にサイエンスナビゲーターを名乗り、数学の驚きと感動を伝える講演活動をスタート。東京工業大学世界文明センターフェローを経て現在に至る。 子どもから大人までを対象とした講演会は年間70回以上。 全国で反響を呼び、テレビ・新聞・雑誌など様々なメディアに出演。 著書に『感動する!数学』『わくわく数の世界の大冒険』『面白くて眠れなくなる数学』など50冊以上。 サイエンスナビゲーターは株式会社sakurAi Science Factoryの登録商標です。

-コラム, 人と星とともにある数学, 数学
-,

© 2021 株式会社インフォマティクス