3 ms·
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 contra
by xrisk 8y ago
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...
- Znafon 8y agoIt 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
- deleted 8y ago[deleted]