2
\$\begingroup\$

This is an implementation of the Sieve of Eratosthenes :

  • It takes advantages of the fact that all primes from 5 and above can be written as 6X-1 or 6X+1,

  • For better space complexity, it uses a pretty accurate upperbound. Better estimations of the upper bound can be found here. I've observed a very slight increase in performance with this.


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
}

It was inspired by this code by Mr Martin.

Using the same benchmarking code in that answer, adding a fourth fractional digit in the timing results, plus some formatting, here are the results :

        ---------------------------------------------------------------
        |                |       Nbr   |          Time (sec)          | 
        |      Up to     |        of   |------------------------------|
        |                |    Primes   |   Martin's   |      This     |
        |----------------|-------------|------------------------------|
        |        100_000 |        9592 |       0.0008 |        0.0004 |
        |----------------|-------------|--------------|---------------|
        |      1_000_000 |      78_498 |       0.0056 |        0.0026 |
        |----------------|-------------|--------------|---------------|
        |     10_000_000 |     664_579 |       0.1233 |        0.0426 |
        |----------------|-------------|--------------|---------------|
        |    100_000_000 |   5_761_455 |       1.0976 |        0.5089 |
        |----------------|-------------|--------------|---------------|
        |  1_000_000_000 |  50_847_534 |      12.1328 |        5.9759 |
        |----------------|-------------|--------------|---------------|
        | 10_000_000_000 | 455_052_511 |     165.5658 |       84.5477 |
        |----------------|-------------|--------------|---------------|

Using Attabench, here is a visual representation of the performance of both codes while n is less than 2^16:

Attabench results


One thing I observe is some elements in the composites array are marked with true multiple times. This is expected (but unwanted) behavior since 6X-1 or 6X+1 aren't all primes.

What I'm looking for is making this Sieve of Eratosthenes quicker. I'm well aware of faster methods of finding primes.

Naming, code clarity, conciseness, consistency, etc, are welcome but are not the main point here.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

It takes advantages of the fact that all primes from 5 and above can be written as 6X-1 or 6X+1,

I don't think it does, really. It structures the code around that fact, but to take advantage of it, at a minimum you should replace

    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
    }

with

    while p <= twoOrThree {
        primes.append(p)
        p += 1
    }

which in my testing gives a significant speedup.


To maximise the advantage, you could reduce composites to only store flags for \$6X \pm 1\$. Proof of concept code (could be tidier):

    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)
    }

This gives a moderate speedup in my testing.

\$\endgroup\$
5
  • \$\begingroup\$ Thank you for the answer. Here are the benchmarks, and they favor the code in the question (original being Martin's, and eratosthenes2 is the code in your answer). Attabench confirms the benchmarks. \$\endgroup\$
    – ielyamani
    Jan 14, 2019 at 13:06
  • \$\begingroup\$ @Carpsen90, I don't know Swift and there seem to be some subtleties around imports which both this question and the answer you reference brush under the table, but I compared a tweaked version of your code with my code on tio.run . Full tested code. I see user time: 12.470 s for your code and 7.002 s for mine. tio.run isn't ideal for benchmarking, but that's a significant improvement. \$\endgroup\$ Jan 14, 2019 at 14:02
  • \$\begingroup\$ (I suspect the problem is that you've benchmarked my code sieving three times as far as your code). \$\endgroup\$ Jan 14, 2019 at 14:04
  • \$\begingroup\$ The benchmarks were correct and can still be reproduced. You didn't mention in your answer this line var composites = Array(repeating: false, count: n / 3 + 1), which makes all the difference. Here are the new benchmarks which favor your code. \$\endgroup\$
    – ielyamani
    Jan 14, 2019 at 15:03
  • \$\begingroup\$ The answer is intended to be a code review, not a patch. \$\endgroup\$ Jan 14, 2019 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.