Skip to content

Instantly share code, notes, and snippets.

@pjt33

pjt33/Carpsen.swift

Created Jan 14, 2019
Embed
What would you like to do?
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
You can’t perform that action at this time.