Почему Python замедляет сканирование в этом коде?

Question

Так что я делаю проблему проекта Эйлера, пытаясь включить Сито Эратосфена, чтобы найти самый большой первичный коэффициент числа, однако, когда я пытаюсь заполнить свою начальную хэш-таблицу, он замедляет сканирование и съедает концерты на сумму ОЗУ и берет на себя мой процессор. Может ли кто-нибудь объяснить, почему? Я понимаю, что сам код, вероятно, является подпарам

allNums = {} 
maxNum=600851475143 
maxFactor=0 

#fill dictionary, slows to a crawl here 
for x in xrange(2,maxNum+1): 
    allNums[x]=True 

#sieve of Erastosthenes 
for x in xrange(2,len(allNums)): 
    y=x 
    if allNums[x]: 
     y **= 2 
     while y<=maxNum: 
      if allNums[y]: 
       allNums.pop(y) 
      y+=x 

#largest prime factor 
for x in allNums: 
    if maxNum%x==0 and x>maxFactor: 
     maxFactor=x 

print x 

Answer 1

Ну, вы выделяете огромный список (maxNum * 4 байта, справа)? Даже если это словарь и вы можете искать там сложность log (N), это все равно займет значительное время (и, что более важно, память). Такой огромный список может даже не вписаться в вашу оперативную память, поэтому ваша ОС должна будет имитировать дополнительную память (что будет означать еще большее время доступа, чтобы просто прочитать эти данные).

Кстати, так ваша задача может быть выполнена (не очень эффективная - занимает пару секунд на моей машине :)), но с идеей, подобной сите Eratosphene, за исключением небольшой оптимизации, а именно: продолжить, если x*x > maxNum.

maxNum=600851475143 

maxFactor=0 

x = 1 
while True: 
    (quotient, remainder) = divmod(maxNum, x) 
    if x>quotient: 
     break 
    if remainder==0: 
     maxFactor=x 
    x +=1 

print maxNum, maxFactor