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?

• greybeard: (One reference site is Rosetta Code.)

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.

• Logicrat: 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.