Python OverflowError : 'long'을 인덱스에 맞출 수 없습니다. = 크기의 정수

Question

온라인에서 찾은 알고리즘을 사용하여 두 개의 큰 소수를 생성하고 약간 변경했습니다.

나는 5 행에이 오류를 얻을 :

Python OverflowError: cannot fit 'long' into an index=sized integer 

내 코드 :

import math 
def atkin(end): 
    if end < 2: return [] 
    lng = ((end/2)-1+end%2) 
    **sieve = [True]*(lng+1)** 
    for i in range(int(math.sqrt(end)) >> 1): 
     if not sieve[i]: continue 
     for j in range((i*(i + 3) << 1) + 3, lng, (i << 1) + 3): 
      sieve[j] = False 
    primes = [2] 
    primes.extend([(i << 1) + 3 for i in range(lng) if sieve[i]]) 
    return primes 

가 어떻게 내 오류를 해결할 수 ?

큰 소수를 생성하는 더 좋은 방법을 알고 있다면 도움이 될 것입니다.

Answer 1

다음 코드는 당신이로 실행하는 문제를 보여줍니다. 대신 다음과 같이하십시오 :

x = [True]*(sys.maxint) 

MemoryError이 표시됩니다.

다음은 무슨 일입니까? 파이썬은 자체 확장 가능한 데이터 유형을 가진 임의의 큰 정수를 처리 할 수 ​​있습니다. 그러나 위와 같은 목록을 만들려고하면 Python은 작은 목록이 반복되는 횟수 (Python 정수)를 Py_ssize_t 유형의 C 정수로 변환하려고 시도합니다. Py_ssize_t는 빌드에 따라 다르게 정의되지만 ssize_t, long 또는 int가 될 수 있습니다. 본질적으로, 파이썬은 변환을하기 전에 파이썬 정수가 C 정수형에 들어갈 수 있는지를 검사하고, 작동하지 않으면 오버플로 오류를 발생시킵니다.

Answer 2

라인 5는 True 값으로 가득 찬 정말로 긴 목록을 할당합니다. 아마도 lng이 너무 커서 메모리 목록에 맞지 않을 수 있습니까?

정확하게 오류를 재현하지 못했습니다. 최악의 경우에 나는 단지 MemoryError로 끝났습니다.

아마도 알고리즘은 괜찮습니다 (비록 내가 내기 할 수는 없지만). 더 작은 숫자를 시도하십시오. OverflowError 산출

import sys 
x = [True]*(sys.maxint+1) 

: