#include<stdio.h>
#define n 1000000
int t[n];
int main()
{ int c=0, p, j;
#if 0                  //   O(n²/ln n)   8.75s
  for(p=2;p<n;p++)
  { for(j=2;p%j;j++) ;
    if(j==p) c++;
  }
                       //              n=10^5 n=10^6          
#elif 0                //   O(n^1.5)   0.05s  1.38s
  for(p=2;p<n;p++)
  { for(j=2;p%j && j*j<p;j++) ;
    if(j==p || p%j) c++;
  }
#elif 0                //   O(n^1.5/ln n)   0.02s  0.33s
  for(p=2;p<n;p++)
  { for(j=0;j<c && p%t[j] && t[j]*t[j]<p;j++) ;
    if(j==c || p%t[j]) t[c++]=p;
  }
#elif 1                //   O(n ln n)   0.00s  0.46s
  for(p=2;p<n;p++) t[p]=1;
  for(p=2;p<n;p++)
   for(j=2*p;j<n;j+=p) t[j]=0;
  for(p=2;p<n;p++) c+=t[p];
#else                  //   O(n ln ln n)   0.00s  0.06s
  for(p=2;p<n;p++) t[p]=1;
  for(p=2;p*p<n;p++) if(t[p])
   for(j=p*p;j<n;j+=p) t[j]=0;
  for(p=2;p<n;p++) c+=t[p];
#endif
  printf("Il y a %d nombres premiers inférieurs à %d\n",c,n);
  return 0;
}