Given a number n, find its prime factorization.

Let us say we want to write a number as multiples of its prime factors in exponent form. For Example, 12 = 2^2*3^1, 15 = 3^1*5^1, 2 = 2^1 (no need to multiply with 1, 1 is not prime), 32 = 2^5 and so on. Here, '2^5' means 2 to the power 5. First line of input will contain a number T = no. of test cases. Next n lines will each contain a number n, where 2<=n<=10^9

For each test case, you need to print a single line with prime factors in exponent form as described above. The smallest factor should appear first in the output. There should be no space in between the characters. The only possible characters will be a number , '*' for multiplication operator and '^' for 'something raised to power something (exponent).

5
6
12
17
45
50

2^1*3^1
2^2*3^1
17^1
3^2*5^1
2^1*5^2

1)  O(n) algorithm will give you "Time Limit Exceeded"

Here we have been given a number N and we have to write it as a multiple of its prime factors in exponent form on given number of test cases.

• The first thing comes in mind to run a loop over 2 to N and check if the number is divisible by the prime and increase the count one by one and then print it.
• But this approach might give you Time Limited Excedded as it of O(N) for every test case and N <= 109.
• But if we see it more deeply then we only have to run this loop on till the Square root of N because all the numbers above it would have maximum exponent 1 and also their will be only 1 prime factor because multiplication of 2 numbers will be greater than 109.
• While iterating over 2 to Square root of N, we'll repeatedly check if the number N is divisible by current prime or not.

            // While number is divisible by i
            // It will be divisible by prime only 
            // otherwise it would have been factorized
            // before.
            while(N%i == 0) 
    

• If it is divisible then we'll increase our count and divide our number N by prime and loop till we extract all the current prime factor from number

            while(N%i == 0) {
                
                //Updating count
                count++;
                
                // Dividing the number by prime
                // to continue to check further
                // divisiblity
                N /= i;
            }
    

• Now we'll print prime factor and its exponent if count > 0.
• After that if still N is left to be factorized then we'll print a *.

            // If exponent is more than 0
            if(count > 0) {
                
                // Print Prime i.e., i
                // and its exponent
                cout << i << "^" << count;
                
                // Printing * only if N is greater
                // than 1 because it will be divisible
                // by more primes also.
                if(N > 1) cout << "*";
            }
    

• Now When we come out our loop we'll check if still N is greater than 1 then print N with exponent as 1.

editorial written by ishabh

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    // T - number of testcases
    // N - number which we have to
    // factorize
    int T,N;

    // Input Tests
    cin >> T;

    // Iterating over all tests
    for(int test = 1;test <= T;test++) {

        // Input Number
        cin >> N;

        // Stores the exponent of current prime
        int count;

        // Looping till square root of N
        // Otherwise number above that have maximum
        // exponent 1 and they will be obviously prime
        for(int i = 2;i<=sqrt(N);i++) {

            //initially count is 0
            count = 0;

            // While number is divisible by i
            // It will be divisible by prime only
            // otherwise it would have been factorized
            // before.
            while(N%i == 0) {

                //Updating count
                count++;

                // Dividing the number by prime
                // to continue to check further
                // divisiblity
                N /= i;
            }

            // If exponent is more than 0
            if(count > 0) {

                // Print Prime i.e., i
                // and its exponent
                cout << i << "^" << count;

                // Printing * only if N is greater
                // than 1 because it will be divisible
                // by more primes also.
                if(N > 1) cout << "*";
            }
        }

        // If still N is greater than 1 it means it
        // still can be factorized but now N is a prime
        // otherwise it would have been factorized before
        // It should have power 1 otherwise greater power will
        // be greater than 10^9
        if(N > 1) {
            cout << N << "^1";
        }
        cout << endl;
    }
}

featured solution by ishabh