使用 Logs 或其他快速方法查找第 n 个质数，并详细说明它如何使用 ruby(不是暴力强制)

Question

我正在尝试找到一种方法来找到欧拉项目 #7 的第 10001 个素数，我已经强行找到了答案，但我更想知道如何使用运行速度更快的更复杂的方法得出答案。请向我详细解释它是如何工作的。

我知道所有方法都需要数学，所以我主要关心的是理解找到第n个素数的解决方案背后的数学逻辑。

Answer 1

正如任何数论教科书都会告诉你的那样，第 n 个素数小于 n(log e n + log e log_en(，因此您可以使用埃拉托色尼筛来计算过多的素数，然后将列表修剪到所需的大小。以下是埃拉托色尼筛子的简单版本：

function primes(n) # primes less than n
sieve := makeArray(2..n, True)
for p from 2 to n step 1
if sieve[p]
output p
for i from p*p to n step p
sieve[i] = False

对于第 10,000 个素数，您将需要小于 10000 * 的素数 *(log 10000 + loglog 10000( = 10000 * (9.21034 + 2.2203268( = 114307。您的筛子应该计算素数列表并立即返回。我会让你把伪代码翻译成 Ruby。

有更好的方法来计算第n个素数，但这对于欧拉计划来说已经足够了，并且比使用试验除法来检查素数要快得多。

Answer 2

这里有一个例子(也是我认为使用全局变量可以的极少数时刻之一(。

$primes = {2 => nil}  # Hash for constant asymptotic lookup time, 2 for only even prime
def prime?(num)
return false if num <= 1
return true if $primes.key?(num)
Math.sqrt(num).to_i.downto(2).each {|i| return false if num % i == 0}
$primes[num] = nil
true
end
num = 3  # start with first odd prime
while ($primes.length < 10001)
prime?(num)  #  Check if number is prime and add to $primes if it is
num += 2     #  Only check odd numbers
end
$primes.keys[1-1]      # 1st prime number => 2
$primes.keys[10001-1]  # 10001st prime number => 104743

在此示例中，不需要return true if $primes.key?(num)行，但在检查已知为素数的数字时很有用。 我希望对您有所帮助。