Note that because you're dividing the number by its factors you don't necessarily need all the primes up to the square root of the original number. The approach I've taken in the past requires a primality-testing function and is basically

def prime-factorize (n):
    d = 2
    while n > 1:
        if n % d = 0:
            add-divisor(d)
        else:
            d = next-prime(d)

def next-prime (n):
    if n < 2:
        2
    else if n = 2:
        3
    else if even?(n):
        next-prime(n - 1)
    else:
        candidate = n + 2
    while true:
        if prime?(candidate):
            return candidate
        else:
            candidate = candidate + 2

This approach mostly depends on having a good prime testing function. (Actually, with a really good function, the 'while n > 1' can be replaced with 'until prime?(n)', but the simplest version of 'prime?' would involve testing divisibility against all primes below sqrt(n), and if you're doing that, you might as well just build the list once and use it in your algorithm.)

My primality-testing can be seen at

 <a href="http://aperiodic.net/phil/lisp/primes.lisp">http://aperiodic.net/phil/lisp/primes.lisp</a><br />

(yes, Common Lisp) and it's probably a bit heavyweight for one-offs like your question. I have it lying around for Project Euler things.