Python 2 查找素数的正整数列表

Question

给定 2 个正整数列表，找出有多少种方法可以从每个列表中选择一个数字，使得它们的和为质数。

我的代码太慢了，因为我有 list1 和 list 2，每个都包含 50000 个数字。那么有什么方法可以让它更快，以便在几分钟而不是几天内解决它？ :)

    # 2 is the only even prime number
    if n == 2: return True

    # all other even numbers are not primes
    if not n & 1: return False

    # range starts with 3 and only needs to go 
    # up the squareroot of n for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0: return False

    return True



for i2 in l2:
    for i1 in l1:
        if isprime(i1 + i2):
            n = n + 1 # increasing number of ways
            s = "{0:02d}: {1:d}".format(n, i1 + i2)
            print(s) # printing out

Answer 1

素描:

1. 按照@Steve 的建议，首先找出所有素数 <= max(l1) + max(l2)。我们称该列表为 primes。注意:primes 并不需要是一个列表；你可以改为 generate primes up the max一次一个。

2. 交换列表(如有必要)，使 l2 成为最长的列表。然后把它变成一个集合:l2 = set(l2)。

3. 排序 l1 (l1.sort())。

然后:

for p in primes:
    for i in l1:
        diff = p - i
        if diff < 0:
            # assuming there are no negative numbers in l2;
            # since l1 is sorted, all diffs at and beyond this
            # point will be negative
            break
        if diff in l2:
           # print whatever you like
           # at this point, p is a prime, and is the
           # sum of diff (from l2) and i (from l1)

唉，如果 l2 是，例如:

l2 = [2, 3, 100000000000000000000000000000000000000000000000000]

这是不切实际的。它依赖于此，如您的示例所示，max(max(l1), max(l2)) 是“相当小”。

充实

嗯!您在评论中说列表中的数字最多为 5 位数字。所以他们不到100,000。你在开始时说过每个列表有 50,000 个元素。因此，它们每个都包含 100,000 以下所有可能整数的大约一半，并且您将拥有非常大量的素数和。如果您想进行微优化，这一切都很重要；-)

无论如何，由于最大可能总和小于 200,000，任何 筛选方法都足够快 - 这将是运行时的一个微不足道的部分。这是其余的代码:

def primesum(xs, ys):
    if len(xs) > len(ys):
        xs, ys = ys, xs
    # Now xs is the shorter list.
    xs = sorted(xs)  # don't mutate the input list
    sum_limit = xs[-1] + max(ys)  # largest possible sum
    ys = set(ys)     # make lookups fast
    count = 0
    for p in gen_primes_through(sum_limit):
        for x in xs:
            diff = p - x
            if diff < 0:
                # Since xs is sorted, all diffs at and
                # beyond this point are negative too.
                # Since ys contains no negative integers,
                # no point continuing with this p.
                break
            if diff in ys:
                #print("%s + %s = prime %s" % (x, diff, p))
                count += 1
    return count

我不会提供我的 gen_primes_through()，因为它无关紧要。从其他答案中选择一个，或写下您自己的答案。

这是提供测试用例的便捷方式:

from random import sample
xs = sample(range(100000), 50000)
ys = sample(range(100000), 50000)
print(primesum(xs, ys))

注意:我使用的是 Python 3。如果您使用的是 Python 2，请使用 xrange() 而不是 range()。

在两次运行中，每次运行大约需要 3.5 分钟。这就是您在开始时要求的(“分钟而不是天”)。 Python 2 可能会更快。返回的计数是:

219,334,097

和

219,457,533

当然，可能的总数是 50000**2 == 2,500,000,000。

关于时间

所有 此处讨论的方法(包括您原来的方法)所花费的时间与两个列表长度的乘积成正比。所有的摆弄都是为了减少常数因子。这是对您的原始版本的巨大改进:

def primesum2(xs, ys):
    sum_limit = max(xs) + max(ys)  # largest possible sum
    count = 0
    primes = set(gen_primes_through(sum_limit))
    for i in xs:
        for j in ys:
            if i+j in primes:
                # print("%s + %s = prime %s" % (i, j, i+j))
                count += 1
    return count

也许你会更好地理解这一点。为什么是巨大的进步？因为它用超快的集合查找替换了昂贵的 isprime(n) 函数。它仍然需要与 len(xs) * len(ys) 成正比的时间，但是通过用非常便宜的操作替换非常昂贵的内部循环操作来大幅削减“比例常数”。

事实上，primesum2() 在很多情况下也比我的 primesum() 快。使 primesum() 在您的特定情况 中更快的原因是只有大约 18,000 个素数小于 200,000。因此，遍历素数(如 primesum() 所做的那样)比遍历包含 50,000 个元素的列表要快得多。

针对此问题的“快速”通用函数需要根据输入选择不同的方法。