Problem 3 - Largest Prime Factor

Aerial view overlooking entry road & Sigiriya Fortress - Lion Rock
Sigiriya, Sri Lanka - May 5th, 2025

The prime factors of \(13195\) are \(5, 7, 13\) and \(29\).
What is the largest prime factor of the number \(600851475143\)?

https://projecteuler.net/problem=3

Development

Storing vectors into memory errors when working with \(1, 2, ..., n\). e.g. 

n <- 600851475143
for (i in n) {
  ... do something
}

We can take a more efficient approach by only storing the sequence of odd numbers \(n\) up until \(\sqrt{n}\), i.e. the sequence \(2, 3, 5, 7, ... , \sqrt{n}\), to begin finding the factors.

We can make this even more efficient by then taking the primes of these odd number factors.

Then, we can iterate through them, by updating the next largest factor by dividing by the increasing prime factors, decreasing n incrementally until it reaches 1. This allows us to potentially find prime factors greater than \(\sqrt{n}\).

For odd \(n\), this is all that we must do. For even \(n\), we can also check repeated divisions by \(2\) until the highest odd prime factor is left.

R

Answer 1

n <- 600851475143
primes <- c()
# check odd prime factors of n up until square root of n
y_primes <- c(2, seq(3, floor(sqrt(n)), 2))
# find & keep only factors
y_primes <- y_primes[n %% y_primes == 0]
y_primes <- y_primes[primes::is_prime(y_primes)]
j <- 0
for (i in y_primes) {
  primes <- c(primes, i)
  n <- n / i
  j <- j+1
  if (primes::is_prime(n) & n > i) {
    primes <- c(primes, n)
    break
  }
}
# max of this set is max primes
max(primes)
# Even more impressive is j
j

[1] 6857
[1] 3

Answer 2 - Even Numbers

n <- 600851475142
factor_largest_p <- function(n) {
  primes <- c()
  # for even values of n:
  # check repeated divisions by 2 until we find the highest odd prime factor left
  if (n %% 2 == 0) {
    k <- 1
    i <- n
    while ((n / k) %% 2 == 0) {
      i <- i / 2
      k <- k + 1
      if (primes::is_prime(i)) primes <- c(primes, i)
    }
  }
  # check odd prime factors of n up until square root of n
  y_primes <- c(2, seq(3, floor(sqrt(n)), 2))
  y_primes <- y_primes[n %% y_primes == 0]
  y_primes <- y_primes[primes::is_prime(y_primes)]
  j <- 0
  for (i in y_primes) {
    primes <- c(primes, i)
    n <- n / i
    j <- j+1
    if (primes::is_prime(n) & n > i) {
      primes <- c(primes, n)
      break
    }
  }
  # max of this set is max primes
  return(c(max_prime = max(primes), iter = j))
}

tic()
factor_largest_p(600851475142)
toc()

max_prime      iter 
    22567         4 
0.012 sec elapsed

Python

Answer 1

import time

def is_prime(n):
  """
  Checks if a number n is prime using trial division up to sqrt(n).
  """
  if n != int(n): return False
  if n <= 1: return False
  if n <= 3: return True
  if n % 2 == 0: return False
  limit = int(n**0.5) + 1
  for i in range(3, limit, 2):
    if n % i == 0: return False
  return True

def factor_largest_p(n: int) -> int:
  """
  1st checks for even values of n:
    checks repeated divisions by 2 until we find the highest odd prime factor left
  then, checks odd prime factors of n up until square root of n
  """
  primes = []
  if n % 2 == 0:
    k = 1
    i = n
    while (n / k) % 2 == 0:
      i /= 2
      k += 1
      if is_prime(i): primes.append(i)
  y_primes = [2] + [i for i in range(3, int(n**0.5)+1, 2)]
  y_primes = [i for i in y_primes if n % i == 0]
  y_primes = [i for i in y_primes if is_prime(i)]
  j = 0
  for i in y_primes:
    primes.append(i)
    n = n / i
    j += 1
    if is_prime(n) and n > i:
      primes.append(n)
      break
  return {'max prime': max(primes), 'iter': j}
  
n = 600851475143

t0 = time.perf_counter()
factor_largest_p(n)
t1 = time.perf_counter()
t = t1 - t0
print(f'{t:.3f} sec elapsed')

{'max prime': 6857.0, 'iter': 3}
0.020 sec elapsed

Answer 2 - Even Numbers

n = 600851475142
t0 = time.perf_counter()
factor_largest_p(n)
t1 = time.perf_counter()
t = t1 - t0
print(f'{t:.3f} sec elapsed')

{'max prime': 22567.0, 'iter': 4}
0.019 sec elapsed