Scala: Project Euler: Problem 10
November 29th, 2009
Problem:
Calculate the sum of all the primes below two million (2000000)
import scala.collection.mutable.ListBuffer
import scala.collection.mutable.Map
object Problem10 {
def main(args: Array[String]) :Unit = {
println(findSumOfPrimesFast(2000000))
}
def findSumOfPrimesFast(max: Int) : BigInt = {
//initialize sum to basic primes
var sum = BigInt(0)
if(max > 2) sum += 2
if(max > 3) sum += 3
if(max > 5) sum += 5
if(max > 7) sum += 7
if(max > 11) sum += 11
//initialize map with numbers < max and not multiples of basic primes
var map = Map[Int, Boolean]()
for {
i <- 2.until(max)
if(i % 2 != 0)
if(i % 3 != 0)
if(i % 5 != 0)
if(i % 7 != 0)
if(i % 11 != 0)
} map += (i -> true)
var i = 13
while(i <= Math.sqrt(max)) {
if(map.contains(i)) {
map -- multiples(i, max)
sum += i
}
i += 2 //skipping evens
}
//all numbers greater than sqrt(max) are primes
val iter = map.keys
while(iter.hasNext) {
sum += iter.next
}
return sum
}
def multiples(number:Int, max:Int) : Iterable[Int] = {
val numbers = new ListBuffer[Int]()
var multiple = number
var loop = 1;
while(multiple < max) {
numbers += multiple
loop += 1
multiple = number * loop
}
return numbers
}
}