【Project Euler】No.7 : 10001st prime 解答例【Python】

【Project Euler】No.7 : 10001st prime 解答例【Python】

はじめに

コジマです。

https://projecteuler.net/
の7問目を解いていきます。

問題

問題7

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 10 001st prime number?

和訳(意訳)
リストによって6番目の素数は: 2,3,5,7,11, そして 13となり、6番目の素数は13だとわかる。

10001番目の素数はなにか?

解答例

【Project Euler】No3: Largest prime factor 解答例【Python】
過去に扱った素数判定ロジックを流用していきます。
10001番目の素数になったところで処理をストップします。

# おまじない
import numpy as np
import math

# 素数探索の初期値を10に設定
n = 10

# cnt番目の素数をしりたい。
# 1桁目は見なかったことにするので、5で初期化
cnt = 5

# 10001番目の素数が見つかるまでやる
def judgePrime(n):
    # 1の位が [0, 2, 4, 5, 6, 8]の時計算不要
    if n % 10 in [0, 2, 4, 5, 6, 8]:
        # 素数じゃない
        return 0

    # 3の倍数判定
    # 1文字ずつの配列作成
    num_array = list(map(int, str(n)))
    if sum(num_array) % 3 == 0:
        # 素数じゃない
        return 0

    # √nまで調べればOK
    for i in range(3 , int(math.sqrt(n))+1, 2):
        if(n % i == 0):
            # 素数じゃない
            #print(n , i)
            return 0
        else:
            pass

    # 素数
    #print("{}番目の素数 : {}".format(cnt, n))
    return n

# ここかっこ悪いソースだなと思いながら書いてた
result = 0
while True:
    result = judgePrime(n)
    if result != 0:
        if cnt == 10001:
            break
        cnt += 1 
    n += 1
    
print("cnt = {}".format(cnt))
print("10001番目の素数:{}".format(n))

さいごに

解答はgithubにも上げています。
https://github.com/kojimanotech/project_euler/blob/master/0007_10001st_prime.ipynb

この記事を面白いまたは役に立ったと思ってくれた方は是非私のTwitter(@kojimanotech)を
フォローしてくれたらうれしいです!

以上、コジマでした。


Pythonカテゴリの最新記事