LoginSignup
6
5

More than 1 year has passed since last update.

@hanzawak(k hanzawa)

Pythonで0からプログラムを書く際の考え方（初学者向け、素数編）

Last updated at Posted at 2019-09-02

はじめに

最近Pythonを学習する人が増えているためか、初学者向けの本や動画などが多く見られるようになりました。
しかしそれらの中身はPythonの構文やちょっとしたプログラムの解説が多く、0からPythonのプログラムを書く際の考え方を解説したものがあまり無いように思えます。
そこでPythonをある程度勉強した人向けに、0からプログラムを書く際の考え方をまとめました。

考え方のまとめのため、文字が多く記載されています。

対象読者

Pythonの基礎を理解している人を対象としています。
リスト、for文、if文くらいがわかれば理解できると思います。

問題

さっそくですが問題です。
「100までの素数を表示するプログラムを作成してほしい」
と言われた際に皆様はどのように作成を始めるでしょうか。

頭で考えながらプログラムを書く人、紙に処理の流れを書いてからプログラムを書く人、ネットで調べまくってツギハギでプログラムを書く人、など様々な進め方があると思います。

以下からは私がプログラムを作成する際の考え方をまとめております。もちろん人によって考え方が異なりますし、それに伴いアルゴリズムや出来上がるプログラムも異なります。
あくまで「このように考えればプログラムが作れる」という参考にしていただければと思います。

進め方

進め方の大枠としては以下の通りです。

  1. アルゴリズムを文字で書く
    1. 概要を書く
    2. 詳細に書く
  2. 形はどうあれ動くプログラムを書く
  3. 綺麗に書き直す
  4. 処理を効率化（スピードアップ）する

初学者向けのため、まずは形はどうであれ正しく動くプログラムを作成することを目標とします。その後、余裕があれば綺麗に書き直したり処理を効率化することを考えます。

アルゴリズムを文字で書く

概要を書く

そもそもやりたいことは何なのかを正確に把握する必要があります。
もし「素数って1も含まれたっけ」とか若干あやふやな部分があるなら、まず調べてみましょう。

Wikipediaには以下が記載されています。

素数とは、1と自分自身以外に正の約数を持たない自然数で、1でない数のこと。

なるほど。1は含まれないそうです。それであれば自分以外で割り切れるか1つずつ確認すれば素数がわかるのではないかと考えられます。
問題は「100までの素数を表示する」ですがいきなり大きな数字だと考えにくいことがありますので、まずは「10までの素数を表示する」と小さい範囲ではじめてみます。10までの素数が正しく表示できるようになれば100まででも10000まででも表示できるはずです。
では早速アルゴリズムの概要をまとめてみます。

  1. 例えば5が素数か調べるときは、2,3,4で割り算をして余りを確認。全ての計算結果で余りがあれば（割り切れていなければ）5は素数である
  2. 例えば10が素数が調べるときは、2,3,4,5,6,7,8,9で割り算をして余りを確認。全ての計算結果で余りがあれば（割り切れていなければ）10は素数である

こんな感じです。アルゴリズムと言えるようなものではありませんが、まずはこのように考えれば良いのかという方針が決まるかと思います。
後ろの工程でこのアルゴリズムをより本物っぽく書き換えていこうと思います。

詳細に書く（第1段階）

前段階のアルゴリズムですと汎用的では無いため、汎用的になるように記載してみます。

  1. 素数か調べたい数値に対して、2からその1つ手前の数値までで割り算をする
  2. もし1つでも余りが0であれば割り切れているので素数ではない
  3. もし全て余りが0でなければ素数である

詳細に書く（第2段階）

少しプログラムっぽく書き直してみます。
「素数か調べたい数値」というのは2,3,4,5,,,と変動しますのでiに置き換えます。
ということは「2からその1つ手前の数値まで」は2からi-1までに置き換えることができます。

  1. i（素数か調べたい数値）に対して、2からi-1まで（2からその1つ手前の数値まで）で割り算をする
  2. もし1つでも余りが0であれば割り切れているので素数ではない
  3. もし全て余りが0でなければ素数である

詳細に書く（第3段階）

より詳細に書き直してみます。
まず、割り切れているか割り切れていないかという状態を保存しておくためのフラグが必要です。この素数を判定するためのフラグをflagという名前にして、初期状態をTrueにしておきます。
もし割り切れたらflagをFalseにして素数では無いと印をつけることにします。

  1. flag（素数判定フラグ）をTrueに初期化
  2. i（素数か調べたい数値）に対して、2からi-1まで（2からその数値の1つ手前までの数値）で割り算をする
  3. もし1つでも余りが0であれば割り切れているので素数ではない（flagをFalseにする）
  4. もし全て余りが0でなければ素数である（flagはTrueのまま）

