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