Online Prime Factorization

Prime Factorization -> Technique of finding all prime factors of a number.
There are various algorithms for finding prime factors of a number.

Lets start with the easiest one :

Suppose the number is 12.
Now its prime factors will be 2 , 2 and 3.

Now we need to check for all prime numbers whether they divide the number which we need to factorize or not.But how to decide which prime numbers need to be considered ?

  With little thinking we can conclude that we should start counting from 2 since 1 is not a prime number and the maximum prime number that will be a factor can be the number itself.
Hence we can get the range to check as [2,N] where N is number we need to factorize.

Second conclusion that we can make is that we need to divide the number by a factor till we are able to, for example 8 has factors 2 , 2 and 2 so we need to divide 8 by 2 three times.In other words till remainder is 0.                     //while(N%i==0)

Now the final conclusion could be we can change number N itself once we have got a factor.
For example to find factors of 12 once we divide it by 2 we get 6 , now instead of checking 12 with 2,3,...; we can directly check for 6 by making N = 6 since no number greater than 6 can be a factor of 12.

Pseudo code for the above algorithm can be written as :

The Brute Way

for (i = 2 to N)

{
      while (N % i == 0)

      {
        print(i);
        N /= i;
      }
}

On scratching a bit of head you will be able to conclude that instead of looping till N you could

loop till N/i and later if N>1 you can conclude N as prime.

So the final pseudo code will be :

The Smart Way

for (i = 2 to N/i) 

{
      while (N % i == 0) 

      {
        print(i);
        N /= i;
      }
}

if(N>1) print(N);

Applications : 

The most exciting application of this algorithm is finding no of factors of a number.As we can see,we can find

all prime factors and count from above algorithm, we can use the below formula to find count of all the 

factors of a number :

count(a^p*b^q*....m^z)=(1+a)(1+b)....(1+z).
This can be stored in a variable in above algorithm in similar complexity. 
Problems : Project Euler Problem 12

 All suggestions and doubts are welcomed.