Project Euler - Problem #10

Description

• The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
• Find the sum of all the primes below two million.

Solution


open System.Collections
open System.Numerics


//gets primes but can't handle the number size
//very fast, a huge improvement over prior code
let getPrimes max =
    let primes = new BitArray(max+1, true)
    seq { 2 .. max } |>
    Seq.filter (fun n ->
        if primes.[int n] then
            for i in int64 n * int64 n..int64 n..int64 max do primes.[int i] <- false
        primes.[int n])


//same function, but written to use and return BigInteger
let getPrimesBigInt max =
    let primes = new BitArray(max+1, true)
    seq { 2 .. max } |>
    Seq.filter (fun n ->
        if primes.[int n] then
            for i in bigint n * bigint n..bigint n..bigint max do primes.[int i] <- false
        primes.[int n])


//creates array of primes, up to 2MM
let arrPrimeBigInt = Array.ofSeq(getPrimesBigInt 2000000)


//recursive function to sum array of BigInteger
let rec sumArrayBigInt itemCounter (endVal:BigInteger) (acc:BigInteger): BigInteger =
    if  BigInteger(arrPrimeBigInt.[itemCounter]) = endVal  then
        acc + BigInteger(arrPrimeBigInt.[itemCounter])
    else
        let result = BigInteger(arrPrimeBigInt.[itemCounter]) + acc
        sumArrayBigInt (itemCounter+1) endVal result


//main function
let resPrimesAlt : BigInteger =
    let endVal = BigInteger(arrPrimeBigInt.[Array.length arrPrimeBigInt - 1])
    let acc = BigInteger(0)
    let result = sumArrayBigInt 0 endVal acc
    result