package main
import "fmt"
import "time"
// 100万までの素数を求める
func main(){
const N = 1000000
const sqrtN = 1000
var p[N] bool
var prime[80000] int
for i := 3; i < sqrtN; i += 2 {
if p[i] { continue }
for j := i*i; j < N; j += i+i {
p[j] = true
}
}
prime[0] = 2
n := 0
for i := 3; i < N; i += 2 {
if !p[i] {
n++
prime[n] = i
}
}
t
:= time.
Since(startTime
) fmt.Println(t.Seconds() * 1000)
fmt.Println(n)
}
cGFja2FnZSBtYWluCmltcG9ydCAiZm10IgppbXBvcnQgInRpbWUiCgovLyAxMDDkuIfjgb7jgafjga7ntKDmlbDjgpLmsYLjgoHjgosKZnVuYyBtYWluKCl7CgoJY29uc3QgTiA9IDEwMDAwMDAKCWNvbnN0IHNxcnROID0gMTAwMAoKCXZhciBwW05dIGJvb2wKCXZhciBwcmltZVs4MDAwMF0gaW50CgoJc3RhcnRUaW1lIDo9IHRpbWUuTm93KCkKIAoJZm9yIGkgOj0gMzsgaSA8IHNxcnROOyBpICs9IDIgewoJCWlmIHBbaV0geyBjb250aW51ZSB9CgkJZm9yIGogOj0gaSppOyBqIDwgTjsgaiArPSBpK2kgewoJCQlwW2pdID0gdHJ1ZQoJCX0KCX0KIAoJcHJpbWVbMF0gPSAyCgluIDo9IDAKCWZvciBpIDo9IDM7IGkgPCBOOyBpICs9IDIgewoJCWlmICFwW2ldIHsKCQkJbisrCgkJCXByaW1lW25dID0gaQoJCX0KCX0KIAoJdCA6PSB0aW1lLlNpbmNlKHN0YXJ0VGltZSkKCWZtdC5QcmludGxuKHQuU2Vjb25kcygpICogMTAwMCkKCWZtdC5QcmludGxuKG4pCn0=