#include <queue>
#include <iostream>
#include <utility>
#include <vector>
 
using namespace std;
 
int main()
{
  unsigned max_num_primes;
  cout << "Wie viele Primzahlen? ";
  cin >> max_num_primes;
 
  // Die 2 sparen wir uns mal bei der Rechnung:
  if (max_num_primes > 0)
    {
      cout << "2\t";
      unsigned num_primes_printed = 1;
      unsigned current_number = 3;
 
      std::priority_queue<pair<unsigned int, unsigned int>,
        vector< pair<unsigned int, unsigned int> >,
        greater< pair<unsigned int, unsigned int> >
        >
        queue;
 
      while (num_primes_printed < max_num_primes)
        {
          if (queue.empty() || queue.top().first != current_number)
            {
              cout << current_number << '\t';
              ++num_primes_printed;
              queue.push(make_pair(current_number*current_number, current_number*2));
            }
          else
            {
              for(pair<unsigned int, unsigned int> top = queue.top();
                  top.first == current_number;
                  top=queue.top())
                {
                  queue.pop();
                  queue.push(make_pair(top.first + top.second, top.second));
                }              
            }
          current_number += 2;
        }
      cout << '\n';
    }
}