Qiitaにログインしてダークテーマを使ってみませんか?🌙

ログインするとOSの設定にあわせたテーマカラーを使用できます!

0

[Python][Julia]Project euler7 (プロジェクトオイラー7)

最終更新日 投稿日 2024年01月01日

Project euler Ploblem 7 (プロジェクトオイラー7)

10001st Prime

備忘のために残しておく。
コードを修正しました(指摘ありがとうございます)

問題

問題文 (意訳)

素数をはじめから順に6個並べると、2,3,5,7,11,13。6番目の素数は13だとわかる。
10001番目の素数は?

原文

By listing the first six prime numbers: 2, 3, 5, 7, 11 and 13 , we can see that the 6th prime is 13 .

What is the 10001st prime number?

解答

答え

104743

解答の方針

エラトステネスのふるいを使って10001個より大きい素数のリストを作成し、10001番目の素数をリストから取り出す。

Pythonのコード

Python Ploblem7
def eratosthenes(n: int) -> list:
    """エラトステネスのふるい"""
    isprime = [True] * (n+1)
    isprime[0], isprime[1] = False, False
    # ふるい
    for p in range(2, n + 1):
        素数以外(False)を飛ばす
        if not isprime[p]: 
            continue
        # p 以外の p の倍数をふるいにかける(TrueをFalseに)
        q = p + p
        while q <= n:
            isprime[q] = False
            q += p
    l = [x for x in range(n+1) if isprime[x]]
    return l

def seek_ans(limit: int, interval: int = 100000) -> int:
    # intervalは適当な値を置いている
    n = 2
    while len(eratosthenes(n)) < limit:
        n += interval
    return eratosthenes(n)[limit-1]
        
print(seek_ans(10001))

Juliaのコード

Julia Ploblem7
function eratosthenes(n::Int64)::Vector{Int64}
    # エラトステネスのふるい
    isprime = fill(true, n+1)
    isprime[1] = false
    
    for p in 2:n
        if !isprime[p]
            continue
        end
        # p 以外の p の倍数をふるいにかける(TrueをFalseに)
        q = p + p
        while q <= n
            isprime[q] = false
            q += p
        end
    end
    
    l = [x for x in 1:n if isprime[x]]
    return l
end

function seek_ans(limit::Int64, interval::Int64 = 100000)::Int64
    # intervalは適当に置く
    n = 2
    while length(eratosthenes(n)) < limit
        n += interval
    end
    
    return eratosthenes(n)[limit]
end

println(seek_ans(10001))

新規登録して、もっと便利にQiitaを使ってみよう

  1. あなたにマッチした記事をお届けします
  2. 便利な情報をあとで効率的に読み返せます
  3. ダークテーマを利用できます
ログインすると使える機能について
fujihop
@fujihop

コメント

WolfMoon@WolfMoon
        if not isprime[p]:
            continue

は,やめるべし。意味ない。

1
WolfMoon@WolfMoon

エラトステネスの篩の実装例は多いが,
https://qiita.com/WolfMoon/items/0483ac130684a10cf25e
なども見てください。

1
fujitanozomu@fujitanozomu(藤田 望)

@fujihopさん、

        # if not isprime[p]: 
            # continue

は有効にした方が無駄な処理が省けるので良いと思いますがどうして無効化されるんですか?

import timeit
print(timeit.timeit("print(seek_ans(10001))", globals = globals(), number = 1))

で比較してみました。

該当部分有効化
104743
0.08551279455423355

該当部分無効化
104743
0.2537324130535126

処理に掛かった時間を秒で出力しています。有効化した場合に比べて無効化した場合では 3倍近く処理時間が掛かっています。

1
fujihop@fujihop

@fujitanozomu さん コメント・検証ありがとうございます。
「ふるい」としては正しく、有効なものですね。

1

いいね以上の気持ちはコメントで

記事投稿キャンペーン開催中
記事投稿キャンペーン 「2024年!初アウトプットをしよう」
~
0