Once upon a time, I read an article where the author said something like this:

My professor asked us whether we had prime factored our Social Security numbers yet. Being a normal person, I laughed with everyone else. Being a nerd, I managed to resist for only three days.

Of course I immediately rushed to my computer and wrote a prime factoring program. At the time it was kind of hard because the computer I was using didn't have integers big enough to hold Social Security numbers. This is a lot easier now.

This example's FindFactors function finds a number's prime factors.

// Return the number's prime factors.
private List FindFactors(long num)
{
    List result = new List();

    // Take out the 2s.
    while (num % 2 == 0)
    {
        result.Add(2);
        num /= 2;
    }

    // Take out other primes.
    long factor = 3;
    while (factor * factor <= num)
    {
        if (num % factor == 0)
        {
            // This is a factor.
            result.Add(factor);
            num /= factor;
        }
        else
        {
            // Go to the next odd number.
            factor += 2;
        }
    }

    // If num is not 1, then whatever is left is prime.
    if (num > 1) result.Add(num);

    return result;
}

First, while the number num is divisible by 2, the program adds 2 to the list of factors and divides num by 2.

Next for odd numbers factor = 3, 5, 7, etc. the program determines whether factor divides evenly into num. If factor does divide evenly into num, the program adds factor the the list of factors and divides num by it. If factor does not divide num evenly, the program adds 2 to factor to check the next odd number.

The program stops when factor * factor is greater than num.