0

重複の可能性：
20、30、n番目の素数を調べます。（私は20番目になりますが、30番目にはなりませんか？）[Python]Python
でNより下のすべての素数を一覧表示する最速の方法

素数 ：

P=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, …]

フィボナッチ数：

F=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …]

ユーザーが（1,100000）とプログラムの間の乱数を指定して、結果を要約する(F[n]+P[n])ようにします。n=3 F[3]+P[3]=7+2=9

私は次のコードを書きました：

import math
def F(n):
    return int(((1+math.sqrt(5))**n-(1-math.sqrt(5))**n)/(2**n*math.sqrt(5)))
L=[]
L.append(2)
L=[]
for n in range(2, 10000):
    for x in range(2, n):
        if n % x == 0:
            break
    else:
        # loop fell through without finding a factor
        L.append(n)

while True:
    x = raw_input().strip()
    if x == "END" or x == "end":
        break
    else:
        num = int(x)
        print F(num)+L[num]

def F（n）からフィボナッチ数を見つけるのは簡単ですが、素数リストを作成することは、数が増えるにつれてリストの作成に時間がかかり、到達するのがほとんど不可能になるため、本当に頭痛の種です。 nをそれらの巨大な数に..私はリストを作成するのではなく、ユーザーによって提供されたnの素数を計算するだけでdefを作成しようとしました。

前もって感謝します！

4

1 に答える 1

1

素数の場合、実装できる素数テストがいくつかあります。私は素朴な方法が好きで、sqrt（n）までチェックします。マーカス・ストゥールが指摘したように、エラトステネスのふるいもあります。奇数の素数性のみをチェックすると、少し最適化できます。

于 2013-01-03T22:42:06.347 に答える