Eratospheres in Swift

Carpsen.swift

func eratosthenesSieve(to n: Int) -> [Int] {

    guard 2 <= n else { return [] }

    var composites = Array(repeating: false, count: n + 1)
    var primes: [Int] = []
    let d = Double(n)
    let upperBound = Int((d / _log(d)) * (1.0 + 1.2762/_log(d)))
    primes.reserveCapacity(upperBound)
    let squareRootN = Int(d.squareRoot())

    //2 and 3
    var p = 2
    let twoOrThree = min(n, 3)
    while p <= twoOrThree {
        primes.append(p)
        var q = p * p
        let step = p * (p - 1)
        while q <= n {
            composites[q] = true
            q += step
        }
        p += 1
    }

    //5 and above
    p += 1
    while p <= squareRootN {
        for i in 0..<2 {
            let nbr = p + 2 * i
            if !composites[nbr] {
                primes.append(nbr)
                var q = nbr * nbr
                var coef = 2 * (i + 1)
                while q <= n  {
                    composites[q] = true
                    q += coef * nbr
                    coef = 6 - coef
                }
            }
        }
        p += 6
    }

    while p <= n {
        for i in 0..<2 {
            let nbr = p + 2 * i
            if nbr <= n && !composites[nbr] {
                primes.append(nbr)
            }
        }
        p += 6
    }

    return primes
}

var ps = eratosthenesSieve(to: 100_000_000)
print(ps.count)
print(ps[ps.count - 1])

Peter.swift

func eratosthenesSieve(to n: Int) -> [Int] {

    guard 2 <= n else { return [] }

    var primes: [Int] = []
    let d = Double(n)
    let upperBound = Int((d / _log(d)) * (1.0 + 1.2762/_log(d)))
    primes.reserveCapacity(upperBound)

    //2 and 3
    var p = 2
    let twoOrThree = min(n, 3)
    while p <= twoOrThree {
        primes.append(p)
        p += 1
    }

    // To save memory and improve cache performance, store flags for values \pm 1 (mod 6)
    // Even index => (idx / 2) * 6 + 1 = 3 * idx + 1  == 1 (mod 6)
    // Odd index => ((idx-1) / 2) * 6 + 5 = 3 * idx + 2  == 5 (mod 6)
    var composites = Array(repeating: false, count: n / 3 + 1)
    let squareRootN = Int(d.squareRoot())

    var pidx = 1
    p = 5
    while p <= squareRootN {
        if !composites[pidx] {
            primes.append(p)

            var qidx = 3 * pidx * (pidx + 2) + 1 + (pidx & 1)
            let delta = p << 1
            let off = (4 - 2 * (pidx & 1)) * pidx + 1
            while qidx < composites.count {
                composites[qidx - off] = true
                composites[qidx] = true
                qidx += delta
            }
            if qidx - off < composites.count {
                composites[qidx - off] = true
            }
        }

        pidx += 1
        p += 2 + 2 * (pidx & 1)
    }

    while p <= n {
        if !composites[pidx] { primes.append(p) }
        pidx += 1
        p += 2 + 2 * (pidx & 1)
    }

    return primes
}

var ps = eratosthenesSieve(to: 100_000_000)
print(ps.count)
print(ps[ps.count - 1])