HiveBrain v1.2.0
Get Started
← Back to all entries
patternswiftMinor

Calculate the sum of all primes less than 2,000,000 in Swift

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
swifttheprimesall000thanlesscalculatesum

Problem

This is a Swift program I wrote to calculate the sum of primes below 2 million, but it is tediously slow.

I am curious about what makes it so slow. My theory is that copying the filtered array is the heavy operation. Any other ideas on how to speed it up?

func initArray (p:Array)  -> Array {

    var arr = Array()
    arr.reserveCapacity(2000000)

    func isDiv(p:Array, val:UInt32) ->Bool {

        for i in p {

            if val % i == 0 {
                return true
            }
        }

        return false
    }

    for i:UInt32 in 2...2000000 {

        if !isDiv(p, val: i) {
            arr.append(i)
        }

    }

    return arr

}

var primes:Array = [2,3,5,7]

primes.reserveCapacity(20000)

var numbers = initArray(primes)

while numbers.count != 0 {
    numbers = numbers.filter( { return ($0 % primes[primes.count - 1] != 0 )} )

    if !numbers.isEmpty {
        primes.append(numbers[0])
    }

}

let result = primes.reduce(0, combine: +)

print (result)

Solution

This is a bit of a brute-force solution using trial division, with an optimization that you try dividing by just the previously discovered primes.

When you want to find many primes, though, a much faster algorithm is the sieve-of-eratosthenes.

Context

StackExchange Code Review Q#131312, answer score: 3

Revisions (0)

No revisions yet.