#coding: utf-8
# 100万までの素数を求める
from time import clock
t = clock()
p = bytearray(1000000)
for i in range(3, 1000, 2):
if p[i]: continue
for j in range(i * i, 1000000, i + i): p[j] = 1
prime = [2] + [i for i in range(3, 1000000, 2) if p[i] == 0]
t = clock() - t
print('{:.3f} ms'.format(1000 * t))
print(len(prime))
I2NvZGluZzogdXRmLTgKIyAxMDDkuIfjgb7jgafjga7ntKDmlbDjgpLmsYLjgoHjgosKIApmcm9tIHRpbWUgaW1wb3J0IGNsb2NrCgp0ID0gY2xvY2soKQogCnAgPSBieXRlYXJyYXkoMTAwMDAwMCkKZm9yIGkgaW4gcmFuZ2UoMywgMTAwMCwgMik6CglpZiBwW2ldOiBjb250aW51ZQoJZm9yIGogaW4gcmFuZ2UoaSAqIGksIDEwMDAwMDAsIGkgKyBpKTogcFtqXSA9IDEKIApwcmltZSA9IFsyXSArIFtpIGZvciBpIGluIHJhbmdlKDMsIDEwMDAwMDAsIDIpIGlmIHBbaV0gPT0gMF0KIAp0ID0gY2xvY2soKSAtIHQKcHJpbnQoJ3s6LjNmfSBtcycuZm9ybWF0KDEwMDAgKiB0KSkKcHJpbnQobGVuKHByaW1lKSkK