#include <iostream>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <list>

using namespace std;

const unsigned long N = 0x100000000;

class Primzahlen {
  private:
    static bitset<N> primes;

  public:
    static void init() {
      primes.set();
      primes.reset(0); primes.reset(1);

      for (unsigned long k = 2; k*k < N; k++)
        if (primes[k])
          for (unsigned long i = k; i * k < N; i++)
            primes.reset(i*k);
    }

    static bool ist_primzahl(unsigned long n) {
      if (n < N)
        return primes[n];
      else if (N * N > n) {
        for (unsigned long k = 2; k < N; k++)
          if (primes[k] && n % k == 0)
            return false;
        return true;
      } else {
        ostringstream err;
        err << n << " lies outside of acceptable range for ist_primzahl [0.." << N*N << ")";
        throw domain_error(err.str());
      }
    }
};

bitset<N> Primzahlen::primes{};

class Primfaktor {
  public:
    unsigned long p, k;

    Primfaktor(unsigned long p_ = 0, unsigned long k_ = 1): p(p_), k(k_) {}

    friend ostream& operator<<(ostream& stream, Primfaktor pf) {
      stream << pf.p;
      if (pf.k != 1)
        stream << "^" << pf.k;
      return stream;
    }
};

class Primfaktorzerlegung {
  private:
    list<Primfaktor> factors;

  public:
    Primfaktorzerlegung(unsigned long n = 1) {
      for (unsigned long p = 2; p * p <= n && p * p < N; p++) {
        if (!Primzahlen::ist_primzahl(p))
          continue;
    
        unsigned long k = 0;
        while (n % p == 0) {
          k++;
          n /= p;
        }
    
        if (k >= 1)
          factors.push_back(Primfaktor{p, k});
      }
    
      if (n != 1)
        factors.push_back(Primfaktor{n});
    }

    operator unsigned long() {
      unsigned long res = 1;
      for (Primfaktor pf: factors)
        while (pf.k-- > 0)
          res *= pf.p;
      return res;
    }

    friend bool ist_primzahl(const Primfaktorzerlegung& pfz) {
      if (pfz.factors.empty())
        return false;
    
      list<Primfaktor>::const_iterator it = pfz.factors.begin();
      return it->k == 1 && ++it == pfz.factors.end();
    }

    friend ostream& operator<<(ostream& stream, Primfaktorzerlegung pfz) {
      if (pfz.factors.empty())
        return stream << "1";
    
      for (list<Primfaktor>::iterator i = pfz.factors.begin();
        i != pfz.factors.end();
        i++) {
        if (i != pfz.factors.begin())
          stream << "*";
        stream << *i;
      }
    
      return stream;
    }
};

int main() {
  Primzahlen::init();

  unsigned long zweip = 1;
  while (true) {
    Primfaktorzerlegung pfz{zweip};
    cout << setw(20) << zweip;
    if (ist_primzahl(pfz))
      cout << " Mersenne-Primzahl: ";
    else
      cout << ":                   ";
   cout << pfz << endl;
   if (zweip != static_cast<unsigned long>(pfz))
     cout << "Typumwandlung (" << static_cast<unsigned long>(pfz) << ") entspricht nicht Argument (" << zweip << ")" << endl;

    unsigned long old_zweip = zweip;
    zweip = (zweip << 1) | 1;
    if (zweip > N * (N - 1) + (N - 1) || old_zweip == zweip)
      break;
  }
}