python - 这个主要功能真的有效吗？

Question

自从我开始掌握 Python 的窍门以来，我开始在 projecteuler.net 上测试我新学到的 Python 技能并解决一些问题。

无论如何，在某些时候，我最终创建了一个函数来获取所有素数的列表，直到数字“n”为止。

这是函数在 atm 中的样子:

def primes(n):
    """Returns list of all the primes up until the number n."""

    # Gather all potential primes in a list.
    primes = range(2, n + 1)
    # The first potential prime in the list should be two.
    assert primes[0] == 2
    # The last potential prime in the list should be n.
    assert primes[-1] == n

    # 'p' will be the index of the current confirmed prime.
    p = 0
    # As long as 'p' is within the bounds of the list:
    while p < len(primes):
        # Set the candidate index 'c' to start right after 'p'.
        c = p + 1
        # As long as 'c' is within the bounds of the list:
        while c < len(primes):
            # Check if the candidate is divisible by the prime.
            if(primes[c] % primes[p] == 0):
                # If it is, it isn't a prime, and should be removed.
                primes.pop(c)
            # Move on to the next candidate and redo the process.
            c = c + 1
        # The next integer in the list should now be a prime, 
        # since it is not divisible by any of the primes before it. 
        # Thus we can move on to the next prime and redo the process.
        p = p + 1       
    # The list should now only contain primes, and can thus be returned.
    return primes

它似乎工作正常，尽管有一件事困扰着我。评论代码的时候，突然觉得这一段不对:

# Check if the candidate is divisible by the prime.
if(primes[c] % primes[p] == 0):
    # If it is, it isn't a prime, and should be removed from the list.
    primes.pop(c)
# Move on to the next candidate and redo the process.
c += 1

如果候选项不能被素数整除，我们将检查位于“c + 1”的下一个候选项。没问题。

但是，如果候选项可以被素数整除，我们首先弹出它，然后检查位于“c + 1”的下一个候选项。令我震惊的是，下一个候选人在弹出后，不位于 'c + 1'，而是位于 'c'，因为在 'c' 弹出后，下一个候选人“落入”该索引。

然后我认为该 block 应该如下所示:

# If the candidate is divisible by the prime:
if(primes[c] % primes[p] == 0):
    # If it is, it isn't a prime, and should be removed from the list.
    primes.pop(c)
# If not:
else:
    # Move on to the next candidate.
    c += 1

上面的 block 对我来说似乎更正确，但让我想知道为什么原来的 block 显然工作得很好。

所以，这是我的问题:

在弹出一个不是素数的候选项后，我们可以假设下一个候选项不能被同一个素数整除吗？

如果是，那是为什么？

建议的“安全”代码是否会对在“不安全”代码中跳过的候选人进行不必要的检查？

附言:

我尝试将上述假设作为断言写入“不安全”函数，并使用 n = 100000 对其进行测试。没有出现任何问题。这是修改后的 block :

# If the candidate is divisible by the prime:
if(primes[c] % primes[p] == 0):
    # If it is, it isn't a prime, and should be removed.
    primes.pop(c)
    # If c is still within the bounds of the list:
    if c < len(primes):
        # We assume that the new candidate at 'c' is not divisible by the prime.
        assert primes[c] % primes[p] != 0
# Move on to the next candidate and redo the process.
c = c + 1

Answer 1

它对更大的数字失败。第一个素数是71，因为候选人可能会失败。 71 的最小失败候选者是 10986448536829734695346889，它盖过了数字 10986448536829734695346889 + 142。

def primes(n, skip_range=None):
    """Modified "primes" with the original assertion from P.S. of the question.
    with skipping of an unimportant huge range.
    >>> primes(71)
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
    >>> # The smallest failing number for the first failing prime 71:
    >>> big_n = 10986448536829734695346889
    >>> primes(big_n + 2 * 71, (72, big_n))
    Traceback (most recent call last):
    AssertionError
    """
    if not skip_range:
        primes = list(range(2, n + 1))
    else:
        primes = list(range(2, skip_range[0]))
        primes.extend(range(skip_range[1], n + 1))
    p = 0
    while p < len(primes):
        c = p + 1
        while c < len(primes):
            if(primes[c] % primes[p] == 0):
                primes.pop(c)
                if c < len(primes):
                    assert primes[c] % primes[p] != 0
            c = c + 1
        p = p + 1
    return primes

# Verify that it can fail.
aprime = 71   # the first problematic prime 
FIRST_BAD_NUMBERS = (
        10986448536829734695346889, 11078434793489708690791399,
        12367063025234804812185529, 20329913969650068499781719,
        30697401499184410328653969, 35961932865481861481238649,
        40008133490686471804514089, 41414505712084173826517629,
        49440212368558553144898949, 52201441345368693378576229)

for bad_number in FIRST_BAD_NUMBERS:
    try:
        primes(bad_number + 2 * aprime, (aprime + 1, bad_number))
        raise Exception('The number {} should fail'.format(bad_number))
    except AssertionError:
        print('{} OK. It fails as is expected'.format(bad_number))

我通过搜索 n 个对小素数取模的可能余数，通过像拼图一样复杂的算法解决了这些数字。最后一个简单的步骤是得到完整的n(通过三行Python代码中的中国剩余定理)。我知道所有 120 个小于 primorial (71) = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 定期重复这个数字的所有倍数。对于每十年的测试素数，我都多次重写算法，因为每十年的解决方案都比前一个慢得多。也许我可以在可接受的时间内用相同的算法为素数 73 或 79 找到一个更小的解决方案。

---

编辑:

我还想找到不安全原始函数的完全静默失败。也许存在一些由不同素数组成的候选者。这样的解决方式，只会将最终的结果推迟到以后。每一步都将花费越来越多的时间和资源。因此，只有由一个或两个质数组成的数字才具有吸引力。

我希望隐藏的候选者 c 只有两个解决方案是好的:c = p ** n 或 c = p1 * p ** n 或 c = p1 ** n1 * p ** n 其中 p 和 p1 是素数，n是大于 1 的幂。如果 c - 2 * p 不能被小于 p 的素数整除，并且如果所有数c-2n 和 c 之间可以被任何小于 p 的素数整除。变体 p1*p**n 还要求相同的 c 在 p1 (p1 < p) 之前失败，因为我们已经知道无限此类候选人的数量。

编辑:我发现了一个失败的较小的例子:素数 79 的数字 121093190175715194562061。(大约是 71 的九十倍)我无法继续通过相同的算法找到更小的示例，因为所有 702612 基本解决方案在我的笔记本电脑上花费了 30 多个小时用于素数 79。

我还针对所有小于 400000000 (4E10) 的候选者和所有相关素数验证了它，没有任何候选者会在问题中的断言中失败。直到你有 TB 的内存和数千年的时间，算法中的断言才会通过，因为你的时间复杂度是 O((n/log(n)) ^2) 或非常相似。