POJ.3292 Semi-prime H-numbers

1.Problem
http://poj.org/problem?id=3292

2.Idea
Sieve of Eratosthenes

3.Source

 bool isPrime[1000006];  
 vector<ll> p;  
 int dp[1000006];  
 void prep()  
 {  
      for (int i = 5; i < 1000006; i += 4) {  
           if (!isPrime[i]) {  
                p.push_back(i);  
                for (int j = i * 5; j < 1000006; j += i*4) {  
                     isPrime[j] = true;  
                }  
           }  
      }  
      int n = p.size();  
      for (int i = 0; i < n; i++)  
           for (int j = i; j < n && (p[i] * p[j]) < 1000006; j++) {  
                int k = p[i] * p[j];  
                dp[k] = 1;  
           }  
      for (int i = 1; i < 1000006; i++) {  
           dp[i] += dp[i - 1];  
      }  
 }  
 void solve()  
 {  
      int h;  
      while (1) {  
           cin >> h;  
           if (h == 0) break;  
           cout << h << " " << dp[h] << endl;  
      }  
 }  
 int main()  
 {  
      prep();  
      solve();  
      return 0;  
 }