Given a number n, find its prime factorization.
InputLet 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
OutputFor 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).
Sample Input5 6 12 17 45 50Sample Output
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.
N
and check if the number is divisible by the prime and increase the count one by one and then print it.O(N)
for every test case and N <= 109
.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
.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)
count
and divide our number N
by prime and loop till we extract all the current prime factor from numberwhile(N%i == 0) { //Updating count count++; // Dividing the number by prime // to continue to check further // divisiblity N /= i; }
count > 0
.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 << "*"; }
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