Диапазон слишком велик Python

Question

Я пытаюсь найти наибольший простой множитель числа x, Python выдает ошибку, что диапазон слишком велик. Я пытался использовать x range, но я получаю OverflowError: Python int слишком большой, чтобы преобразовать его в C long

x = 600851475143
maxPrime = 0


for i in range(x):
    isItPrime = True
    if (x%i == 0):
        for prime in range(2,i-1):
            if (i%prime == 0):
                isItPrime = False
        if (isItPrime == True):

            if (i > maxPrime):
                maxPrime = i;

print maxPrime

Answer 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

Answer 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))

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

Answer 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

Answer 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

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

РЕДАКТИРОВАТЬ: Я также сделал еще несколько правок, чтобы получитьэта версия.Это довольно эффективно, и я проверил довольно много цифр, которые эта программа предоставляет (кажется, проверяет до сих пор):

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]

Answer 5

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

Для 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

Последнее простое число является последним напечатанным значением.