Problem 3

Largest prime factor

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

http://projecteuler.net/problem=3

The Easy Way

$ factor 600851475143
# 600851475143: 71 839 1471 6857

GNU coreutils has a factor command. If you are using a linux machine it is most likely already installed. On Mac’s you can install coreutils using a package manager like homebrew.

Brute Force

First lets make a Primes object that can generate an array of primes up to $n$. A prime number is any number that is only divisible by 1 and and itself. For a truly naive approach, to check if $n$ is prime, you would check every number in the range of $[2, n)$.

For our naive approach, we will keep an array of primes we have found and check if $n$ is divisible by any prime. We can do this because any non-prime number that $n$ is divisible by, is itself divisible by a previously found prime, making $n$ also divisible by that prime. We will also limit our search to odd numbers.

var NaivePrimes = (function() {
  // Returns if n is prime using trial division for previously found primes.
  function isPrime(n, primes) {
    var pi = 1, // Skip checking if divisible by 2.
        prime = primes[pi];
    while (prime < n) {
      if (!(n % primes[pi])) return false;
      prime = primes[++pi]
    }
    return true;
  }

  function primesTo(n) {
    var primes, i;
    if (n < 2) return [];
    if (n === 2) return [2];
    if (n === 3) return [3];
    primes = [2, 3];
    i = 5;
    while (i <= n) {
      if (isPrime(i, primes)) primes.push(i);
      i+=2;
    }
    return primes;
  }

  return {
    primesTo : primesTo
  }
})();
timer(NaivePrimes.primesTo, 1, 100000);
// primesTo x 1: 462.319ms
// Array[9592]
// [ 2,
//   3,
//   5,
//   7,
//   ...
//   99971,
//   99989,
//   99991 ]

More Optimizations

The big optimization we can make is only checking if $n$ is divisible by numbers $\le \sqrt n$. This is because if $pq=n$ for $p$ and $q\neq 1$ and $\neq \sqrt n$, then $p$ or $q$ must be $\le \sqrt n$. If both $p$ and $q \gt \sqrt n$ it would contradict $\sqrt n \times \sqrt n = n$.

var LessNaivePrimes = (function() {
  // Returns if n is prime using trial division for previously found primes.
  // Only check up to floor(sqrt(n)).
  function isPrime(n, primes) {
    var pi = 1, // Skip checking if divisible by 2.
        prime = primes[pi],
        limit = Math.floor(Math.sqrt(n));
    while (prime <= limit) {
      if (!(n % prime)) return false;
      prime = primes[++pi];
    }
    return true;
  }

  function primesTo(n) {
    var primes, i;
    if (n < 2) return [];
    if (n === 2) return [2];
    if (n === 3) return [3];
    primes = [2, 3];
    i = 5;
    while (i <= n) {
      if (isPrime(i, primes)) primes.push(i);
      i+=2;
    }
    return primes;
  }

  return {
    primesTo : primesTo
  }
})();
timer(LessNaivePrimes.primesTo, 1, 100000);
// primesTo x 1: 34.117ms
// Array[9592]

Another optimization that we can make that reduces the number of $n$’s we need to check is all primes past $3$ can be generalized in the form $6i \pm 1$.

The proof for this generalization can be stated as:

Given a number, $n \gt 3$, dividing $n$ by $6$ gives you:
$n = 6x + r$ ; $x$ is a non-negative integer and $r$ is the remainder

for $r$ is $0$, $2$, or $4$ ; $n$ is divisible by $2$
for $r$ is $3$ ; $n$ is divisible by $3$

for $r$ is $1$ ; $n$ is $1$ more than a multiple of $6$
for $r$ is $5$ ; $n$ is $1$ less than a multiple of $6$

That means for all $n$ not in for form of $6i \pm 1$, $n$ is divisible by $2$ or $3$. This means we can eliminate all those from our checks.

Primes!

var Primes = (function() {
  // Returns if n is prime using trial division for previously found primes.
  // Only check up to floor(sqrt(n)).
  function isPrime(n, primes) {
    var pi = 1, // Skip checking if divisible by 2.
        prime = primes[pi],
        limit = Math.floor(Math.sqrt(n));
    while (prime <= limit) {
      if (!(n % prime)) return false;
      prime = primes[++pi];
    }
    return true;
  }

  function primesTo(n) {
    var primes, i = 1;
    if (n < 2) return [];
    if (n === 2) return [2];
    if (n === 3) return [2, 3];
    primes = [2, 3];
    while (true) {
      var candidate = 6 * i - 1;
      if (candidate > n) break;
      if (isPrime(candidate, primes)) primes.push(candidate);
      candidate += 2;
      if (candidate > n) break;
      if (isPrime(candidate, primes)) primes.push(candidate);
      i++;
    }
    return primes
  }

  return {
    primesTo : primesTo
  }
})();
timer(Primes.primesTo, 1, 100000);
// primesTo x 1: 26.513ms
// Array[9592]

Using the Prime Generator

To find the prime factors for our number, we can apply the same logic we did for checking primes for divisibility by only checking up to $\sqrt n$.

function euler3() {
  var factors = [],
      n = 600851475143,
      limit = Math.floor(Math.sqrt(n)),
      primes = Primes.primesTo(limit),
      i = primes.length;
  while (i--) {
    if (n % primes[i] === 0) factors.push(primes[i]);
  }
  return factors;
}
timer(euler3);
// euler3 x 1: 243.233ms
// [6857, 1471, 839, 71]