from time import time
 
_start_time_ = time()
 
_primes_ = [2]
 
 
def init_primes():
    global _primes_
    global _primes_list_
 
    for n in range(3, 1_000_000, 2):
        is_prime = True
 
        for p in _primes_:
            if p * p > n:
                break
            elif n % p == 0:
                is_prime = False
                break
 
        if is_prime:
            _primes_.append(n)
 
 
if __name__ == '__main__':
    init_primes()
 
    print(len(_primes_))
 
    print('\nElapsed time: {:.2f}s'.format(time() - _start_time_), end='')
 
 

ZnJvbSB0aW1lIGltcG9ydCB0aW1lCgpfc3RhcnRfdGltZV8gPSB0aW1lKCkKCl9wcmltZXNfID0gWzJdCgoKZGVmIGluaXRfcHJpbWVzKCk6CiAgICBnbG9iYWwgX3ByaW1lc18KICAgIGdsb2JhbCBfcHJpbWVzX2xpc3RfCgogICAgZm9yIG4gaW4gcmFuZ2UoMywgMV8wMDBfMDAwLCAyKToKICAgICAgICBpc19wcmltZSA9IFRydWUKCiAgICAgICAgZm9yIHAgaW4gX3ByaW1lc186CiAgICAgICAgICAgIGlmIHAgKiBwID4gbjoKICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgICAgIGVsaWYgbiAlIHAgPT0gMDoKICAgICAgICAgICAgICAgIGlzX3ByaW1lID0gRmFsc2UKICAgICAgICAgICAgICAgIGJyZWFrCgogICAgICAgIGlmIGlzX3ByaW1lOgogICAgICAgICAgICBfcHJpbWVzXy5hcHBlbmQobikKCgppZiBfX25hbWVfXyA9PSAnX19tYWluX18nOgogICAgaW5pdF9wcmltZXMoKQogICAgCiAgICBwcmludChsZW4oX3ByaW1lc18pKQogICAgCiAgICBwcmludCgnXG5FbGFwc2VkIHRpbWU6IHs6LjJmfXMnLmZvcm1hdCh0aW1lKCkgLSBfc3RhcnRfdGltZV8pLCBlbmQ9JycpCgo=