Prime/PrimeFactorization Template

vector<int32_t> spf, primes;
void RunSieve(const int N) {
	spf.resize(N+1);
	iota(spf.begin(), spf.end(), 0);
	for (int i = 2; i < N; i += 2) {
		spf[i] = 2;
	}
	for(int i = 3; i * i < N; i += 2) {
		if (spf[i] == i) {
			for (int j = i * i; j < N; j += i<<1) {
				if (spf[j] == j) {
					spf[j] = i;
				}
			}
		}
	}
}

bool isPrime(const int x) {
	if (x & 1) return (spf[x] == x && (x > 1));
	return x == 2;
}

auto primeFactorization(int n) {
  vector<pair<int,int>> pf;
  if (spf[n] == 1) pf = {{n,1}};
  else {
    int cur = n;
    do {
      int cpf = spf[cur], exp = 0;
      while (cur % cpf == 0) {
        cur /= cpf, ++exp;
      }
      pf.push_back(make_pair(cpf,exp));
    } while (cur > 1);
  }
  return pf;
}