prime factorization

Prime factorization is a representation of a number as a multiplication of prime numbers.

If the problem you are solving has many test cases you better use the method 1 otherwise use the method 2.

Method 1 slow but useful when you need to factorize many numbers

Generate all the prime numbers in the needed range using the sieve of Eratosphen (which takes O(NlogN) ).
Now loop over the array of found primes until the number gets smaller than the current prime and check if the number is divisible on the current prime. If yes then divide the number into the found prime until it becomes non-divisible on that prime.
Here is the pseudocode

suppose we have the array of found primes called prime[10000]
and our number is N
for(  i=1 continue until a[i]<N)
{
        if( N is divisible on a[i])
        {
             divide N on a[i] until N becomes non divisible on N and keep track of the number of divisions
         }
}


method 2

Loop over numbers from 1, and our loop will end until our N becomes 1. If we found a number on which is divisible on and divide N on that number until it becomes non-divisible to that number. This method works the  same way as the previous method does. Of course the first number which we will find will be prime and other numbers won't be divisible on already found numbers.
 Use the method 1 if you have a problem which requires to factorize many numbers, if you have one big number you better use the second method.