#include <cstdio>
using namespace std;

bool Eratos[1000000];

int main()
{
	Eratos[0] = Eratos[1] = false;
	for (int i = 0; i < 1000000; i++){
		Eratos[i] = true;
	}
	for (int i = 2; i < 1000; i++) {
		if (Eratos[i]) {
			for (int j = 2 * i; j < 1000000; j += i) {
				Eratos[j] = false;
			}
		}
	}
	int n,res;
	res = 1;
	for (int i = 2; i < 1000000; i++) {
		if (Eratos[i])
			Eratos[i] = res;
		res++;
	}
	while (scanf("%d", &n)) {
		res = 0;
		while (!Eratos[n]) {
			n--;
		}
		printf("%d\n",Eratos[n]);
	}
	return 0;
}