#include <iostream>                                                                                                       
#include <vector>                                                                                                         
#include <list>                                                                                                           
                                                                                                                          
#define MAX 1000000                                                                                                       
                                                                                                                          
using namespace std;                                                                                                      
                                                                                                                          
int main() {                                                                                                              
  vector<int> prime_numbers;                                                                                              
  prime_numbers.push_back(2);                                                                                             
  prime_numbers.push_back(3);                                                                                             
  prime_numbers.push_back(5);                                                                                             
  prime_numbers.push_back(7);                                                                                             
                                                                                                                          
  list<int> search_list;                                                                                                  
  for (int i = 5; i < MAX; i++) {                                                                                         
    if (i % 2 != 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0) {                                                           
      search_list.push_back(i);                                                                                           
    }                                                                                                                     
  }                                                                                                                       
  int h = search_list.front();                                                                                            
  while (h * h < search_list.back()) {                                                                                    
    prime_numbers.push_back(h);                                                                                           
    list<int>::iterator itr = search_list.begin();                                                                        
    while (itr != search_list.end()) {                                                                                    
      if (*itr % h == 0) {                                                                                                
        itr = search_list.erase(itr);                                                                                     
      } else {                                                                                                            
        itr++;                                                                                                            
      }                                                                                                                   
    }                                                                                                                     
    h = search_list.front();                                                                                              
  }                                                                                                                       
  for (list<int>::iterator itr = search_list.begin(); itr != search_list.end(); itr++) {                                  
    prime_numbers.push_back(*itr);                                                                                        
  }                                                                                                                       
                                                                                                                          
  int n;                                                                                                                  
  while (cin >> n) {                                                                                                      
    int count = 0;                                                                                                        
    for (vector<int>::iterator itr = prime_numbers.begin(); itr != prime_numbers.end(); itr++) {                          
      if (*itr > n) break;                                                                                                
      count++;                                                                                                            
    }                                                                                                                     
    cout << count << endl;                                                                                                
  }                                                                                                                       
                                                                                                                          
  return 0;                                                                                                               
}

Measured memory_bytes: 4368