pha*_*haz 16 python algorithm math primes python-2.7
由于我开始掌握Python,我开始在projecteuler.net上测试我新获得的Python技能.
无论如何,在某些时候,我最终制作了一个函数,用于获取所有素数的列表,直到数字'n'.
以下是该函数的外观:
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'弹出后,下一个候选人"落入"该指数.
然后我认为该块应如下所示:
# 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
上面的这个块对我来说似乎更正确,但让我想知道为什么原始部分显然工作得很好.
所以,这是我的问题:
弹出一个原来不是素数的候选人之后,我们可以假设,正如我的原始代码中那样,下一个候选人不能被同一个素数整除吗？
如果是这样,为什么呢？
建议的"安全"代码是否会对那些在"不安全"代码中跳过的候选人进行不必要的检查？
PS:
我已经尝试将上述假设写成'不安全'函数的断言,并用n = 100000进行测试.没有出现问题.这是修改后的块:
# 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
hyn*_*cer 11
它失败了更大的数字.第一个素数是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 = p ** n或c = p1 * p ** n或c = p1 ** n1 * p ** n其中,p和P1是素数ñ是一个功率大于1的素数,如果函数失败c - 2 * p是比不小的素数整除p,如果之间的所有号码C- 2n和c可被任何小于p的素数整除.变体p1*p**n还需要在p1之前相同的c失败(p1 <p),因为我们已经知道无数个这样的候选者.
编辑:我找到了一个较小的失败示例:编号为121093190175715194562061为79.(比71少了约九十倍)我无法通过相同的算法继续寻找更小的例子,因为所有702612基本解决方案都花了30多个在我的笔记本电脑上79小时的时间.
我还对所有小于400000000(4E10)的候选人以及所有相关的素数进行了验证,没有候选人会在问题中失败.直到你有数TB的内存和数千年的时间,算法中的断言才会通过,因为你的时间复杂度是O((n/log(n))^ 2)或非常相似.