如何找到给定数目的素数？

Question

我需要按升序找到一定数量的素数，从2开始。我有一个工作算法，它以一个数-极限为参数，它找到所有小于这个极限的素数。

例如，对于param 20，它将返回2,3,5,7,11,13,17,19，但我需要输入5并获取2,3,5,7,11。最好的方法是什么？我正在使用Eratosthenes的筛子，没有办法限制这个数字--删除部分，因为我不知道第195个素数有多大，因此我不知道是否应该删除1568年或1268426的所有2的倍数。我希望问题是清楚的，谢谢你的帮助

Answer 1

有几种方法可以做你想做的事。

素数定理表明，素数小于n的数渐近等于n/log(n)。您可以添加一个小缓冲区，然后进行Eratosthenes筛子，并抛出任何超过您的限制的素数。

这里的公式不是近似，而是计算小于n的素数，而不列出素数。你可以用其中一个公式找出n个素数，然后用一个筛子来列出素数。谷歌的“勒让德和”和“莱默的公式”，如果你想采取这种方法。

你可以用一个分割的埃拉托斯提尼筛子。筛到一些方便的极限。如果你有答案，就停下。否则，选择下一段，然后选择下一段，以此类推，直到找到您想要的素数。

有一种非常聪明的方法可以生成无限个素数列表，它用优先级队列替换Eratosthenes的筛子的位数组。谷歌的梅丽莎奥尼尔的论文，真正的筛子埃拉托斯提尼。

您可以看到所有这些算法的完整解释和实现，这里。

顺便说一下，第195个素数是1187年。有247个素数小于1568,97790素数小于1268426。

Answer 2

您可以在Eratosthenes的原始筛子后面采用相同的想法，但可以迭代地这样做。

find_n_primes(num_primes):
  primes = [2]
  i = 3
  while primes.size < num_primes:
    is_prime = true
    for p in primes:
      if p > sqrt(i):
         break
      if i % p == 0: 
        is_prime = false
        break
    if is_prime:
      primes.add(i)

    i++
  return primes

基本上，与其将每个数字的倍数取到不动点，不如迭代n，然后检查您已经找到的所有素数。

Answer 3

不久前，我编写了一个处理素数的小模块(在处理Project时满足了我的需要)。这是非常迅速的，因为它跟踪它所见过的素数列表。这大大减少了计算时间。

这是您需要的主要例程(用python编写)。文档是平庸的，但我希望这会有所帮助。

def primes(num, l=[]):

    # l is the list of prime numbers you already have
    # This is reused to check for primality of a number

    if len(l) == 0: l = get_list() # Read from disk

    # Check to see if a sublist can be created
    e = l[-1]
    if (num < e):
        res = search.binary_low(l, num)
        return l[:res[0]+1]

    e = 6*(ceil(e/6))

    lim = num + 1
    # Extend the current list
    for n in range(e, lim, 6):
        m = n - 1
        if isprime(m, l): l.append(m)
        m = n + 1
        if isprime(m, l): l.append(m)

    # Save to pickle
    set_list(l) # Write to disk

    return l

你可以在这里找到相关的例程。

https://github.com/pavanky/expo/blob/master/python/prime.py

https://github.com/pavanky/expo/blob/master/python/search.py