math/factor.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

const ll PRIME_SIZE = 10000000;
vector<int> primes; //call primeSieve(PRIME_SIZE); before

//Factorize the number n
vector<int> factorize(ll n) {
	vector<int> factor;
	ll num = n;
	int pos = 0;
	while(num != 1)  {
		if(num % primes[pos] == 0) {
			num /= primes[pos];
			factor.push_back(primes[pos]);
		}
		else pos++;
		if(primes[pos]*primes[pos] > num) break;
	}
	if(num != 1) factor.push_back(num);
	return factor;
}