4

我正在尝试在python中实现eratosthenes的筛子，但是当试图找到所有素数直到例如779695003923747564589111193840021的平方根时，我收到一个错误，说range（）的结果有太多项目。我的问题是，我该如何避免这个问题，如果我用 while 循环实例化列表，我会收到一个错误，说我使用了太多内存（甚至在它开始使用页面文件之前），下面列出了这两个：

使用范围（）

maxnum = 39312312323123123

primes = []
seq = []
i = 0
seq = range(2,maxnum)

for i in seq:
    mul = i * seq
    for j in mul:
        try:
            seq.remove(j)
        except:
            pass
        primes.append(i)

print primes

使用同时：

maxnum = 39312312323123123

primes = []
seq = []
i = 0
while i < maxnum:
    seq.append(i)
    i+=1

for i in seq:
    mul = i * seq
    for j in mul:
        try:
            seq.remove(j)
        except:
            pass
        primes.append(i)

print primes
4

7 回答 7

6

我会说，“xrange()改为使用”，但您实际上是在使用整数列表作为筛分结果.....所以整数生成器不是正确的解决方案。

我认为很难实现一个包含 39312312323123123 个元素的列表，无论您使用什么函数来实现......毕竟，279 PB 的 64 位整数。

试试这个。

class FoundComposite(Exception): pass

primes = [2]

seq = itertools.takewhile(        # Take integers from a list
          lambda x: x<MAXNUM,     #   until we reach MAXNUM
          itertools.count(2)      #   the list of integers starting from 2
          )

#seq = xrange(2, MAXNUM)          # alternatively

for i in seq:
    try:
        for divisor in primes:
            if not (i % divisor):
                # no remainder - thus an even divisor
                # continue to next i in seq
                raise FoundComposite 
        # if this is reached, we have tried all divisors.
        primes.append(i)
    except FoundComposite:
        pass
于 2010-02-25T21:22:18.487 回答
2

你的算法坏了。首先让它为 maxnum=100 工作。

一旦你让它工作，你会发现 maxnum=100000000 需要很长时间才能运行。

绘制在 (10,100,1000,10000,100000,1000000...) 中运行 maxnum 所需的时间，您可以推断出 39312312323123123 需要多长时间 :)

于 2010-02-25T21:29:15.583 回答
2

这是一种更复杂的算法，可能在技术上不算作筛子，但一种方法是不要一次删除给定素数的所有倍数，而是将下一个倍数（与素数一起）排队。这可以在生成器实现中使用。队列最终仍将包含许多（多个）素数，但不如构建然后过滤列表那么多。

前几个步骤手动完成，以显示原理...

  • 2 是素数 - 产量和队列 (4, 2)
  • 3 是素数 - 产量和队列 (6, 3)
  • 4 是复合的 - 将队列中的 (4, 2) 替换为 (6, 2)
  • 5 是素数 - 产量和队列 (10, 5)
  • 6 是复合的 - 将 (6, 2) 替换为 (8, 2) 并将 (6, 3) 替换为 (9, 3)

注意 - 队列不是 FIFO。您将始终提取具有最低第一项的元组，但新的/替换元组（通常）没有最高的第一项，并且（如上面的 6）会有重复项。

为了在 Python 中有效地处理队列，我建议使用以元组的第一项为键的字典（即哈希表）。数据是一组第二项值（原始素数）。

正如其他地方所建议的那样，在尝试大目标之前先测试小目标。如果你失败了也不要太惊讶。您可能仍然需要一次（在队列中）太多堆分配的大整数来完成解决方案。

于 2010-02-25T21:47:46.613 回答
1

有一个用于 python 的第三方模块，称为gmpy

它有几个功能可能对您有用，因为它们非常快。概率的东西大约在 40 亿大关。

next_prime(...)
    next_prime(x): returns the smallest prime number > x.  Note that
    GMP may use a probabilistic definition of 'prime', and also that
    if x<0 GMP considers x 'prime' iff -x is prime; gmpy reflects these
    GMP design choices. x must be an mpz, or else gets coerced to one.

is_prime(...)
    is_prime(x,n=25): returns 2 if x is _certainly_ prime, 1 if x is
    _probably_ prime (probability > 1 - 1/2**n), 0 if x is composite.
    If x<0, GMP considers x 'prime' iff -x is prime; gmpy reflects this
    GMP design choice. x must be an mpz, or else gets coerced to one.
于 2010-02-25T21:41:50.067 回答
0

range()返回一个包含请求范围内所有数字的列表，whilexrange是一个生成器，并一个接一个地生成数字，内存消耗接近于零。

于 2010-02-25T21:27:04.717 回答
0

关于内存限制，如何创建一个内部是列表或数组的链表的自定义列表（类）。在内部神奇地从一个遍历到另一个，并根据需要添加更多，因为调用者使用您的自定义列表和您提供的外部接口，这将类似于促进 .append .remove 等需要的那些成员您的问题中使用的数组。

注意：我不是 Python 程序员。不知道如何实现我在 Python 中所说的内容。也许我不知道这里的上下文，所以如果我被否决，我会理解的。

也许使用“生成器”，因为它们在 python 中被调用来产生内部列表的结果，就好像它是一个巨大的单个列表一样。可能与链表。

于 2010-02-25T21:40:03.220 回答
0

试试这个：

def getPrimes(maxnum):
    primes = []
    for i in xrange(2, maxnum):
        is_mul = False
        for j in primes:         # Try dividing by all previous primes
            if i % j == 0:
                is_mul = True    # Once we find a prime that i is divisible by
                break            # short circuit so we don't have to try all of them
        if not is_mul:           # if we try every prime we've seen so far and `i`
            primes.append(i)     # isn't a multiple, so it must be prime
    return primes

在获得大量素数之前，您不应该耗尽内存。这样您就不必担心创建倍数列表。不确定这是否仍然算作筛子。

实际上，这对maxnum = 39312312323123123. 使用素数定理，我们可以估计1,028,840,332,567,181在该范围内大约有素数。

正如在这个问题中指出的那样，32 位系统上 python 列表的最大大小是536,870,912. 所以即使你没有耗尽内存，你仍然无法完成计算。

不过，64 位系统不应该有这个问题。

2 ** 64 => 18446744073709551616

使用上述问题的数学计算(2 ** 64) / 8，列表中元素的最大数量将2,305,843,009,213,693,951大于您将遇到的估计素数数量。

编辑：

为避免内存问题，您可以将素数列表存储在硬盘上的文件中。每行存储一个素数并在每次检查新数字时读取文件。

也许是这样的：

primes_path = r'C:\temp\primes.txt'

def genPrimes():
    for line in open(primes_path, 'r'):
        yield int(line.strip())    

def addPrime(prime):
    primes_file = open(primes_path, 'a')
    primes_file.write('%s\n' % prime)
    primes_file.close()

def findPrimes(maxnum):
    for i in xrange(2, maxnum):
        is_mul = False
        for prime in genPrimes():  # generate the primes from a file on disk
            if i % prime == 0:
                is_mul = True    
                break            
        if not is_mul:           
            addPrime(i)  # append the new prime to the end of your primes file

最后，您的硬盘驱动器上会有一个包含所有素数的文件。

好的，所以这会很慢，但你不会用完内存。您可以通过提高读取/写入文件的速度（如RAID）来使其更快。

于 2010-02-25T21:56:56.107 回答