Python list is not an array

[alegrigoriev]

Python's list buitin doesn't do random access, it's not an array. bytearray builtin is a real array.
Yet, somehow the bytearray gains not too much.
On my setup, the original version does 20 passes in 10 seconds, an with the bytearray it only does 42 passes.
Also, every step of the sieve can actually start from factor*factor, because every N*factor for N<factor has already been eliminated. This doesn't give much gain, though.

[BrunoDSL]

If you want something closer to an actual array, the deque builtin from the collections module is the one to use.

[sueskind]

Actually, Python lists do have an amortized item access complexity of O(1). Internally it is represented as an array. However, pop intermediate and insert are O(n).

[alegrigoriev]

Actually, Python lists do have an amortized item access complexity of O(1). Internally it is represented as an array. However, pop intermediate and insert are O(n).

Thank you. I actually looked at the python sources after I posted it and, sure, the list() is implemented as an array.

[aberent]

Python does also have a true array type in the standard library. See https://docs.python.org/3/library/array.html for details. I use this in my version of the prime sieve (https://github.com/davepl/Primes/pull/36)