詳細に書く（第4段階）

より詳細に書き直してみます。
まず、素数と判明した数値を格納するためのリストが必要だと思いますので、numbersというリストを作ります。
さらに、ループ処理していることがわかりやすいようにインデントもつけてみます。

  1. numbers（素数を格納するリスト）を初期化
  2. flag（素数判定フラグ）をTrueに初期化
  3. i （素数か調べたい数値）に対して、2からi-1まで（2からその数値の1つ手前までの数値）で割り算をする
    1. もし1つでも余りが0であれば割り切れているので素数ではない（flagをFalseにする）
    2. もし全て余りが0でなければ素数である（flagはTrueのまま）
    3. 素数であればnumbersに追加

詳細に書く（第5段階）

前段階で作成したアルゴリズムを確認してみます。
よく考えると前段階のアルゴリズムですと「flag（素数判定フラグ）をTrueに初期化」するタイミングがループの外にあるため、1度しか実行されません。i（素数か調べたい数値）が変わるたびにTrueにしないといけませんので、ループの中で「flag（素数判定フラグ）をTrueに初期化」するようにします。

  1. numbers（素数を格納するリスト）を初期化
  2. i （素数か調べたい数値）に対して、2からi-1まで（2からその数値の1つ手前までの数値）で割り算をする
    1. flag（素数判定フラグ）をTrueに初期化
    2. もし1つでも余りが0になっていれば割り切れているので素数ではない（flagをFalseにする）
    3. もし全て余りが0でなければ素数である（flagはTrueのまま）
    4. 素数であればnumbersに追加

詳細に書く（第6段階）

より詳細に書き直してみます。
ここではループ処理の部分をよく考えてみようと思います。

まずループの範囲について考えます。
ループの範囲は例えば10までの素数を調べたい場合は、2,3,4,5,6,7,8,9,10（合計9回）となります。ということは2からiまで（合計9回）をループすれば良いということになります。
次に「割り算をする」という処理はループの中で行いますので、ループの中に移動します。

  1. numbers（素数を格納するリスト）を初期化
  2. 2からiまでをループ
    1. flag（素数判定フラグ）をTrueに初期化
    2. 割り算をする
    3. もし1つでも余りが0になっていれば割り切れているので素数ではない（flagをFalseにする）
    4. もし全て余りが0でなければ素数である（flagはTrueのまま）
    5. 素数であればnumbersに追加

詳細に書く（第7段階）

より詳細に書き直してみます。
ここでは割り算をする部分をよく考えてみようと思います。

  • もしi（素数か調べたい数値）が5なら、割り算の対象は2,3,4です
  • もしi（素数か調べたい数値）が10なら、割り算の対象は2,3,4,5,6,7,8,9です

このようにiが変化するたびに割り算の対象となる数値も変化させる必要があります。
そこで割り算の対象となる数値をjとして再度上の内容を考え直してみると、以下のように書き換えることができます。

  • もしi（素数か調べたい数値）が5なら、jは2からi-1です
  • もしi（素数か調べたい数値）が10なら、jは2からi-1です

この内容を踏まえて割り算の部分を書き直してみます。

  1. numbers（素数を格納するリスト）を初期化
  2. 2からiまでをループ
    1. flag（素数判定フラグ）をTrueに初期化
    2. iをj（2からi-1までのいずれかの数値）で割り切れたら素数ではない（flagをFalseにする）
    3. iをj（2からi-1までのいずれかの数値）で割り切れなかったら、素数である（flagはTrueのまま）
    4. 素数であればnumbersに追加

若干ややこしくなってきたかもしれませんが、落ち着いて1行ずつ考えれば理解できるかと思います。

詳細に書く（第8段階）

より詳細に書き直してみます。
「iをj（2からi-1までのいずれかの数値）で割り切れたら」という部分はループ処理になりますので、ループに書き直してみます。
あとよく考えると「素数であればnumbersに追加」の処理は内側のループ（2からi-1までをループ）ではなく外側のループ（2からiまでをループ）が正しいのでインデントを調整します。numbersに追加するタイミングは素数かどうかが判定が完了したタイミングだからです。

  1. numbers（素数を格納するリスト）を初期化
  2. 2からiまでをループ
    1. flag（素数判定フラグ）をTrueに初期化
    2. 2からi-1までをループ
      1. iをj（2からi-1までのいずれかの数値）で割り切れたら素数ではない（flagをFalseにする）
      2. iをj（2からi-1までのいずれかの数値）で割り切れなかったら、素数である（flagはTrueのまま）
    3. 素数であればnumbersに追加

