#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
typedef long long ll;
#define F(i,k,n) for (ll i=k;i<=n;i++)
ll n;
ll k[N];
bool prime[N];
ll cnt=0;
int main(){ 
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	F(i,2,N-9){
		if(!prime[i]){
			cnt++;
			k[cnt]=i;
		}
		F(j,1,cnt){
			if (i*k[j]>N-9){
				break;
			}
			prime[i*k[j]]=1;
			if (!(i%k[j])){
				break;
			}
		}
	}
	ll sum=0;
	F(i,1,cnt){
		if (k[i]*k[i]>sqrt(n)) break;
		ll L=i-1,R=cnt+1,mid;
		while (L+1!=R){
			mid=(L+R)>>1;
			if (k[i]*k[mid]<=sqrt(n)) L=mid;
			else R=mid;
		}
		sum+=L-i;
	}
	cout<<sum;
	return 0;
}

第二个样例输出少了12