是一道很水的题，用链表就能解决了，但是由于加减乘除的时间复杂度太高，所以不能一个一个判断，得用筛法。这里采用线性筛。

template <class _Tp = const unsigned long long int>
class P { _Tp *p { nullptr }; };
signed WinMain(int argv, char* argc[]) {}
#include <cstdio>
#include <ctype.h>
typedef unsigned long long ULL;
int add(int a, int b) {
	if (!a) return b;
	return add((a & b) << 1, a ^ b);
}
ULL quick_mul(int a, int b) {
	ULL res = 0;
	for (ULL t = a; b; b >>= 1, t <<= 1)
		if (b & 1) res = add(res, t);
	return res;
}
ULL square(int a) {
	return quick_mul(a, a);
}
int read() {
	char ch;
	int res = 0;
	while (!isdigit(ch = getchar()));
	res = ch ^ 48;
	while (isdigit(ch = getchar())) res = add(quick_mul(res, 10), ch ^ 48);
	return res;
}
int binary_div(int a, int b) {
	int left = -1, right = add(1ll << 31, 0xffffffff);
	while (left + 1 != right) {
		int mid = add(left, right) >> 1;
		if (quick_mul(b, mid) <= a) left = mid;
		else right = mid;
	}
	return left;
}
int mod(int a, int b) {
	return a - quick_mul(binary_div(a, b), b);
}
void print(int a) {
	if (!a) return;
	print(binary_div(a, 10));
	putchar(mod(a, 10) ^ 48);
}
struct Node {
	int dat;
	Node* next;
};
Node* create() {
	Node* head = new Node;
	head->next = nullptr;
	return head;
} 
Node* insert(Node* node, int dat) {
	Node* newNode = new Node;
	newNode->next = node->next;
	node->next = newNode;
	newNode->dat = dat;
	return newNode;
}
#define MAX_N 100005
signed main(int argv, char* argc[]) {
	int n = read();
	Node* head = create();
	Node* end = head;
	int res = 0;
	bool is_prime[MAX_N];
	for (auto& elem : is_prime) elem = true;
	for (int i = 2; i <= n; i = add(i, 1)) {
		if (is_prime[i]) {
			end = insert(end, i);
			res = add(res, 1);
		}
		for (Node* p = head->next; p; p = p->next){
			int mul = quick_mul(p->dat, i);
			if (mul > n) break;
			is_prime[mul] = false;
			if (!mod(i, p->dat)) break;
		}
	}
	print(res);
	return 0;
}