Hacker News new | comments | ask | show | jobs | submit login
Show HN: Prime number sieve in 31 lines of Python (github.com)
3 points by arthurcolle 3 months ago | hide | past | web | favorite | 2 comments



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...


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




Applications are open for YC Summer 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: