1

It's a Project Euler problem. What is the largest prime factor of the number 600851475143? I wrote the following code-:

def prime_factors(x):
    my_list = []
    for no3 in range(2, int(x)):
        i = 0
        if x % no3 == 0:
            for a in range(1, int(no3)):
                if no3 % a == 0:
                    i = i + 1
            if i == 1:
                my_list.append(no3)
    print(max(my_list))

prime_factors(600851475143)

It works fine for small numbers but for a large number such as this one '600851475143' the code does not give an output, it just keeps on running. I want to know that what is the problem with this code and how can I resolve it.

Tejas Agarwal
  • 53
  • 1
  • 6
  • 3
    This number is relatively huge, and your code has to loop over loads of numbers in the first loop (hint: you don't need that many numbers) and loads of numbers in the second loop, so it may take quite a while to finish. – ForceBru Jun 24 '18 at 21:48
  • 1
    This might be better on the Code Golf or Software Engineering StackExchange sites. – ryanwebjackson Jun 24 '18 at 21:58
  • Have done any research? There are over 300 hits on [stackoverflow](https://stackoverflow.com/search?q=600851475143) alone by just searching for the number you are trying to factor. – Joseph Wood Jun 25 '18 at 02:14
  • Once again, the mods mark something as a duplicate even though it isn't a duplicate. This question asks _specifically_ about Python, and the other question is about Java. – Brandon Dyer Jan 09 '22 at 22:32

1 Answers1

1

Each of your loop is from 2 to n, so with 2 loops, your loop has to be run for square(n) times, before giving you an answer

If you change your loop slightly, you can make it much faster. To find the factors of a number n, you dont have to check all numbers less than n. It is enough if you check upto int(sqrt(n)). For each factor x between 2 and int(sqrt(n)), n/x will also be a factor.

So by changing your loop to run only upto int(sqrt(n)), your code would run much faster

from math import sqrt 

def is_prime(n): 
    for a in range(2, int(sqrt(n))): 
        if n % a == 0: 
            return False 
    return True 

def prime_factors(x): 
    my_list = [] 
    for no3 in range(2, int(sqrt(x))): 
        if x % no3 == 0: 
            # no3 and x/no3 are factors of x 
            if is_prime(no3): 
                my_list.append(no3) 
            if is_prime(x/no3): 
                my_list.append(no3) 
    print(max(my_list))

Now on trying this we get

>>> prime_factors(600851475143)
6857
>>>
Sunitha
  • 11,777
  • 2
  • 20
  • 23
  • The target number is odd, so it does not have any even factors. When checking for possible factors, start at 3 and step 2 so only odd possible factors are checked. That should halve the search time. – rossum Jun 25 '18 at 10:32
  • Yes... There are a lot more optimizations that can be done to this; but wanted to maintain the code as much as possible to OP's code I hope OP would try out your suggestion and experiment with a few more – Sunitha Jun 25 '18 at 10:37
  • 2
    Thank you @Sunitha ma'am for the help but checking till the square root of the target number will not work in cases where the square root is smaller than the largest factor. For example- in case of the number 10, the largest factor is 5 but the square root is 3.16, so this code will return 2 as the output while it should have given 5. – Tejas Agarwal Jun 26 '18 at 09:30