Python “OverflowError”

Je commence tout juste à apprendre à coder en Python. Je suis en train d'écrire un peu de code pour répondre à ce Projet Euler Question:

Les facteurs premiers de 13195 sont 5, 7, 13 et 29.

Ce qui est le plus grand facteur premier de le nombre 600851475143 ?

Mon programme fonctionne avec les cas de test de 13195, mais quand j'essaie d'entrer 600851475143, j'obtiens l'erreur: "OverflowError: range() résultats a trop d'éléments"
Personne ne sait comment je peux résoudre ce problème?

Voici mon code:

class Euler3:
    "A class to find the largest prime factor of a given number"
     n = 600851475143
     primeFactors = []
     for i in range(2,n):
         if (n%i ==0):
            primeFactors.append(i)
            n = n/i
            i = i -1 #reset i
     print primeFactors

Toute aide ou suggestion serait bien apprécié!

Vous le faites mal. Pour chaque facteur de x, il y a un autre facteur y tels que x*y = num. Si x dans le n-ième plus petit facteur, y sera le n-ième facteur le plus important (la preuve de ceci est un exercice laissé au lecteur). Trouver le plus petit facteur x, et ne y = num/x. Si y est premier, c'est votre numéro, si non, continuez. Aussi, x est sensiblement plus petit que sqrt(num), de sorte que vous pouvez réduire votre range() un peu.

OriginalL'auteur Erica Dohring | 2012-05-28

overflow python

17

La range fonction crée une liste et tente de le stocker dans la mémoire. Création d'une liste du nombre de numéros longtemps est la cause de la OverflowError. Vous pouvez utiliser xrange au lieu d'obtenir un générateur qui produit l'un des numéros sur la demande.

Cela dit, je pense que vous trouverez que votre algorithme est beaucoup trop lent pour le calcul de grands nombres premiers. Il y a beaucoup de nombre premier algorithmes, mais j'ai peut proposer de vérifier la Crible d'Eratosthène comme un point de départ.

EDIT: Correctement xrange ne fait pas de retour d'un générateur, mais un xrange objet qui se comporte un peu comme un générateur. Je ne sais pas si vous vous en souciez, mais il était sur écoute-moi que je n'étais pas précis!

Merci beaucoup! C'est de l'information utile. J'ai juste regardé le Crible d'Eratosthène et je suis actuellement en train de travailler sur mon deuxième projet. Merci d'avoir pris le temps de répondre à ma question!

OriginalL'auteur
4

Je devine que vous êtes à l'aide de python 2 et pas de python 3 -- range(2,n) effectivement construit une liste! Vous n'avez pas assez de mémoire pour stocker les 600 milliards de chiffres! xrange devrait être bon, cependant.

Aussi, votre idée de i=i-1 ne fonctionne pas. Pour les boucles ne fonctionnent pas comme en C, et que le hack ne fonctionne que dans le style C boucles. La boucle for parcourt range(2,n). Si i obtient la valeur 5 à la fois itération, alors peu importe ce que vous faites pour i, il obtient toujours 6 la prochaine fois.

Aussi, la liste range(2,n) est construit lorsque vous entrez dans la boucle. Ainsi, lorsque vous modifiez n, ça ne change rien.

Vous allez avoir à repenser votre logique un peu.

