How do I find the largest prime factor in an array?

Question

I am solving problem 3 in euler project to find the largest prime factor of a certain number.

def findFactors(num: int)->list:
    factors = []
    for i in range(1, num+1):
        if num%i == 0:
            factors.append(i)
    return factors



prime_factors = (findFactors(600851475143))
max= prime_factors[0]
num = 600851475143
for i in range(0, len(prime_factors)):
    if (prime_factors[i] > max):
        max = prime_factors[i]

print(f"The largest prime factor of the {num} is {max}")

When I run the code for "13195", the code runs correctly but when I run the code for the actual number i.e 600851475143, the code is not giving any output, neither any errors

it is a very big number. iteration will take a very long time maybe hours — ashish singh, Jan 13 '23 at 08:15
The second loop can be replaced by the `max` function, see [Python documentation](https://docs.python.org/3/library/functions.html?highlight=built#max). — guidot, Jan 13 '23 at 08:48
Does this answer your question? [Finding largest prime number out of 600851475143?](https://stackoverflow.com/questions/15279278/finding-largest-prime-number-out-of-600851475143) — Alvi15, Jan 13 '23 at 10:30
Estimate how long it can take to produce a result. Assuming that your loop body takes one nanosecond per iteration (which is *very* optimistic, even if this weren't Python), `findFactors(600851475143)` would take just over ten minutes. More realistically, one *micro*second per iteration would take slightly less than a week. — molbdnilo, Jan 13 '23 at 12:22
Very few of the Project Euler problems can be solved with a brute force approach in a reasonable time - they are maths problems, not programming problems. — molbdnilo, Jan 13 '23 at 12:28

Talha Tayyab · Answer 1 · 2023-01-13T12:13:10.960

2

I think while loop will perform better:

n = 600851475143
x = 2
while x * x < n:
    while n % x == 0:
        n = n // x
    x = x + 1

print(n)
#6857

edited Jan 13 '23 at 12:13

answered Jan 13 '23 at 08:18

Talha Tayyab

8,111
25
27
44

I would use `n = n // x`. – treuss Jan 13 '23 at 12:11
I am getting `6857` – Talha Tayyab Jan 13 '23 at 12:15

score 0 · Answer 2 · answered Jan 13 '23 at 08:41

You need two functions. One to determine the factors of a positive integer and another to determine if a number is prime.

from functools import cache
from math import sqrt, floor
from functools import reduce
from time import perf_counter

@cache
def isprime(n):
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, floor(sqrt(n))+1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True

def factors(n):
    if n > 0:
        for f in sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, floor(sqrt(n)) + 1) if n % i == 0)))):
            yield f

N = 600851475143

start_time = perf_counter()

f = [_f for _f in factors(N) if isprime(_f)]

end_time = perf_counter()

print(f[-1] if f else None, f'{end_time-start_time:.4f}s')

Output:

6857 0.0452s

score 0 · Answer 3 · answered Jan 13 '23 at 10:57

Your code does work, but just takes too long. As someone pointed out, the number evaluated is indeed very big... Here it is required that you compute at least 10^12 division before it finishes.

Of course there are better ways to answer this problem. For instance, you need to look for factors only up to sqrt(n); or you could try to think about the sieve of eratosthenes.

score 0 · Answer 4 · answered Jan 13 '23 at 13:09

You could use a recursive function:

from math import sqrt, floor
import time
def findFactors(n):
    if n%2==0:
        findFactors(int(n/i))
        return
    
    for i in range (3, floor(sqrt(n))+2, 2):
        if n%i==0:
            print (i)
            findFactors(int(n/i))
            return
    print (n)
    return 

start=time.time()
findFactors(600851475143)
print (time.time()-start)

Output:

71

839

1471

6857

0.00026988983154296875

How do I find the largest prime factor in an array?

4 Answers4