package main
import "fmt"
import "time"
 
// 100万までの素数を求める
func main(){
 
	const N = 1000000
	const sqrtN = 1000
 
	var p[N] bool
	var prime[80000] int
 
	startTime := time.Now()
 
	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=