public class Nsieve {
	static void nsieve(int m) {
		int count = 0, i, j;
		byte[] flags = new byte[m];
		for (i = 2; i < m; ++i)
			if (flags[i] == 0) {
				++count;
				for (j = i << 1; j < m; j += i)
//					if (flags[j])
					flags[j] = 1;
			}
		System.out.format("Primes up to %8d %8d\n", m, count);
	}

	static void nsieve2(int m) {
		int count = 0, i, j;
		byte[] flags = new byte[(m + 7) >>> 3];
		for (i = 2; i < m; ++i) {
			if (((flags[i >>> 3] >> (i & 7)) & 1) == 0) {
				++count;
				for (j = i << 1; j < m; j += i)
					//noinspection lossy-conversions
					flags[j >>> 3] |= 1 << (j & 7);
			}
		}
		System.out.format("Primes up to %8d %8d\n", m, count);
	}

	public static void main(String[] args) {
		int m = Integer.parseInt(args[0]);
		for (int i = 0; i < 3; i++)
			nsieve2(10000 << (m - i));
	}
}