def primesUpto(x):
primes = [2]
sieve = [2]
i = 3
while i <= x:
composite = False
j = 0
while j < len(sieve):
sieve[j] = sieve[j] - 1
if sieve[j] == 0:
composite = True
sieve[j] = primes[j]
j += 1
if not composite:
primes.append(i)
sieve.append(i*i-i)
i += 1
return primes
print( len( list( primesUpto( 7919 )) )) # 1.41s 7.7 MB
# print( len( list( primesUpto( 17389 )) )) # 6.33s 7.8 MB n^2.15
ZGVmIHByaW1lc1VwdG8oeCk6CiAgICBwcmltZXMgPSBbMl0KICAgIHNpZXZlID0gWzJdCiAgICBpID0gMwogICAgd2hpbGUgaSA8PSB4OgogICAgICAgIGNvbXBvc2l0ZSA9IEZhbHNlCiAgICAgICAgaiA9IDAKICAgICAgICB3aGlsZSBqIDwgbGVuKHNpZXZlKToKICAgICAgICAgICAgc2lldmVbal0gPSBzaWV2ZVtqXSAtIDEKICAgICAgICAgICAgaWYgc2lldmVbal0gPT0gMDoKICAgICAgICAgICAgICAgIGNvbXBvc2l0ZSA9IFRydWUKICAgICAgICAgICAgICAgIHNpZXZlW2pdID0gcHJpbWVzW2pdCiAgICAgICAgICAgIGogKz0gMQogICAgICAgIGlmIG5vdCBjb21wb3NpdGU6CiAgICAgICAgICAgIHByaW1lcy5hcHBlbmQoaSkKICAgICAgICAgICAgc2lldmUuYXBwZW5kKGkqaS1pKQogICAgICAgIGkgKz0gMQogICAgcmV0dXJuIHByaW1lcwogICAgCnByaW50KCBsZW4oIGxpc3QoIHByaW1lc1VwdG8oIDc5MTkgKSkgICAgKSkgICAgICAjIDEuNDFzIDcuNyBNQgojIHByaW50KCBsZW4oIGxpc3QoIHByaW1lc1VwdG8oIDE3Mzg5ICkpICAgICkpICAgIyA2LjMzcyA3LjggTUIgIG5eMi4xNQ==