Int n = 1234567
for (int i = 2; i * i < n; i++) { do something }

The purpose of i*i here is to avoid sqrt(), which seems a costy call
and in Swift, we can write like

for i in 2...n where i * i < n { }

I want to ask, does Swift compiler optimize this for loop pattern, if it first finds i * i >= n, Swift will abandon the rest of the iterations? So the total iteration count is much smaller than 2...n

Well, I don't know exactly if the compiler can do what you're asking. The compiler is much smarter than me already. I just want to point out that the two codes are much more different semantically.

haha, then maybe someone could help answering. Yes I know the difference, that's why I want to know if Swift has additional process to handle such cases

The compiler doesn’t know if the where clause’s predicate will be true for elements at the start, the middle, the end, or some interweaved pattern (w.g. Evens and odds). It’s not smart enough to know which sections of the collection are safe to skip over,

What you’re looking for here is a prefix, and hey, and the standard library has a method just for this!

for i in (2...n).prefix(while: { $0 * $0 < n }) { ... }

Of course, this just for illustration, typically you would just make the upper bound of your range be sqrt(n)

prefix should be O(k) where k is the output side for most collections (excluding Lazy collection family), which is the same for traversing k elements. It is fine to use on 2....

In fact, Swift compiler is quite aggressive on combining Collection APIs, so you'll likely get the optimal or near optimal code (You should still benchmark it though it that's what matter).

Note that this is different from your where case. Since the semantic of where is to loop until the end, while prefix bails out, even in an unoptimized code.

Available when Bound conforms to Strideable and Bound.Stride conforms to SignedInteger .

Parameters

predicate

A closure that takes an element of the sequence as its argument and returns true if the element should be included or false if it should be excluded. Once the predicate returns false it will not be called again.

Discussion

Complexity: O( n ), where n is the length of the collection.

Whether we hit the ceiling O(n) depends on the usage too. Since we know we're using i * i < n and not arbitrary predicate, the prefix will just loop through the indices sqrt(n) times.

Of course it’s O(n). The prefix can either be empty, or the full collection, or some middle ground. The condition check in the Java example is also O(n), you just don’t recognize it as such because it’s sneakily embedded in a loop, and not a named construct like a method.

Are you sure about this? The square root could be computed just once, whereas the square of the current index would need to be computed on each iteration.