Created
March 4, 2011 05:15
-
-
Save heuristicfencepost/854213 to your computer and use it in GitHub Desktop.
Solution to Project Euler problem #10 in various languages
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(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))) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(:+) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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