prime factorisation of a number in c++
// Function that returns a vector containing all the prime factors of n (25 --> 5, 5)
vector<long long> prime_factorisation(long long n)
{
//spf is smallest prime factor
map<long long, long long> spf;
vector<long long> ans(0);
for(long long i = 2; i <= n; i++) spf[i] = i;
for (long long i = 2; i <= n; i++)
if (spf[i] == i)
for (long long j = i * i; j <= n; j += i)
if (spf[j] == j)
spf[j] = i;
while (n != 1)
{
ans.push_back(spf[n]);
n /= spf[n];
}
return ans;
}