prime factorization of a number.

If you do not know what prime factorization is then google it , its very easy to understand.

if I give n=147 the program should give me 3 * 7 *7

I can write 3 * 7 *7 as 3*(7^2).

Start dividing the number from 2 and continue till

1) the number becomes 1 (you able to divide the number)

or

2)  the number you are dividing becomes more that square root of n.(means n is prime number and my prime factororization answer will be n*1.).

code in java :


import java.util.Scanner;
import java.lang.*;

class spoj
{


void primeFactorization(int n){

int b=2;
int p=0;

while(n!=1 || b<=(Math.sqrt(n))){

if((n%b)==0){

while(true){
if(n%b==0){
n=n/b;
p=p+1;
}
else{

System.out.println(b+"^"+p);
p=0;
break;
}

}

}

else{
b=b+1;
}


}

}

public static void main(String args[])
{

Scanner s=new Scanner(System.in);
int n=0;
int sum=0;
int i=0;
int val=s.nextInt();
spoj sp=new spoj();
sp.primeFactorization(val);

}
}


// please comment if the explanation is unclear.
// Or the code do not work for some input.
// Thanks

good implementation is given at http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/