#include<stdio.h>
#include<stdlib.h>
#define n 1000000000
int main()
#if 0
{ int t[n], i, j, c=0;
  for(i=n;i--;) t[i]=i;
  for(i=2;j=i*i,j<n;i++) if(t[i]==i) for(;j<n;j+=i) t[j]=i;
  for(i=n;--i>1;) c+=t[i]==i;
#elif 1
{ int i, j, c=0, m=n/2;
  char *t=malloc(m*sizeof(*t));
  for(i=m;i--;) t[i]=1;
  for(i=3;j=i*i/2,j<m;i+=2) if(t[i/2]) for(;j<m;j+=i) t[j]=0;
  for(i=m;i--;) c+=t[i];
#else
{ int i, j, k, c=0, m=1;
  while(m*m<n) m+=m;
  int tete[m], suite[m], m1=m-1;
  for(i=m;i--;) tete[i]=i, suite[i]=0;
  tete[1]=0;
  for(i=2;j=i*i,j<n;i++) if(tete[i]==i) for(;j<m;j+=i) tete[j]=0;
  for(j=i*i;j<m;j++) tete[j]=0;
  for(i=m;i--;) c+=tete[i]>0;
  for(i=2;i<n;i++) for(j=tete[i&m1],c+=!j,tete[i&m1]=0;j;j=k) k=suite[j], suite[j]=tete[(i+j)&m1], tete[(i+j)&m1]=j;
#endif
  printf("%d %d\n",n,c);
  return 0;
}