Hacker News Reader

Comment by xrisk | Hacker News Reader

This is an exceptionally slow implementation. It took 1 hour and 29 minutes to generate all primes under 1 million. (I forgot I had left it running).

In contrast, a C++ implementation would take under 1s. Considering the standard Python multiplier of 5x-10x, that’s still a maximum of 10 seconds for a well-written implementation. And that’s the standard implementation with no fancy tricks.

Sometimes brevity is just not worth it...

View on HN

It is just a slow implementation, the usage of a dictionnary rather than a list is weird and the setup will be long, `get_sentinel` scan the whole list while it should just continue so it multiplies the complexity of the algorithm by n, line 22 scan the remainder of the list while it should just go for the multiples.

Here's a naive implementation I just wrote:

    def crible(n):
        nums = [True] * n
        nums[:1] = [False, False]

        for i, isPrime in enumerate(nums):
            if not isPrime:
                continue
            yield i
            j = 2
            while i*j < len(nums):
                nums[i*j] = False
                j += 1

It is much faster (and is about 10 lines of Python):

    timeit.timeit("list(crible(1000000))", number=1, globals={'crible': crible})
    0.9441672329999165

Reply on news.ycombinator.com