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