欧拉筛

#include <bits/stdc++.h>
using namespace std;

int p[50010];
int st[50010];
int cnt, n;
int main()
{
	cin >> n;
	memset(st, true, sizeof st);
	st[1] = false;
	for (int i = 2; i <= n; i++)
	{
		if (st[i]) p[++cnt] = i;
		for (int j = 1; j <= cnt && i * p[j] <= n; j++)
		{
			st[p[j] * i] = false;
			if (i % p[j] == 0) 
				break;
		}
	}
	cout << cnt;
	return 0;
}