Find index of array item starting at a given location

Question

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?

Answer 1

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.