超过python中列表的大小

这是一个更复杂的算法,也许技术上不算筛子,但一种方法是不一次删除给定素数的所有倍数,而是将下一个倍数(连同素数)排队。这可以在生成器实现中使用。队列最终仍将包含大量(倍数)素数,但没有构建然后过滤列表所包含的素数那么多。

• 2是素数-产量和队列(4,2)
• 3是素收益率和排队(6,3)
• 4是复合的-将队列中的(4,2)替换为(6,2)
• 5是优等收益率和排队(10,5)

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

为了在Python中有效地处理队列,我建议使用一个由元组的第一项设置键的字典(即hashtable)。数据是一组第二项值(原始素数)。

我会说,“使用 xrange() 相反,您实际上使用int列表作为筛选结果。。。。。所以整数生成器不是正确的解决方案。

试试这个。

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

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

在(1010010001000010000000000…)中绘制运行maxnum所需的时间,您可以推断3931232323所需的时间:)

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.

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

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

注意 :我不是Python程序员。不知道如何实现我在Python中所说的。也许我不知道这里的来龙去脉,所以如果我被否决了,我会理解的。

或许可以使用“ generators linked list .

试试这个:

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 . 使用 Prime number theorem 我们可以估计大约 1,028,840,332,567,181

正如在 this question 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