Home > scala > Scala: Project Euler: Problem 10

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
    }
}

scala

  1. No comments yet.
  1. No trackbacks yet.