Python에서 MemoryError 직면

나는 숫자의 소인수를 찾는 프로그램을 작성했습니다. 큰 숫자 (600851475143)를 입력하면 MemoryError가 나타납니다. 다음은 코드입니다.

def fact(a): factors = [] for i in range(1,a+1): if a%i == 0: factors.append(i) return factors num = raw_input(">> ") #600851475143 a = b = [] a = fact(long(num)) for i in range(0,len(a)): b = fact(a[i]) if len(b) <= 2: print a[i] 

탐색을 통해 Python이 컴퓨터 메모리 (RAM)를 사용한다는 것을 알게되었습니다. 구성을 변경하지 않고 Unbuntu에서 Python을 사용하고 있습니다. 64 비트 컴퓨터에서 작동하도록 anythig를 변경해야합니까? 또는이 오류를 해결하기 위해 추가 기능을 사용해야합니까?

댓글

• 기본 문제는 알고리즘이 너무 많이 사용하고 있다는 것입니다. 기억. Python 2를 사용하는 경우 range(1, a+1)는 600851475143 요소가있는 목록을 생성하려고합니다. 각 요소가 정수이고 각 정수가 4 바이트를 차지하므로 이것은 아마도 원하는 것이 아닙니다. (또한이 질문은 ' 프로그래머에게 적합하지 않습니다. 실제로 코드 검토가 필요하고 특히 python의 작동 방식을 이해해야하기 때문입니다.)
• ( xrange-필요에 따라 요소를 for 루프로 반환하는 생성기입니다. 이것이 유일한 문제는 아닐 수도 있습니다. .)
• 목록은 2.2TB입니다. 64 비트 시스템으로 전환하는 것은 도움이되지 않습니다. 2TB 이상의 RAM을 설치해야합니다 (공정하게 사용하려면 64 비트 OS가 필요함). 또는 알고리즘을 다시 생각해보십시오.
• 기억 문제 외에도 (다른 사람이 지금까지 지적하지 않았기 때문에) 숫자의 요인 목록을 계산하거나 결정하는 데 더 효율적인 알고리즘이 있습니다. 숫자가 소수인지 여부 또는 소수 목록을 생성합니다. 대부분의 사람들이 시간 복잡성 에 대해 이야기하지만 공간 복잡성 과 관련된 개념도 있습니다.