ログイン新規登録

Qiitaにログインして、便利な機能を使ってみませんか？

あなたにマッチした記事をお届けします

便利な情報をあとから読み返せます

ログイン新規登録
0
0
@fujihop

[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
rss_feed

コメント

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
WolfMoon@WolfMoon
（編集済み）

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

そうですか。理論的に考えて，処理時間の差は無視できる程度だと思いますが...

以下に当方での処理結果を載せておきます。max_limit = 100000 での結果です。

continue を使います
$ python3
Python 3.12.0 (v3.12.0:0fb18b02c8, Oct  2 2023, 09:45:56) [Clang 13.0.0 (clang-1300.0.29.30)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 
>>> from time import time
>>> max_limit = 100000
>>> 
>>> #------------------
>>> 
>>> 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]
... 
>>> s = time()
>>> print(seek_ans(max_limit), time() - s)
1299709 1.5001881122589111
>>> quit()

引き続き

continue を使いません
$ python3
Python 3.12.0 (v3.12.0:0fb18b02c8, Oct  2 2023, 09:45:56) [Clang 13.0.0 (clang-1300.0.29.30)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 
>>> from time import time
>>> max_limit = 100000
>>> 
>>> #------------------
>>> 
>>> def eratosthenes2(n: int) -> list:
...     """エラトステネスのふるい"""
...     isprime = [True] * (n+1)
...     isprime[0], isprime[1] = False, False
...     # ふるい
...     for p in range(2, n + 1):
...         # p 以外の p の倍数をふるいにかける(TrueをFalseに)
...         if isprime[p]: 
...             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_ans2(limit: int, interval: int = 100000) -> int:
...     # intervalは適当な値を置いている
...     n = 2
...     while len(eratosthenes2(n)) < limit:
...         n += interval
...     return eratosthenes2(n)[limit-1]
... 
>>> #------------------
>>> 
>>> s = time()
>>> print(seek_ans2(max_limit), time() - s)

1299709 1.1917200088500977
>>> 
>>> quit()

timeit で

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

104743
0.08967183399909118

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

104743
0.09099333399899479

何回か行うと，所要時間に違いは出ますが，むしろ continue を使わないほうが速いかもしれません。少なくとも，continue を使わないほうが 3 倍遅いということはなさそうに思います。

もっと単純な場合。

from time import time
n = 100000000

s = time()
t = 0
for i in range(n):
    if i % 2 == 0:
        continue
    else:
        t += 1
print(t, time() - s)

s = time()
t = 0
for i in range(n):
    if i % 2 != 0:
        t += 1
print(t, time() - s)



50000000 7.034915208816528
50000000 6.985969066619873

要するに，言いたいことは， if ***: continue は無駄だということですが。

0

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

ログイン新規登録
記事投稿キャンペーン開催中
記事投稿キャンペーン 「2024年!初アウトプットをしよう」
~
すべて見る
0
0