When substituting x
in the get_large
function with a large integer such as 600851475143 the program stalls and doesn't return a value. But, when substituting x
with a smaller integer such as 20 it returns the result. How can I fix this?
factors = [] # create new empty list
def calc[x]:
for n in range[1, x]:
if x % n == 0:
factors.append[n] # if x is divisible by n append to factor list
return factors
def get_large[x]:
calc[x] # call the returned values in factors list
return calc[x][-1] # return the last factor in the list
print["The largest factor is: " + str[get_large[600851475143]]]
mkrieger1
15.6k4 gold badges45 silver badges57 bronze badges
asked Jun 20, 2018 at 18:53
5
Here is mine. Note that factors
is local to calc[]
so we aren't constantly appending to the previous list.
Also note that get_large[]
only has to call calc[]
once. There is no reason to call it twice.
Finally, I replaced your algorithm in
calc[]
with one that should go substantially faster.
def calc[x]:
factors = []
i = 2
while i < x:
while x % i == 0:
x /= i
factors += [i]
i += 1
return factors
def get_large[x]:
return calc[x][-1] #return the last factor in the list
print ["The largest factor is: " +str[get_large[600851475143]]]
Result, including timing:
$ time python3 x.py
The largest factor is: 1471
real 0m0.065s
user 0m0.020s
sys 0m0.004s
answered Jun 20, 2018 at 19:26
RobᵩRobᵩ
157k17 gold badges225 silver badges300 bronze badges
1
It's probably not broken, just taking a long time. Python is well known for being slow when running big for
loops. I would recommend something like the following:
def calc[x]:
n = 2
factors = []
while x != n:
if x % n == 0:
factors.append[n] #if x is divisible by n append to factor list
x = x / n #this will safely and quickly reduce your big number
n = 2 #then start back at the smallest potential factor
else:
n = n + 1
return factors #This will return a list of all prime factors
def get_large[x]:
bigFactor = x / calc[x][0]
#The largest factor is just the original
#number divided by its smallest prime factor
return bigFactor
I used 2 as the smallest potential factor because using 1 would get us nowhere :]
answered Jun 20, 2018 at 19:24
2
if the number itself is not the largest factor, then why to loop till x, it can looped until x/2 .
answered Jul 24, 2018 at 4:00
nandynandy
811 silver badge3 bronze badges
[Edited]
import math
def get_large[x]:
for n in range[2, math.ceil[math.sqrt[x]]]:
if x % n == 0:
return x / n
return 1
print ["The largest factor is: " +str[get_large[600851475143]]]
Your code is too inefficient and so it takes forever to run for large numbers. The above is a more efficient version.
answered Jun 20, 2018 at 19:13
2
Source Code
# Python Program to find the factors of a number
# This function computes the factor of the argument passed
def print_factors[x]:
print["The factors of",x,"are:"]
for i in range[1, x + 1]:
if x % i == 0:
print[i]
num = 320
print_factors[num]
Output
The factors of 320 are: 1 2 4 5 8 10 16 20 32 40 64 80 160 320
Note: To find the factors of another number, change the value of num
.
In this program, the number whose factor is to be found is stored in num
, which is passed to the print_factors[]
function. This value is assigned to the variable x in print_factors[]
.
In the function, we use the for
loop to iterate from i equal to x. If x is perfectly divisible by
i, it's a factor of x.