見出し画像

[python] 準備編 03 : 素数をテーマにプログラミングを楽しく学びます。

Kimono club

概要　素数はおもしろい性質をもっています。素数をテーマにプログラミングを楽しく学んでいきましょう。

前回の復習

前回は、ある数が素数かどうかを判定するコードを書き、100000までに素数が何個現れるかを数えました。しかし、この方法では数が大きくなるにつれて計算に時間がかかってしまいます。

def is_prime_number(natural_number):
    n = 0  # 変数nを0で初期化
    for i in range(natural_number):  # 0からnatural_number-1までの繰り返し処理
        if natural_number % (i + 1) == 0:  # natural_numberをi+1で割った余りが0の場合
            n += 1  # nに1を加える
    if n == 2:  # nが2の場合
        return True  # True を返す
    else:  # nが2でない場合
        return False  # False を返す

コードの無駄を省く

その計算は必要か？

このコードには無駄があります。例えば、5の約数を数えるときに、次のように計算しています。

  1. 5 を 1 で割って、余りが 0 か判定する。

  2. 5 を 2 で割って、余りが 0 か判定する。

  3. 5 を 3 で割って、余りが 0 か判定する。

  4. 5 を 4 で割って、余りが 0 か判定する。

  5. 5 を 5 で割って、余りが 0 か判定する。

まず、1番目、1で割っていますが、どの数も1で必ず割り切れるので計算する必要はありません。 次に、5番目、5で割っていますが、どの数も自分自身で必ず割り切れるので計算する必要はありません。 1と自分自身で割るケースは必ず余りがゼロになります。以下のように書き直すことができます。

for i in range(2, natural_number):  
    if natural_number % i == 0:  # natural_numberをiで割った余りが0の場合
        n += 1  # nに1を加える

次に100の約数を計算する場合を考えてみましょう。 100 は 2 で割り切れます。100÷2=50，50 も 100 の約数です。 100 は 5 で割り切れます。100÷5=20, 20 も 100 の約数です。 20や50は約数であることは、この時点でわかっているので、再び20や50で100が割れるか確認する必要はないということです。 では、どこまで調べたら十分なのでしょうか。100であれば、

$$
\sqrt{100}
$$

​までです。つまり、ある数の平方根まで調べたら十分です。ある数をxとおけば、

$$
\sqrt{x}
$$

​まで調べたら十分です。

for i in range(2, int(natural_number ** .5)+1):  
    if natural_number % i == 0:  # natural_numberをi+1で割った余りが0の場合
        n += 1  # nに1を加える

Pythonでは例えばxの平方根を求める際、次のように書きます。

x ** .5

range()の引数は整数である必要があるので、int()によって整数部分だけ取り出しています。int()は引数の値のうち整数部分のみ取り出す関数です。この関数を使うためには import math として、数学関係の関数を使う準備をしておく必要があります。

import文とは

import文は、Pythonのコードで外部のモジュールやライブラリを利用できるようにするものです。モジュールやライブラリは、他の人が作成した便利な関数やクラスの集まりであり、これらを活用することで、自分で一からコードを書く手間を省き、より効率的にプログラムを作成することができます。

import mathと書くことで、Pythonに標準で用意されているmathモジュールをインポートし、その中の関数（例えばsqrt()など）を利用できるようになります。mathモジュールには、平方根を計算するsqrt()関数や、三角関数、指数関数など、様々な数学関連の関数が含まれています。

import文を使うことで、車輪の再発明を避けることができます。車輪の再発明とは、すでに存在するもの（ここでは便利な関数）を再び作ってしまうことを指します。import文を効果的に利用することで、開発効率を向上させることができます。


さらなる高速化

さらなる高速化を考えていきましょう。

for i in range(2, int(natural_number ** .5)+1):  
    if natural_number % i == 0:  # natural_numberをi+1で割った余りが0の場合
        n += 1  # nに1を加える

わたしたちは上のコードのように，ある数の約数をすべて数え上げています。しかし，全て数え上げる必要はありません。1 と自分自身以外の約数，つまり3つ目の約数があるならば，その数は素数ではありません。3つ目の約数が見つかった時点でその数は素数ではないと判断し，計算をやめていいわけです。

import math

def is_prime_number(natural_number):
    if natural_number < 2:
        return False

    for i in range(2, int(math.sqrt(natural_number)) + 1):
        if natural_number % i == 0:
            return False
    return True

上のように，natural_numberをiで割った余りが0であったら，natural_number は素数ではないと判断しています。

本当に高速化しているのか？

さて，前回作ったコードは 100000までの素数の個数を求めるのに，373.94 秒かかりました。6分以上かかっています。

今回のコードではどうでしょうか。下のコードを実行し，実行時間を計測してみました。

import time
import math

def is_prime_number(natural_number):
    if natural_number < 2:
        return False

    for i in range(2, int(math.sqrt(natural_number)) + 1):
        if natural_number % i == 0:
            return False
    return True


def count_prime_number_between(n1,n2):
    n = 0
    for i in range(n1, n2+1):
        if is_prime_number(i):
            n += 1
    return(n)

count1 = count_prime_number_between(2, 10)
print(f"10\tまでには{count1}個")
count2 = count_prime_number_between(11, 100) + count1
print(f"100\tまでには{count2}個")
count3 = count_prime_number_between(101, 1000) + count2
print(f"1000\tまでには{count3}個")
count4 = count_prime_number_between(1001, 10000) + count3
print(f"10000\tまでには{count4}個")
count5 = count_prime_number_between(10001, 100000) + count4
print(f"100000\tまでには{count5}個")

結果，0.15 秒。1秒もかからずでした。前回のコードは6分以上かかりましたので，だいぶん改善されましたね。それでは，1000000000 までの素数の個数を数えてみましょう。

実行してみました。しかし，あれから1日が経とうとしていますが，未だ計算が終わりません。

コードの効率化はまだ必要なようです。

次回の予告

次回はより計算を効率化します。今回のコードにはまだ無駄があります。半分程度は作業時間を減らせるはずなのですが，どこに無駄があるかわかりますか？

関連する記事

以前作ったパズルゲームです。面白いと思います。

  • 解ける？Python with Pyxel でパズルゲームを作りました。[note]

およそ1年前ピンポンを作ろうと思ってそのままになっていました。また続きを書いてみたいです。

  • ピンポンを Python with Pyxel で作る。[note]

Python のおすすめの入門書

[ サイトマップを見る ]


いいなと思ったら応援しよう！