Problem 3 - Largest Prime Factor

Ella, Sri Lanka - Black Bridge overlooking the top of Kuda Ravana waterfall - April 29th, 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

Code

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

Code

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

Reuse

Citation

For attribution, please cite this work as:

Clemson, Vincent. 2026. “Problem 3 - Largest Prime Factor.” January 15, 2026. https://prncevince.xyz/euler/problem/0003.html.