Question

Python Question:

I am trying to use xrange to determine the factors of a number. However the number is too big and I am getting an Overflow Error. Is there a way to iterate without creating a list.
t = 600851475143
for x in xrange(1,600851475143):
if t % x == 0:
list.append(x)

Answer 1

t = 600851475143
x = 1
while x < 600851475143:
if t % x == 0:
list.append(x)
x += 1

Maybe that'd work?

Answer 2

Thanks!

Answer 3

I think it is going to work, but it is taking a long long time to calculate. I wonder if there is a more efficient way to calculate factors.

Answer 4

Try a different way, like this:

t = 600851475143.0
x = 2

while t % x != 0:
x += 1

print t / x

Answer 5

Opps, that would just give you the highest factor.

Answer 6

import math

number = 600851475144

factors = []

limit = int(math.sqrt(number)) + 1

if (number % 2) == 0:
factors.append(2)

currentNumber = 3
while currentNumber < limit:
if (number % currentNumber) == 0:
factors.append(currentNumber)
currentNumber += 1

print factors

the idea is that you only need to check up to the square root of the number because you wont find any factors after it

Answer 7

That's a better answer, knowing the math behind it certainly helps.