Medium Factorization | Editorial by manishjoshi394

We can modify the sieve of Eratosthenes so that it stores the smallest Prime factor of every number up to MAX = 107. 
After this Preprocessing, we use the smallest Prime Factor sieve to extract the whole Prime Factorization in O( MAX * log(log MAX) + log n) which fits the time limit easily.

Explanation of Time Complexity: 
- First term is contributed by sieve preprocessing up to MAX = 107.
- Second term comes because at worst prime factorization of a number n can contain only log n prime factors.

```
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define SPEED ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FOR(i, a, b) for (ll i = a; i < b; ++i)
#define RFOR(i, b, a) for (ll i = b; i >= a; --i)
#define DEBUG(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');\
stringstream _ss(_s); istream_iterator<string> _it(_ss); _debug(_it, args);}
#define endl "\n"
#define F first
#define S second
#define pb(x) push_back(x)
#define ALL(x) x.begin(), x.end()
#define mp(x, y) make_pair(x, y)

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void _debug(istream_iterator<string>) {}
template<typename T, typename... Args>
void _debug(istream_iterator<string> it, T first, Args... args) {
 cerr << ">> " << *it << " : " << first << endl; _debug(++it, args...);
}
template <typename T1, typename T2>
inline ostream& operator << (ostream& out, const pair<T1, T2>& p) {
 return out << "(" << p.F << ", " << p.S << ")";
}
template<typename T>
inline ostream& operator << (ostream& out, const vector<T>& v) {
 if (v.empty()) return out << "[]";
 else { out << '['; for (auto& e : v) { out << e << ", "; } return out << "\b\b]"; }
}
template<typename T>
inline ostream& operator << (ostream& out, const set<T>& s) {
 if (s.empty()) return out << "{}";
 else { out << '{'; for (auto& e : s) { out << e << ", "; } return out << "\b\b}"; }
}
template<typename T>
inline ostream& operator << (ostream& out, const unordered_set<T>& s) {
 return out << set<T>(ALL(s));
}
template<typename T1, typename T2>
inline ostream& operator << (ostream& out, const map<T1, T2>& m) {
 if (m.empty()) return out << "{}";
 out << '{'; for (auto& p : m) { out <
inline ostream& operator << (ostream& out, const unordered_map<T1, T2>& m) {
 return out << map<T1, T2>(ALL(m));
}
template<typename T>
inline ostream& operator << (ostream& out, const ordered_set<T>& s) {
 return out << set<T>(ALL(s));
}

typedef long long ll;
typedef long double ld;
typedef vector<long long> vll;
typedef pair<ll, ll> pll;
typedef vector<pair<ll, ll>> vpll;
typedef unordered_map<ll, ll> STll;
/************************************** MAIN PROGRAM ********************************************/
/**** @author: MANISH JOSHI ****/

const int MAX = 1e7 + 2;

int minFac[MAX];

void sieve()
{
 for (int i = 2; i * i <= MAX; ++i)
 {
 if (!minFac[i])
 {
 for (int j = 2 * i; j < MAX; j += i)
 {
 if(!minFac[j])
 minFac[j] = i;
 }
 }
 }
 for (int i = 1; i < MAX; ++i)
 {
 if (minFac[i] == 0)
 minFac[i] = i;
 }
 minFac[0] = 1; // just kidding
}

int main()
{
 //freopen("input.txt", "r", stdin);
 SPEED
 ll n;
 sieve();
 while (cin >> n)
 {
 vll ansVec;
 ansVec.pb(1);
 while (n > 1)
 {
 int div = minFac[n];
 n /= div;
 ansVec.pb(div);
 }
 FOR(i, 0, ansVec.size()) {
 if (i != ansVec.size() - 1)
 cout << ansVec[i] << " x ";
 else cout << ansVec[i] << endl;
 }
 }
}
/************************************** END OF PROGRAM ******************************************/

```

Medium Factorization | Editorial by manishjoshi394

Download submission

All caught up!

View submission

Is your resume even shortlisted?