Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# pjt33/Carpsen.swift

Created Jan 14, 2019
Eratospheres in 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])
 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])
to join this conversation on GitHub. Already have an account? Sign in to comment