-2

i was attempting to write a python code that finds the largest prime factor in a given number, a for loop would count from 2 up, each time passing a number to a function that checks if it's a prime. nested in it is another for loop that sees if said given number can divide correctly with the current number in question, the code gives no results and seems to be stuck in an infinite loop.

here's the code :

def prime_x (n):   #identify primes        
    for x in range (2,n):
        if n % x == 0:
            return False
    return True

c = 600851475143 #given number
primes = []                        


for num in range(2 , c):
    if prime_x (num):
        if c % num == 0:
            primes.append(num)

print (max(primes))

please note that i was able to find the answer by placing a print statement inside the loop, but i can't get the loop to end and the answer be printed on it's own.

ChatGPT tells me that the algorithm is not efficient and it causes the program to get stuck, however there was no memory error. additionally, when the mentioned in-loop solution is performed, outputs are displayed properly, indicating that the execution ran properly through the whole number set.

Fred
  • 1
  • 2
  • 1
    Do you actually get the *entire* output when you add a `print` into the loop, or do you just abort the program after seeing some output? Because running `600851475143` iterations will quite likely take a while – UnholySheep Aug 01 '23 at 09:32
  • 1
    The code works for smaller numbers just fine, so it's obvious that the program the problem is complexity of this algorithm. – matszwecja Aug 01 '23 at 09:32
  • said number is comprised exactly of 4 prime numbers, all 4 of them are displayed, however after the fourth is displayed, the program still freezes edit: sorry meant 4 factors, not 3, they are 71, 839, 1471, 6857 – Fred Aug 01 '23 at 09:36
  • Since you're looping over finite ranges and there's no recursion, there's no chance of an infinite loop here. It's probably just running for a very very long time to completion. – deceze Aug 01 '23 at 09:38
  • 1
    @Fred I'm getting 4 primes, but the thing is - you are looping through **all** the numbers up to `c`. You don't check in any way that you found all the factors. So after code finds `6857` it then checks if `6858` is prime. And then `6859`. And so on until `600851475143` – matszwecja Aug 01 '23 at 09:41
  • alright, thanks, i will be looking for a more efficient method – Fred Aug 01 '23 at 09:43

2 Answers2

2

You are looping through all the numbers up to c. You don't check in any way that you found all the factors. So after code finds 6857 it then checks if 6858 is prime. And then 6859. And so on until 600851475143

A direct "fix" for this would be to break if all the primes multiply up to c:

from functools import reduce

def prime_x (n):                   #function that checks if a number is a prime
    for x in range (2,n):
        if n % x == 0:
            return False
    return True

c = 600851475143                   # given number
primes = []                        


for num in range(2 , c):
    if prime_x (num):
        if c % num == 0:
            primes.append(num)
            if reduce(lambda x, y: x*y, primes) == c:
                break

print (max(primes))

But that is not a real fix, as it doesn't take into account multiples of the same factor, amongst other problems.

In general, this code can be optimised a lot, starting with a simple concept - checking if some number is a factor of c is much quicker operation than checking if it's prime. Thus, simple swapping of conditions will speed up the code greatly:

    if c % num == 0:
        if prime_x (num):

But, after all, the biggest bottleneck is the very inefficient way of checking primes. I suggest reading up on various methods for that, for example:

Why do we check up to the square root of a number to determine if the number is prime?

Python: Sieve of Eratosthenes method, for computing prime number

Just the first optimization (with only checking up to square root of a number) will make the code near-instant.

matszwecja
  • 6,357
  • 2
  • 10
  • 17
1

There is no problem with your code, but the given number is very large, so the execution time of the program is very long. Your code needs to be optimized; I have applied 2 of these optimizations here:

The main idea is that when you are looking for the divisors of a number, it is not necessary to calculate the remainder of that number over all the numbers from 1 to that number itself, and if it is equal to 0, put it in a list. In fact, in order to find the divisors of a number, it is enough to calculate the remainder of that number by 1 to the square root of that number plus 1 (sqrt(number)+1) and put each of them equal to 0 in the list.

The same formula is also true for checking whether a number is prime or not. This allows you to get rid of a significant part of the computations, thus greatly speeding up your program.

def prime_x(n):        
    for x in range(2, int(n**0.5)+1):
        if n % x == 0:
            return False
    return True

c = 600_851_475_143 #given number

divisors = []                        
for num in range(1 , int(c**0.5)+1):
    if c % num == 0:
        divisors.append(num)
        divisors.append(c//num)

primes = []
for num in divisors:
    if prime_x(num):
        primes.append(num)

print(max(primes))
arash.shx
  • 51
  • 2