/C++/Prime factorisation of a number in c++

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;
}

Similar codes

3 votes323 views5 answers
Combine two vectors c++
C++
5 votes386 views3 answers
Fast io c++
C++
6 votes353 views3 answers
C++ dynamic array
C++
0 vote345 views1 answer
Bnchch
C++
12 votes316 views1 answer
How to sort in descending order c++
C++
0 vote317 views1 answer
C++ print number not in scientific notation
C++
1 vote342 views1 answer
How to compare two char* in c++
C++
0 vote346 views1 answer
Print elements of linked list
C++
0 vote324 views1 answer
Waiting in a serial as the spool reflect the queue operation. Demonstrate Printer Behavior in context of Queue.Subject to the Scenario implement the Pop and Push Using C++.
C++
1 vote314 views2 answers
Insert vector to end of vector c++
C++