1. /**
  2.  🍪 the_hyp0cr1t3
  3.  🍪 30.05.2021 04:20:37
  4. **/
  5. #ifdef W
  6.     #include <k_II.h>
  7. #else
  8.     #include <bits/stdc++.h>
  9.     using namespace std;
  10. #endif
  11. #define pb emplace_back
  12. #define all(x) x.begin(), x.end()
  13. #define sz(x) static_cast<int32_t>(x.size())
  14.  
  15. const int64_t k_II = 2e18;
  16. const int INF = 2e9, MOD = 1e9+7;
  17. const int N = 1e7 + 5;
  18.  
  19. int main() {
  20.     cin.tie(nullptr)->sync_with_stdio(false);
  21.     int n;
  22.     // spf is the smallest prime factor
  23.     // precompute spf for all n using prime sieve (O(n loglogn))
  24.     array<int, N> spf; iota(all(spf), 0);
  25.     for(int z = 4; z < N; z += 2) spf[z] = 2;
  26.     for(int z = 3; z*z < N; z += 2)
  27.         if(spf[z] == z) for(int y = z*z; y < N; y += z*2)
  28.             if(spf[y] == y) spf[y] = z;
  29.  
  30.     // Answer queries in O(log n) per query.
  31.     // Log n because the maximum number of prime factors is log2 n.
  32.     while(cin >> n) {
  33.         cout << 1;
  34.         while(n > 1) {
  35.             cout << " x " << spf[n];
  36.             n /= spf[n];
  37.         } cout << '\n';
  38.     }
  39.     
  40. } // ~W