Question

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

What is the largest prime factor of the number 600851475143 ?

Answer

6857

---

Python

#!/usr/bin/env python
import math

def factorize(n):
    res = []
    # iterate over all even numbers first.
    while n % 2 == 0:
        res.append(2)
        n //= 2
    # try odd numbers up to sqrt(n)
    limit = math.sqrt(n+1)
    i = 3
    while i <= limit:
        if n % i == 0:
            res.append(i)
            n //= i
            limit = math.sqrt(n+i)
        else:
            i += 2
    if n != 1:
        res.append(n)
    return res

print(max(factorize(600851475143)))

---

JavaScript

let n = 600851475143
let limit = Math.ceil(Math.sqrt(n))
for (var i = 3; i <= limit; i += 2) {
  while (n % i === 0) {
    n = Math.floor(n / i)
    limit = Math.ceil(Math.sqrt(n))
  }
}
console.log(n)

---

Ruby

#!/usr/bin/env ruby

def factorize(orig)
  factors = {}
  factors.default = 0     # return 0 instead nil if key not found in hash
  n = orig
  i = 2
  sqi = 4                 # square of i
  while sqi <= n do
    while n.modulo(i) == 0 do
      n /= i
      factors[i] += 1
      # puts "Found factor #{i}"
    end
    # we take advantage of the fact that (i +1)**2 = i**2 + 2*i +1
    sqi += 2 * i + 1
    i += 1
  end

  if (n != 1) && (n != orig)
    factors[n] += 1
  end
  factors
end

puts factorize(600851475143).keys.max

---

Go

package main

import "fmt"
import "math"
import "math/big"

func eratosthenes(max int) []int {
	nums := make([]int, max)

	p := 2 // first prime, 2
	for {
		i := p - 1
		// mark multiples not prime
		for i += p; i < max; i += p {
			nums[i] = -1
		}
		// find first unmarked number greater than p
		for i = p; i < max; i++ {
			if nums[i] != -1 {
				p = i + 1
				break
			}
		}
		// no unmarked numbers greater than p found; finished
		if i == max {
			break
		}
	}
	// filter out all marked numbers
	primes := make([]int, max)
	j := 0
	for i := range nums {
		if nums[i] == 0 {
			primes[j] = i + 1
			j++
		}
	}
	return primes[:j]
}

func main() {
	n := new(big.Int)
	n.SetString("600851475143", 10)
	m := new(big.Int)
	max := int(math.Sqrt(600851475143))
	primes := eratosthenes(max)
	// find the largest prime factor of n
	for i := len(primes) - 1; i >= 0; i-- {
		p := big.NewInt(int64(primes[i]))
		m.Mod(n, p)
		if m.Int64() == 0 {
			fmt.Println(p)
			break
		}
	}
}

---

Haskell

primes :: [Integer]
primes = sieve [2..] where
    sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]

factorize :: Integer -> [Integer]
factorize n = primeFactors n primes where
    primeFactors 1 _ = []
    primeFactors m (p:ps) | m < p * p = [m]
                          | r == 0 = p : primeFactors q (p:ps)
                          | otherwise = primeFactors m ps
                          where (q, r) = quotRem m p

main :: IO ()
main = print $ maximum $ factorize 600851475143

---

Rust

fn main() {
    let mut n: u64 = 600851475143;
    let mut limit = n / 2;
    let mut i = 3;
    while i < limit {
        while n % i == 0 {
            n = n / i;
            limit = n / 2;
        }
        i += 2;
    }
    println!("{}", n);
}

---

Java

public final class p003 implements EulerSolution {
	
	public static void main(String[] args) {
		System.out.println(new p003().run());
	}
	
	
	/* 
	 * By the fundamental theorem of arithmetic, every integer n > 1 has a unique factorization as a product of prime numbers.
	 * In other words, the theorem says that n = p_0 * p_1 * ... * p_{m-1}, where each p_i > 1 is prime but not necessarily unique.
	 * Now if we take the number n and repeatedly divide out its smallest factor (which must also be prime), then the last
	 * factor that we divide out must be the largest prime factor of n. For reference, 600851475143 = 71 * 839 * 1471 * 6857.
	 */
	public String run() {
		long n = 600851475143L;
		while (true) {
			long p = smallestFactor(n);
			if (p < n)
				n /= p;
			else
				return Long.toString(n);
		}
	}
	
	
	// Returns the smallest factor of n, which is in the range [2, n]. The result is always prime.
	private static long smallestFactor(long n) {
		if (n <= 1)
			throw new IllegalArgumentException();
		for (long i = 2, end = Library.sqrt(n); i <= end; i++) {
			if (n % i == 0)
				return i;
		}
		return n;  // n itself is prime
	}
	
}

---

Mathematica

First[Last[FactorInteger[600851475143]]]