You do not need to find all prime factors and then pick the largest. Instead, you can divide out small factors as you find them.
Start with . While divides , divide by . Then increment . After all small factors are removed, what remains is either or the largest prime factor.
Why does this work? If has a composite factor, its prime factors are smaller and will be divided out first. The largest factor left is always prime.