Project Euler 007

007

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10001 番目の素数を求めよ.

Sympyにありました。

import sympy

print(sympy.prime(10001))

->次の問題

考え方

順番に素数判定してリストに加えていく方法も試しましたが、エラトステネスの篩を使ったほうが早かったので適当な大きさの数を入れて計算しました。
任意のnについて計算できるようにしたかったので篩の大きさもnから計算したいと思い調べてみました。
nが十分に大きい場合、n番目の素数Pnは

Pn \approx n \bigl( \ln n + \ln(\ln n) \bigr)

で近似できるようです。
実際に試してみたところ、素数が13以上の場合(6番目以降の素数を予測する場合)は予測値Pnが実際の素数より大きくなるようなので、6番目以降の素数を計算する場合はPnまでのサイズの篩を作って計算すればn番目の素数を計算できそうです。
Pnを小数点以下切り上げて+2すれば2番目の素数から使用可能です。

コード

euler007.py

from math import log, ceil
from math_functions import prime_generator # 以前に作った指定した数値以下の素数を返すgenerator


def main():
    n = 10001
    #エラトステネスの篩のサイズを計算
    max_number = ceil(n * log(n) + n * log(log(n))) + 2
    prime_list = list(prime_generator(max_number))

    print(f'{max_number}以下の素数{len(prime_list)}個を生成')
    print(f'{n}番目の素数は{prime_list[n - 1]}')


if __name__ == '__main__':
    main()

math_functions

import numpy as np


def prime_generator(n: int) -> int:
    """
    n以下の素数を返すgenerator
    :param n: int
    :return: int
    """
    num_arr = np.arange(2, n + 1)
    while num_arr.size > 0:
        prime = num_arr[0]
        yield prime
        num_arr = num_arr[num_arr % prime != 0]

結果 114322以下の素数10818個を生成 10001番目の素数は104743 main処理時間: 1.0734169483184814 sec.
時間がかかってしまいますが、大きめのサイズの篩を用意して計算する以外にいい方法が思いつきません(；・∀・)
またn=1のとき、log 0でエラーが発生してしまうのでn=1の場合に処理をスキップするifを追加したほうがいいかもしれません。