I worked on Project Euler problem 3 (find largest prime factor of 600851475143) a while back and have tweaked with the code a few times to reuse for other problems, but I eventually found that there were numbers which came up with the wrong factorization list. I found that my problem was that my prime factorization function would create a bound of:
$\textrm{bound} = \textrm{ceil}(\sqrt n + 1)$
And use a loop to work it's way down for factors, which happened to work for the target of the problem. This led me to discover jagged numbers, " Not sqrt(n)-smooth: some prime factor of n is > sqrt(n)." (e.g. 1234124 is jagged) I've since made changes that start from the bottom rather than the top to search for factors, and it seems to run about as quickly as my "top down" algorithm.
I haven't been able to find anything on a formula or algorithm to determine whether a number is "jagged" or "smooth" in order to establish a bound other than just factorizing normally, so, as the title says, is there a way to establish a bound on the largest prime factor of a number $n$? I suspect that if there is a way to determine said bound, it might not be worth computing for either small or large (I don't know much about number theory) or it'll be difficult to implement. Any pointers?
In the worst case, the largest prime factor could equal $n$ itself - i.e., when $n$ is prime. In general you would need to know something about the prime factorization of $n$ already in order to give a more precise bound for the largest prime.
Instead, the more interesting bound is that the smallest prime of any composite number satisfies $$ \min p\leq \sqrt{n}, $$ which means if you start from the bottom and search for primes, you will either succeed before the bound is reached, or else $n$ is prime.