Skip to content

Instantly share code, notes, and snippets.

@DarrenN
Created December 21, 2010 18:17
Show Gist options
  • Save DarrenN/750315 to your computer and use it in GitHub Desktop.
Save DarrenN/750315 to your computer and use it in GitHub Desktop.
Project Euler #3 in pure CoffeeScript
# Project Euler #3 -> http://projecteuler.net/index.php?section=problems&id=3
# Q: What is the largest prime factor of the number 600851475143 ?
# Generate a Sieve of Eratosthenes (an array loaded with prime numbers)
primes = []
sieve = (set, pos) ->
return false if pos >= set.length
if set[pos] * set[pos] < set[set.length-1]
primes = (x for x in set when x == set[pos] or x % set[pos] != 0)
return sieve(primes,pos+1)
sieve([2..200000],0)
# Factor a number into its primes - we use our Sieve above to quickly check if number is prime
factors = []
factorial = (primes, target, count) ->
if primes[count] < target
if target % primes[count] == 0
factors.push(primes[count])
target = target / primes[count]
else
count++
if (num for num in primes when num == target).length > 0
factors.push(target)
else
factorial(primes, target, count)
factorial(primes, 600851475143, 0)
console.log(factors)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment