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

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

CodePudding user response：

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

CodePudding user response：

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

CodePudding user response：

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.

CodePudding user response：

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:

839

1471

6857

0.00026988983154296875