Prime Factorization

This problem comes form Project Euler. I solved it with a computer program written in C++.

Problem:

What is the largest prime factor of the number 600851475143?

Solution:

It is tempting to write a function to find the prime factorization of a given number. Why? Because it's cool. I wrote that function, too, but I'm only going to cover the process of solving the given problem.

When solving a programming problem, you should always start on paper to get an idea of what your algorithm needs to do. Suppose I wanted to find the largest prime factor of 90, or what if I wanted to find the largest prime factor of 260? I might do something like what I did in the diagram to the right. In words, our algorithm might look something like this:

Start with your number.
Keep dividing by its factors until you find the biggest prime.

How is the computer going to know which numbers to try? We'll be using a loop, so we can start at 2 and work our way up through the numbers. The computer's factorization of 260 would look more like this: 13/7 is less than 2, 13/8 is even smaller, and 13/9 is smaller still. We're not going to get any more numbers that go evenly into 13 once our divisor is greater than 13/2. We can stop dividing whenever the divisor is greater than half of the number we're dividing. Notice that 4 divides 260, but it did not come up in our list of factors. Instead, we divided 2 out twice. 2 is prime, and 4 is not. Our algorithm automatically sifts out composite numbers by dividing their prime factors out first. In words, our algorithm looks something like this:

Start with your number.
Divide it by 2.
If it divides evenly, keep dividing by 2, otherwise, try 3.
If it divides evenly, keep dividing by 3, otherwise, try 4.
Keep dividing this way until your divisor is greater than or equal to half the original number.

Now we're ready for pseudo-code:

from ( divisor = 2 until divisor >= number/2 )
{
  if ( number is divisible by divisor ) then
    number <- number/divisor
  else
    increment divisor
}
return number

We would like to save our selves some time by only using prime numbers, but we don't have a list of primes. However, we do know that 2 is the only even prime number, so after trying 2, we only have to try odd numbers, which cuts our list of divisors in half. This is my final code:

unsigned long long LargestPrimeFactor(unsigned long long number)
{
  int divisor = 2;
  while(divisor<=sqrt((float)number))
  {
    if(number%divisor==0)
    {
      number = number/divisor;
    }
    else if(divisor==2)
    {
      divisor++;
    }
    else
    {
      divisor+=2;
    }
  }
  return number;
}

The largest prime factor of 600851475143 is 6857.