Диапазон слишком большой Python

Ответ 1

В старых (2.x) версиях Python, xrange может обрабатывать только Python 2.x int s, которые привязаны собственным длинным целым размером вашей платформы. Кроме того, range заранее назначает список со всеми номерами на Python 2.x и поэтому непригоден для больших аргументов.

Вы можете либо переключиться на 3.x(рекомендуется), либо на платформу, где long int (на C) имеет длину 64 бит или использовать следующую вставку:

import itertools
range = lambda stop: iter(itertools.count().next, stop)

Эквивалентно, в простой форме:

def range(stop):
   i = 0
   while i < stop:
       yield i
       i += 1

Ответ 2

Это то, что я сделал бы:

def prime_factors(x):
    factors = []
    while x % 2 == 0:
        factors.append(2)
        x /= 2
    i = 3
    while i * i <= x:
        while x % i == 0:
            x /= i
            factors.append(i)
        i += 2
    if x > 1:
        factors.append(x)
    return factors

>>> prime_factors(600851475143)
[71, 839, 1471, 6857]

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

2017-11-08

Вернемся к этому 5 лет спустя, я бы использовал yield и yield from плюс более быстрый подсчет по простому диапазону:

def prime_factors(x):
    def diver(x, i):
        j = 0
        while x % i == 0:
            x //= i
            j += 1
        return x, [i] * j
    for i in [2, 3]:
        x, vals = diver(x, i)
        yield from vals
    i = 5
    d = {5: 2, 1: 4}
    while i * i <= x:
        x, vals = diver(x, i)
        yield from vals
        i += d[i % 6]
    if x > 1:
        yield x

list(prime_factors(600851475143))

В dict {5: 2, 1: 4} используется тот факт, что вам не нужно смотреть на все нечетные числа. Выше 3 все числа x % 6 == 3 кратны 3, поэтому вам нужно смотреть только на x % 6 == 1 и x % 6 == 5, и вы можете прыгать между ними, поочередно добавляя 2 и 4, начиная с 5.

Ответ 3

Принятый ответ предполагает замену замены для xrange, но охватывает только один случай. Вот более общая замена.

def custom_range(start=0,stop=None,step=1):
    '''xrange in python 2.7 fails on numbers larger than C longs.
    we write a custom version'''
    if stop is None:
        #handle single argument case. ugly...
        stop = start
        start = 0
    i = start
    while i < stop:
        yield i
        i += step

xrange=custom_range

Ответ 4

Я бы определенно придерживался xrange, так как создание списка между 0 и тем, что похоже на число, соперничаемое с бесконечностью, будет облагаться налогом на память. xrange будет генерировать только числа при запросе. Для слишком большой проблемы вы можете попробовать "длинный". Этого можно добиться, написав L в конце номера. Я сделал свою собственную версию, чтобы проверить ее. Я немного поспал, чтобы не уничтожить мой компьютер практически в цикле while(1). Я также был неспособен увидеть, что программа подходит к концу, поэтому я печатаю заявления

from time import sleep

x = 600851475143L
maxPrime = 0

for i in xrange(1,x):
    isItPrime = True
    if (x%i) == 0:
        for prime in xrange(2,i-1):
            if (i%prime) == 0:
                isItPrime = False
                break
        if isItPrime:
            maxPrime = i
            print "Found a prime: "+str(i)
    sleep(0.0000001)


print maxPrime

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

EDIT: Я также сделал несколько дополнительных изменений для этой версии. Это довольно эффективно, и я проверил немало номеров, которые эта программа предоставляет (кажется, до сих пор проверяется):

from time import sleep

x = 600851475143L

primes = []

for i in xrange(2,x):
    isItPrime = True
    for prime in primes:
        if (i%prime) == 0:
            isItPrime = False
            break
    if isItPrime:
        primes.append(i)
        print "Found a prime: "+str(i)
    sleep(0.0000001)


print primes[-1]

Ответ 5

Очень неопределенный код, это не лучший способ получить разделители, я сделал это с помощью for и range, но я не могу выполнить его из-за длинных переменных, поэтому я решил реализовать его с помощью a для использования while и приращения счетчика.

Для 32-битного int как 13195:

# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?

i = 13195
for j in xrange(2, i, 1):
    if i%j == 0:
        i = i/j
        print j

Хороший способ для более длинных номеров:

# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?

i = 600851475143
j = 2

while i >= j:
    if i%j == 0:
        i = i/j
        print j
    j = j+1

Последний штрих - это последнее напечатанное значение.