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) 中找到 Fib 数字，但是创建素数列表确实令人头疼，因为随着数字的增加，创建列表需要一些时间，并且几乎不可能到达n 成那些巨大的数字..我试图做一个定义而不是创建列表，而只是为用户提供的 n 计算素数。有什么想法吗？

先感谢您！

4

1 回答 1

1

对于素数，您可以实现几个素性测试。我喜欢幼稚的方法，检查到 sqrt(n)，正如 Marcus Stuhr 指出的那样，还有 Erathostenes 的筛子。如果你只检查奇数的素数，你可以稍微优化一下。

于 2013-01-03T22:42:06.347 回答