Skip to content

Instantly share code, notes, and snippets.

@heuristicfencepost
Created March 4, 2011 05:15
Show Gist options
  • Save heuristicfencepost/854213 to your computer and use it in GitHub Desktop.
Save heuristicfencepost/854213 to your computer and use it in GitHub Desktop.
Solution to Project Euler problem #10 in various languages
(def odds (iterate #(+ 2 %) 3))
(def primes
(let [pred (fn [v]
(let [root (int (. Math floor (. Math sqrt v)))
samples (take-while #(<= % root) primes)]
(every? #(not (= 0 (mod v %))) samples)
))]
(lazy-cat (list 2) (filter pred odds))
)
)
(println (reduce + (take-while #(< % 2000000) primes)))
class Euler10
include Enumerable
def initialize()
@primearr = [2]
@nat = 3
end
def each
yield 2
loop do
root = Math.sqrt @nat
if @primearr.take_while {|i| i <= root }.all? {|i| @nat % i != 0}
@primearr << @nat
yield @nat
end
@nat += 2
end
end
end
puts Euler10.new().take_while {|i| i < 2000000}.reduce(:+)
package org.fencepost
import scala.math.sqrt
import scala.math.floor
object Euler10 {
// A stream for odd values starting from a specific value. We only need to consider
// odds since by definition any prime value other than two must be odd. Adding this
// constraint cuts the number of comparisons we must execute by a factor of two.
def odds(n:Long):Stream[Long] = Stream.cons(n,odds(n + 2))
// Predicate to test for primality. Base test is to verify that a candidate isn't evenly
// divisible into all integers between 2 and the candidate's square root. As an optimization
// we can compare all primes within this range. We pursue this path here, however in order
// to make the whole thing work we must supply an initial "seed" value of the first prime;
// thus the Stream.cons() usage below.
def pred(n:Long):Boolean = {
val root = floor(sqrt(n))
(primes takeWhile { _ <= root }) forall { n % _ != 0 }
}
// Note that since we're explicitly stating 2 as the first argument to Stream.cons()
// we now have to start the natural number sequence at 3.
lazy val primes:Stream[Long] = Stream.cons(2,odds(3) filter pred)
def main(args: Array[String]): Unit = {
println("Result: " + (0L /: (primes takeWhile { _ < 2000000 })) (_+_))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment