#include <stdio.h>
#include <stdlib.h>
#include <time.h>

char p[1000000];
int prime[80000];

int main(void) {
	clock_t t = clock();
	int i, j, n;
	
	for(i = 3; i < 1000; i += 2){
		for(j = i * i; j < 1000000; j += i + i) p[j] = 1;
	}

	n = 0;
	prime[0] = 2;
	for(i = 3; i < 1000000; i += 2){
		if(!p[i]) prime[++n] = i;
	}

	t = clock() - t;
	printf("%.3fms\n", 1000 * (double)t / CLOCKS_PER_SEC);
	printf("%d\n", n);
	return 0;
}