1
\$\begingroup\$

I've written a lot of C++ but now I'm learning Swift. I did an exercise, the standard Sieve of Erastosthenes. It works fine, but it seems a bit clunky and I wonder if I'm missing some language features that might streamline it a bit and make it more idiomatic Swift.

Here's the code:

struct Sieve {
    let primes: [Int]
    init(_ maxValue: Int) {
        var numbers = Array<Int?>(repeating: nil, count:maxValue + 1)
        for n in 2...maxValue { numbers[n] = n }
        var start = 2
        while start < maxValue {
            guard let prime = numbers.first(where: {$0 != nil && $0! >= start}) else {break}
            let lo = 2 * prime!
            if lo < maxValue {
                for x in stride(from: lo, to: numbers.count, by: prime!) {
                    numbers[x] = nil
                }
            }
            start = prime! + 1
        }
        primes = numbers.compactMap{$0}
    }
}

With the line starting "guard let prime", I'd like to supply a starting index for the 'find' operation, which would be a lot more efficient and would let me drop the comparison $0! >= start altogether. Something along the lines of

guard let prime = numbers.first(where: {$0 != nil}, start: start) else {break}

I also tried

guard let prime = (start...maxValue).first(where: {index in numbers[index] != nil}) else {break}

and that does work but it seems even more awkward. It does have the advantage of starting the search at the index start instead of index zero each time. What's the preferred way to search an array beginning somewhere in the middle of it?

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! \$\endgroup\$ – Martin R Jan 10 at 20:45
  • \$\begingroup\$ (One reference site is Rosetta Code.) \$\endgroup\$ – greybeard Jan 10 at 21:25
0
\$\begingroup\$

To answer your immediate question: You can search in an array slice:

 guard let prime = numbers[start...].first(where: {$0 != nil}) else {break}

That works because array slices share their indices with the originating array.


There is a small bug in your program, as one can see here:

let sieve = Sieve(4)
print(sieve.primes) // [2, 3, 4]

The reason is that the

if lo < maxValue { ... }

loop does not include the last value. The test should be lo <= maxValue.


There are also some possible improvements:

        let lo = 2 * prime!

can be replaced by

        let lo = prime! * prime!

because all lower multiples have been “nilled” before. As a consequence, the outer loop

    while start <= maxValue { ... }

can be replaced by

    while start * start <= maxValue { ... }

Now instead of repeatedly searching for the next non-nil entry in the array you might as well iterate over the array. This allows also to get rid of the ugly forced unwrapping prime!:

    for i in (2..<numbers.count).prefix(while: { $0 * $0 <= maxValue }) {
        if numbers[i] != nil {
            for x in stride(from: i * i, to: numbers.count, by: i) {
                numbers[x] = nil
            }
        }
    }

At this point it becomes apparent that the information in the numbers array is redundant: Each element is equal to its index or nil. Therefore a boolean array is sufficient instead of an array of optional integers, this reduces the required memory considerably.

I suggest that you first try to implement that yourself, otherwise have a look at func eratosthenesSieve() in Prime Number Generator & Efficiency.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the welcome, and for pointing out that bug. I had rather hastily inserted that if statement when I found that the invocation of stride threw an exception when lo >= numbers.count. The (now deprecated) older form of the for loop, for x = lo; x < numbers.count; x += prime simply would have executed zero times in that case. \$\endgroup\$ – Logicrat Jan 10 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.