#3: Largest prime factor | Ben Cunningham

#3: Largest prime factor

Problem by Project Euler · on November 2, 2001

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

Python

def l_factors(x):

    [ll, lh] = [[], []]

    for f in range(1, int(x ** (1/2.0)) + 1):
        if x % f == 0:
            ll.append(f)
            fp = x / f
            if fp != f:
                lh.append(int(fp))

    return ll + list(reversed(lh))
    
def is_prime(x):

    if x < 4:
        return True

    if x % 2 == 0:
        return False

    for fac in range(3, int(x ** (1/2.0)) + 1, 2):
        if x % fac == 0:
            return False

    return True
    
ans = None
fac = l_factors(600851475143)

i = len(fac) - 2
while ans is None:
    if is_prime(fac[i]):
        ans = fac[i]
    i -= 1
    
print(ans)
## 6857

R

x <- 600851475143

d <- c(2, seq(3, sqrt(x), by = 2))
fac <- c(d[x %% d == 0], x / d[x %% d == 0])

is_prime <- function(x) {
  d <- c(2, seq(3, sqrt(x), by = 2))
  length(d[x %% d == 0]) == 0
}

max(fac[sapply(fac, is_prime)])
## [1] 6857