Skip to content

Instantly share code, notes, and snippets.

@heuristicfencepost
Created March 7, 2011 07:10
Show Gist options
  • Save heuristicfencepost/858177 to your computer and use it in GitHub Desktop.
Save heuristicfencepost/858177 to your computer and use it in GitHub Desktop.
A better Ruby implementation of Project Euler problem #10 and a horrible implementation in Haskell
module Main where
-- Definition of our candidate set
tens = map (*10) [1..]
urcandidate(x:xs) = map (+x) [1,3,7,9] ++ urcandidate(xs)
candidates = urcandidate(tens)
-- Define the logic to be used by our predicate and utilize currying to support partial application
urpred(candidate,prime) = prime > (truncate (sqrt (fromIntegral candidate))) || candidate `mod` prime == 0
pred = curry urpred
-- Self-referential definition of prime numbers. Apparently pred must be qualified here in order to
-- avoid confusion with a definition in the Prelude. Using "head (filter pred primes)" as a surrogate
-- for "find"; some docs seem to suggest that GHC has a "find" function but attempts to use it have
-- so far been unsuccessful
primes = [2,3,5,7] ++ filter (\c -> head (filter (Main.pred c) primes) > (truncate (sqrt (fromIntegral c)))) candidates
-- Kick the whole thing off
main = print (foldr (+) 0 (takeWhile (<2000000) primes))
class Candidates
include Enumerable
def initialize
@base = 10
end
def each
loop do
[1,3,7,9].each { |i| yield @base + i }
@base += 10
end
end
end
class Euler10
include Enumerable
def initialize()
@primearr = [2,3,5,7]
@candidates = Candidates.new()
end
def each
@primearr.each { |i| yield i }
@candidates.each { |candidate|
root = Math.sqrt candidate
testelem = @primearr.find { |i| (i > root) || (candidate % i == 0) }
if testelem > root
@primearr << candidate
yield candidate
end
}
end
end
puts Euler10.new().take_while {|i| i < 2000000}.reduce(:+)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment