# Project Euler Problem 3 Solution

## Question

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

What is the largest prime factor of the number 600851475143 ?

## 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
}
}
}
$go build -o prime-factor prime-factor.go$ time ./prime-factor
real   0m0.018s
user   0m0.018s
sys    0m0.009s

## 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
$ghc -O2 -o prime-factor prime-factor.hs$ time ./prime-factor
real   0m0.003s
user   0m0.000s
sys    0m0.003s

## 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)
$time node --use-strict prime-factor.js real 0m0.052s user 0m0.046s sys 0m0.007s ## 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))) $ time python3 prime-factor.py
real   0m0.018s
user   0m0.018s
sys    0m0.000s

## 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
$time ruby prime-factor.rb real 0m0.038s user 0m0.038s sys 0m0.000s ## 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); } $ 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