(si vous ne me croyez pas, essayez d'utiliser 175 comme un cas de test)

Un dernier commentaire, vous devriez probablement obtenir dans l'habitude de l'aide de la division entière: n = n //i. Bien que / et // les mêmes en python 2, qui est vraiment obsolète de comportement, et ils ne travaillent pas de la même chose en python 3, où / vous donnera un nombre à virgule flottante.

Merci pour le commentaire à propos de la boucle for. Ma principale langue de programmation Java, qui est un peu comme C dans le fait que vous pouvez réinitialiser les boucles de faire des choses comme i = i - 1. C'est utile de savoir que cela ne fonctionne pas en Python. Merci!!!!

OriginalL'auteur
4

Vous pouvez résoudre le problème en utilisant xrange au lieu de range

Votre prochain problème sera que le programme prend beaucoup trop de temps à s'exécuter parce que vous avez besoin de sortir de la boucle sous certaines condition

Une meilleure façon de traiter avec la répétition des facteurs est de remplacer le if avec un while
```
     while (n%i ==0):
        primeFactors.append(i)
        n = n/i
```
Dans ce cas, elle aura de la chance et ça va se terminer rapidement. (lorsqu'elle fixe la logique)
Je vais essayer ça. Merci!!!!
vous êtes la plupart de bienvenue

OriginalL'auteur
2
```
n = 600851475143
primeFactors = []
for i in range(2,n):
```
je pense que vous pouvez optimiser la fonction, en remarquant que
```
for i in range(2,n):
```
vous pouvez remplacer
```
range(2,n)
```
par
```
range(2,int(sqrt(n))+2)
```
car, vous pouvez voir wiki...

OriginalL'auteur

C'est la meilleure façon de trouver des nombres premiers que j'ai trouvé jusqu'à présent:

def isprime(n):
    #make sure n is a positive integer
    n = abs(int(n))
    #0 and 1 are not primes
    if n < 2:
        return False
    #2 is the only even prime number
    if n == 2:
        return True
    #all other even numbers are not primes
    if not n & 1:
        return False
    #range starts with 3 and only needs to go up to the square root of n
    #for all odd numbers
    for x in range (3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True #if it makes it through all the catches, it is a prime

OriginalL'auteur

Ce qui m'a pris environ 5 secondes pour trouver la réponse.

import math

def is_prime_number(x):
   for i in range(int(math.sqrt(x)), 2, -1):
      if x % i == 0:
        return False
   return True

def next_prime_number(number):
    #Returns the next prime number.
    if number % 2 == 0 and number != 2:
        number += 1
    while not is_prime_number(number):
        number += 2
    return number

num = 600851475143
i = 2
while (i < long(math.sqrt(num) / 2)):
    if num % i == 0:
       largest = i
       print largest
    i = next_prime_number(i + 1)

OriginalL'auteur

1

xrange ne serez pas probablement vous aider(ou il peut!),mais la clé ici est de reliaze que vous n'avez pas besoin de trouver les nombres premiers jusqu'à 600851475143 ou les facteurs de 600851475143,mais c'est le premier des facteurs,donc...
Utiliser la bonne vieille méthode de factorisation ,comme suit:
```
A=600851475143
n=2
fac=[]
while(n<=int(A)):
    B=1
    while(A%n==0):
        B=0   
        A=A/n
    if(B==0):
        fac.append(n)
    n=n+1

print max(fac)
```
Ce sera le retour de la argest premier facteur presque instantanément

OriginalL'auteur

J'ai été aux prises avec ce Python "OverflowError", ainsi, en travaillant sur ce projet. Il a été me rend fou en essayant de trouver une combinaison qui fonctionne.

Cependant, je n'ai découvert un d'intelligent, au moins je pense que oui :), la façon de le faire.

Voici mon code pour ce problème.

def IsNumberPrime(n):
   bounds = int(math.sqrt(n))
   for number in xrange(2,bounds+2):
        if n % number == 0:
            return False
   return True

def GetListOfPrimeFactors(n):
    primes = []
    factors = GetListOfFactors(n)
    if n % 2 == 0:
       primes.append(2)

    for entries in factors:
       if IsNumberPrime(entries):
          primes.append(entries)
    return primes


GetListOfPrimeFactors(600851475143)

def GetListOfFactors(n):
   factors = []
   bounds = int(math.sqrt(n))
   startNo = 2

   while startNo <= bounds:
      if n % startNo == 0:
         factors.append(startNo)
      startNo += 1
   return factors

Ce que j'ai fait était de prendre les facteurs du nombre entré et entrez dans une liste des "facteurs". Après cela, je prends la liste de facteurs et de déterminer celles qui sont les nombres premiers et de les stocker dans une liste, qui est imprimé.

J'espère que cette aide

-- Mike

OriginalL'auteur

Vous devez vous connecter pour publier un commentaire.