python - 优化第 n 个素数 Ruby/Python 的代码

Question

我需要在 Ruby 或 Python 中以最快的方式找到第 n 个素数：

require "prime"

puts Prime.first(n).join("")  

对于 >= 100000 的数字，这需要很长时间。

如何优化此代码？

Answer 1

试试这个：-

# Steps
    # List first 'n' prime
    # Choose the very last one


require "prime"

def nprime(n)
   (Prime.first n).last
end

puts nprime(10001)

它很快就给了我答案：

$ ruby nprime.rb
   104743

Answer 2

你可以在 python 中尝试这个动态程序，它在素数字典中查找（由程序本身动态构建），它最初是空的，当你找到更大的素数时它会变得更快。

dict = {}
def prime(x):
    dict[1] = 2
    s = x
    if x in dict:
        return dict[s]
    else:
        while s > 0:
            if s in dict:
                pno = int(dict[s]) + 1
                break 
            s-=1

        while s < x:
            m = 1
            while m <= s:
                if pno % dict[m] == 0:
                    pno+=1
                    m=1
                else:
                    m+=1
            dict[s+1]= pno
            s+=1
        return dict[x]

最初为较低的素数构建字典以加速较高的素数。查找第 10000 个素数的示例，在运行模块的 python shell ahen 中执行以下操作： prime(1000) prime(5000) prime(10000)

Answer 3

Prime Ruby 文档。

require "prime"
Prime::EratosthenesSieve.instance.get_nth_prime(1000000)