お疲れさまです。ついにアルゴリズムが完成しました！

形はどうあれ動くプログラムを書く

上記のアルゴリズムをそのままプログラムにしてみます。

# 1. `numbers`（素数を格納するリスト）を初期化
numbers = []

# 2. `2からiまで`をループ
# まずは10までの素数を表示するためiを10として、2〜10をループさせる
# 2〜10の範囲はrangeで書くと「range(2, 11)」となる
for i in range(2, 11):

    # 1. `flag`（素数判定フラグ）を`True`に初期化
    flag = True

    # 2. `2からi-1まで`をループ
    # 2からi-1の範囲はrangeで書くと「range(2, i)」となる
    for j in range(2, i):

        # 1. `i`を`j`（`2からi-1`までのいずれかの数値）で割り切れたら素数ではない（`flag`を`False`にする）
        # 2. `i`を`j`（`2からi-1`までのいずれかの数値）で割り切れなかったら、素数である（`flag`は`True`のまま）
        if i % j ==0:
            flag = False

    # 3. 素数であれば`numbers`に追加
    if flag == True:
        numbers.append(i)

# 結果確認
print(numbers)

上記を実行すると2, 3, 5, 7と表示されると思います。
100までの素数を表示したい場合はrange(2, 11)をrange(2, 101)に書き直すだけです。
いかがでしょうか。文字でアルゴリズムさえかければプログラムをかけることがわかっていただけたかと思います。

綺麗に書き直す

上記のプログラムですと表示したい素数の数が変わるとrange(2, 11)の部分を書き直すことになりますし、使い勝手が悪いです。
そのため関数化してみようと思います。PrimeNumberとは素数の意味です。

def prime_number(number):    # 追記
    numbers = []

    for i in range(2, number + 1):    # 修正
        flag = True

        for j in range(2, i):
            if i % j ==0:
                flag = False

        if flag == True:
            numbers.append(i)

    print(numbers)

prime_number(100)    # 追記

処理を効率化（スピードアップ）する

上記のプログラムで10万までの素数を表示しようとすると時間がかかるかと思います。
実はこのプログラムは非常に効率の悪い方法で素数を探しているためです。

このプログラムでは「2からi-1まで」の値の全てで割り算をしていますが、例えば1つの数値で割り切れたらその後ろの数値で割り切れるかを確認する必要はないです。
たとえば10が素数か確認する場合、2で割り切れるのでその後の3〜9で割り切れるか確認する必要はないということです。
この考えで効率化（スピードアップ）するアルゴリズムに修正しようと思います。

  1. numbers（素数を格納するリスト）を初期化
  2. 2からiまでをループ
    1. flag（素数判定フラグ）をTrueに初期化
    2. 2からi-1までをループ
      1. iをj（2からi-1までのいずれかの数値）で割り切れたら素数ではない（flagをFalseにする） + その時点でループを抜ける（break）
      2. iをj（2からi-1までのいずれかの数値）で割り切れなかったら、素数である（flagはTrueのまま）
    3. 素数であればnumbersに追加

プログラムを書く

1箇所追記するだけです。
このプログラムで10万までの素数を表示しようとすると先ほどより体感的に早くなるのがわかると思います。

def prime_number(number):
    numbers = []

    for i in range(2, number + 1):
        flag = True

        for j in range(2, i):
            if i % j ==0:
                flag = False
                break    # 追記

        if flag == True:
            numbers.append(i)

    print(numbers)

prime_number(100)

さらに処理を効率化（スピードアップ）する

実はさらに効率化することも可能です。
「2からi-1まで」の数値で割り算をしていますが、例えば2で割り切れないものは4でも割り切れないです。
ということは、i-1までの素数で割り切れるか確認するだけでよいということがわかります。
この考えで効率化（スピードアップ）するアルゴリズムに修正してみます。

プログラムを書く

1箇所修正するだけです。
このプログラムで10万までの素数を表示しようとすると先ほどより体感的に早くなるのがわかると思います。

def prime_number(number):
    numbers = []

    for i in range(2, number + 1):
        flag = True

        for j in numbers:    # 修正
            if i % j ==0:
                flag = False
                break

        if flag == True:
            numbers.append(i)

    print(numbers)

prime_number(100)

さらに処理を効率化（スピードアップ）する

実はさらに効率化することも可能です。
しかしここでは「初学者がプログラムを書く際の考え方を把握する」ことが目的ですので、ご興味があればご自身で改良していってください！

6
5
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
5