Python OverflowError: ne peut pas être "long" dans un index=taille entier
Je veux générer deux très grands nombres premiers en utilisant un algorithme que j'ai trouvé en ligne et légèrement modifiée.
J'ai cette erreur à la ligne 5:
Python OverflowError: cannot fit 'long' into an index=sized integer
Mon code:
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
Comment puis-je réparer mon erreur?
Si vous connaissez un meilleur moyen de générer de grands nombres premiers, qui pourrait être utile aussi.
Avez-vous essayé ce code pour de petits nombres? Si vous souhaitez utiliser les grands nombres, vous devriez essayer de gmplib.org de la bibliothèque. Il y a un Python wrappers pour cette bibliothèque et il a bien fonctionné pour moi.
Ouais le code fonctionne très bien pour les petits nombres. J'ai vérifié les nombres premiers entre 1 et 100 et c'était correct. Merci pour le lien, si, je vais vérifier.
Il y a un certain nombre de façons d'obtenir de plus grands nombres premiers rapidement à l'aide de cet algorithme discuté ici: stackoverflow.com/questions/2897297/...
Ouais le code fonctionne très bien pour les petits nombres. J'ai vérifié les nombres premiers entre 1 et 100 et c'était correct. Merci pour le lien, si, je vais vérifier.
Il y a un certain nombre de façons d'obtenir de plus grands nombres premiers rapidement à l'aide de cet algorithme discuté ici: stackoverflow.com/questions/2897297/...
OriginalL'auteur Rell3oT | 2011-01-20
Vous devez vous connecter pour publier un commentaire.
Le code suivant illustre le problème que vous rencontrez:
qui donne une
OverflowError
. Si vous au lieu de faire:alors vous devriez obtenir un
MemoryError
.Voici ce qui se passe. Python peut manipuler arbitrairement grands entiers avec sa propre extensible type de données. Toutefois, lorsque vous essayez de faire une liste comme ci-dessus, Python essaie de convertir le nombre de fois que la petite liste est répétée, ce qui est un Python entier, une C entier de type Py_ssize_t. Py_ssize_t est défini différemment selon votre construire, mais peut être un ssize_t, long ou int. Essentiellement, Python vérifie si le Python entier peuvent s'adapter dans le C de type entier avant de faire la conversion et la pose de la OverflowError si elle ne fonctionne pas.
sys.maxsize
au lieu desys.maxint
OriginalL'auteur Justin Peel
Ligne 5 trues d'allouer une très longue liste complète des
True
valeurs. Probablement votrelng
est trop grand pour tenir cette liste à la mémoire?Je n'étais pas en mesure de reproduire avec exactitude votre erreur; dans le pire des cas j'ai fini vers le haut avec juste un
MemoryError
à la place.Probablement l'algorithme est ok (même si je ne peux pas parier), juste essayer un plus petit nombre.
OriginalL'auteur 9000