import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	// 100万までの素数素数を求める
	public static void main (String[] args) throws java.lang.Exception {
		long t =  System.currentTimeMillis();
 
		boolean[] p = new boolean[1000000];
		for(int i = 3; i < 1000; i += 2){
			for(int j = i*i; j < 1000000; j += i+i) p[j] = true;
		}
 
		int[] prime = new int[80000];
		prime[0] = 2;
		int n = 0;
		for(int i = 3; i < 1000000; i += 2){
			if(!p[i]) prime[++n] = i;
		}
 
		t = System.currentTimeMillis() - t;
		System.out.println(t + "ms");
		System.out.println(n);
	}
}

aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CiAKLyogTmFtZSBvZiB0aGUgY2xhc3MgaGFzIHRvIGJlICJNYWluIiBvbmx5IGlmIHRoZSBjbGFzcyBpcyBwdWJsaWMuICovCmNsYXNzIElkZW9uZQp7CgkvLyAxMDDkuIfjgb7jgafjga7ntKDmlbDntKDmlbDjgpLmsYLjgoHjgosKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbiB7CgkJbG9uZyB0ID0gIFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpOwogCgkJYm9vbGVhbltdIHAgPSBuZXcgYm9vbGVhblsxMDAwMDAwXTsKCQlmb3IoaW50IGkgPSAzOyBpIDwgMTAwMDsgaSArPSAyKXsKCQkJZm9yKGludCBqID0gaSppOyBqIDwgMTAwMDAwMDsgaiArPSBpK2kpIHBbal0gPSB0cnVlOwoJCX0KIAoJCWludFtdIHByaW1lID0gbmV3IGludFs4MDAwMF07CgkJcHJpbWVbMF0gPSAyOwoJCWludCBuID0gMDsKCQlmb3IoaW50IGkgPSAzOyBpIDwgMTAwMDAwMDsgaSArPSAyKXsKCQkJaWYoIXBbaV0pIHByaW1lWysrbl0gPSBpOwoJCX0KIAoJCXQgPSBTeXN0ZW0uY3VycmVudFRpbWVNaWxsaXMoKSAtIHQ7CgkJU3lzdGVtLm91dC5wcmludGxuKHQgKyAibXMiKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4obik7Cgl9Cn0=