Python «OverflowError»

Я только начинаю учиться кодировать на Python. Я пытаюсь написать код для ответа на вопрос Project Euler:

Основными факторами 13195 являются 5, 7, 13 и 29.

Что является самым большим основным фактором числа 600851475143?

Моя программа работает с тестовым набором 13195, но когда я пытаюсь ввести 600851475143, я получаю сообщение об ошибке: & quot; OverflowError: range () result имеет слишком много элементов & quot; Кто-нибудь знает, как я могу это исправить?

Вот мой код:

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

Любая помощь или предложения будут высоко оценены!

 WhyNotHugo17 сент. 2015 г., 22:35
Вы делаете это неправильно. Для каждого фактораxесть еще один факторy такой, чтоx*y = num, Еслиx в n-м наименьшем факторе,y будет n-м по величине фактором (доказательство того, что это упражнение оставлено читателю). Найдите самый маленький факторx, и делатьy = num/x, Еслиy простое, это ваш номер, если нет, продолжайте. Также,x значительно меньше, чемsqrt(num), так что вы можете уменьшить свойrange() немного.

Ответы на вопрос(8)

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
n = 600851475143
primeFactors = []
for i in range(2,n):

for i in range(2,n):

Вы можете заменить

range(2,n)

от

range(2,int(sqrt(n))+2)

потому что вы можете увидеть вики ...

Вы можете решить проблему с помощьюxrange вместоrange

Ваша следующая проблема будет в том, что программа слишком долго запускается, потому что вам нужно выйти из цикла при некоторых условиях

Лучший способ справиться с повторяющимися факторами - это заменитьif сwhile

     while (n%i ==0):
        primeFactors.append(i)
        n = n/i
 Erica Dohring30 мая 2012 г., 19:44
Я попробую это. Спасибо!
 28 мая 2012 г., 04:43
В этом случае ей повезет, и она быстро закончится. (когда она исправляет логику)
 30 мая 2012 г., 23:43
@EricaDohring, пожалуйста

вероятно, не поможет вам (или может!), но главное здесь состоит в том, чтобы подтвердить, что вам не нужно находить простые числа до 600851475143 или множители 600851475143, но это главные факторы, поэтому ... Используйте старый добрый простой метод факторизации, например, так:

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)

Это вернет самый главный фактор почти мгновенно

range(2,n) на самом деле строит список! У вас недостаточно памяти для хранения 600 миллиардов номеров!xrange должно быть хорошо, хотя.

Кроме того, ваша идеяi=i-1 не работает. Циклы for не работают как C, и этот хак работает только в циклах в стиле C. Цикл for повторяетсяrange(2,n), Еслиi получает значение5 сразу итерация, тогда неважно, что вы делаетеi, он все еще получает6 в следующий раз до конца.

Также списокrange(2,n) создается при входе в цикл. Поэтому, когда вы модифицируетеn, это ничего не меняет.

Вам придется немного переосмыслить свою логику.

(если вы мне не верите, попробуйте использовать 175 в качестве контрольного примера)

В качестве последнего комментария вы, вероятно, должны привыкнуть использовать специальное целочисленное деление:n = n // i, Хотя/ а также// работают одинаково в Python 2, это действительно устаревшее поведение, и они не работают одинаково в Python 3, где/ даст вам число с плавающей запятой.

 Erica Dohring30 мая 2012 г., 19:43
Спасибо за комментарий о цикле for. Мой основной язык кодирования - Java, который во многом похож на C в том смысле, что вы можете сбрасывать циклы, выполняя такие вещи, как i = i - 1. Это полезно знать, что это не работает в Python. Спасибо!

работая над этим проектом. Это сводило меня с ума, пытаясь придумать комбинацию, которая сработала.

Тем не менее, я нашел умный, по крайней мере, я так думаю :), способ сделать это.

Вот мой код для этой проблемы.

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

Что я сделал, так это взял факторы введенного числа и занес их в список «факторов». После этого я беру список факторов и определяю, какие из них являются простыми, и сохраняю их в виде списка, который печатается.

надеюсь, это поможет

- Майк

range Функция создает список и пытается сохранить его в памяти. Создание списка, состоящего из нескольких чисел, является причиной ошибки OverflowError. Ты можешь использоватьxrange вместо этого, чтобы получить генератор, который производит числа по требованию.

Тем не менее, я думаю, вы обнаружите, что ваш алгоритм слишком медленный для вычисления больших простых чисел. Есть много алгоритмов простых чисел, но я мог бы предложить проверитьСито Эратосфена в качестве отправной точки.

РЕДАКТИРОВАТЬ: правильноxrange на самом деле не возвращает генератор, но объект xrange, который ведет себя очень похоже на генератор. Я не уверен, что вы заботитесь, но меня беспокоило, что я не был точен!

 Erica Dohring30 мая 2012 г., 19:43
Большое спасибо! Это полезная информация. Я только что посмотрел сито Эратосфена и сейчас работаю над своим вторым проектом. Спасибо, что нашли время ответить на мой вопрос!

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)

Ваш ответ на вопрос