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]) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment