【Python問題集】No.5　10001番目の素数を求める

問題

おすすめのレンタルサーバー

解答

解答を見る前に、一度ご自身で考え、コードを書いてみることをオススメします。

def is_prime_number(number: int) -> bool:
    if number <= 1:
        return False
    
    for i in range(2, number):
        if number % i == 0:
            return False
    
    return True


def get_next_prime_number(pre_prime_number: int) -> int:
    next_prime_number = pre_prime_number

    while True:
        next_prime_number += 1

        if is_prime_number(next_prime_number):
            return next_prime_number


def find_prime_number(order: int) -> int:
    prime_number = 1
    count = 0

    while count < order:
        prime_number = get_next_prime_number(prime_number)
        count += 1
    
    return prime_number


print('10001番目の素数は', find_prime_number(10001), 'です。')

10001番目の素数は 104743 です。

解説

この問題のポイントはズバリ、

素数をどう求めるか？

この1点に尽きるでしょう。

しかも、10001番目ですから、できるだけ効率的に求めたいですね。

素数とは？

素数を求めるにあたり、まずは素数がどんなものかを知る必要があります。

素数（そすう、英: prime number）とは、1 より大きい自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。1 より大きい自然数で素数でないものは合成数と呼ばれる。

素数 – Wikipedia

ということは、

と言えそうです。

①はそのままですね。

②からは、2は素数、2以外の偶数は素数ではない、ということが分かります。

あとは、この②の考え方が最も単純な素数の求め方になりそうですね。

自分自身より小さい自然数で割っていって、1以外に余りが0になるものが無ければ素数、と判断する方法が最もシンプルなので、今回の回答はこの方法を採用しました。

処理を関数にまとめる

もう1つ、今回は「小さい順から数えて10001番目の素数を求める」という処理を次の3つの関数に分けました。

③が今回の問題の答えを求める関数ですが、③の関数の中で②の関数を、②の関数の中で①の関数を使用しています。

分ける必要があるかは微妙ですが、分かりやすくなると思い、今回は3つの関数に処理を分けました。

本来は、引数が想定している値かどうかをチェックする必要がありますが、それは省いています。

偶数の判定は過去の問題で取り上げていますので、そちらを確認してください。

あわせて読みたい

【Python問題集】No.1　奇数・偶数の判定、リストから値を削除 Python初心者向けの問題集No.1です。＜問題＞自然数のリストを入力すると、そのリストから奇数をすべて削除したリストを出力するプログラムを作成せよ。さらに、そのプログラムが正しく機能することを示す具体例を与えよ。

Google Colaboratory

解答例や解説のコードは Google Colaboratory で確認しています。

あわせて読みたい

Google Colab

環境構築の不要な Google が提供している Webサービスなので、Python を学習中の方にはオススメです。

おわりに

今回の問題は LINE のオープンチャットに投稿されたものです。

今後も具体的な問題・課題の解説記事を増やしていきたいと思っています。

解説して欲しい問題・課題がありましたら、お問い合わせフォームからご連絡ください。

以上です。