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
        }
    }
}

$ go build -o prime-factor prime-factor.go
$ time ./prime-factor
real   0m0.018s
user   0m0.018s
sys    0m0.009s

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

$ ghc -O2 -o prime-factor prime-factor.hs
$ time ./prime-factor
real   0m0.003s
user   0m0.000s
sys    0m0.003s

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)

$ time node --use-strict prime-factor.js
real   0m0.052s
user   0m0.046s
sys    0m0.007s

#!/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)))

$ time python3 prime-factor.py
real   0m0.018s
user   0m0.018s
sys    0m0.000s

#!/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

$ time ruby prime-factor.rb
real   0m0.038s
user   0m0.038s
sys    0m0.000s

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);
}

$ rustc -C target-cpu=native -C opt-level=3 -o prime-factor prime-factor.rs
$ time ./prime-factor
real   0m0.001s
user   0m0.000s
sys    0m0.001s